排序

引言

为什么想起来最近写这一些列的文章,因为最近一个朋友吐槽面试的有67年工作经验的员工,连基本的排序都不能实现,所以想了下,如果让自己来做,能不能讲的清楚这一些列的排序。所以就动手写了这一系列的文章,也算是自己了解巩固下。

 

常用的排序算法

一、冒泡排序

二、选择排序

三、插入排序

四、快速排序

五、堆排序

六、归并排序

七、基数排序

八、希尔排序

九、桶排序

 

冒泡排序(Bubble Sort

冒泡排序也称为:沉降排序(SinkingSort),之所以有这两个名字和他的实现方法有关,因为冒泡排序的实现方式是将数据列表中的最小的数据往前移动,想水里面的气泡一样向上浮。这样也就对应着最大的数据,逐渐往后移动,对应着上浮的就是下沉。

冒泡排序每次只比较相邻的两个数字的大小,再将一个数字和后面数字继续比较大小,一轮比较完成后在比较下一轮数据。知道最终没有数据可以比较位置,排序结束。

 常见排序算法(一)插图

Java:

public class BubbleSort {

    public static void main(String[] args) {

        int[] a = new int[]{9, 2, 7, 8, 5, 6, 3, 4, 1};
        for (int i = a.length 1; i >= 1; i–) {
            for (int j = 0; j < i; j++) {
                int temp1 = a[j];
                int temp2 = a[j + 1];
                a[j] = temp1 > temp2 ? temp2 : temp1;
                a[j + 1] = temp1 > temp2 ? temp1 : temp2;
                printArrays(a);
            }
        }

    }

    private static void printArrays(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + “、”);
        }
        System.out.println();
    }

}

 

Out:

297856341

279856341

278956341

278596341

278569341

278563941

278563491

278563419

278563419

278563419

275863419

275683419

275638419

275634819

275634189

275634189

257634189

256734189

256374189

256347189

256341789

256341789

256341789

253641789

253461789

253416789

253416789

235416789

234516789

234156789

234156789

234156789

231456789

231456789

213456789

123456789

 

程序的实现逻辑很简单,变及数组,依次将两个数字做比较,如果小的在大的前面,那么换一个位置,否则位置不换,继续拿大的和后面的比较。重复实现逻辑,为什么外面循环用i–,呢,因为每次我们实现一次排序,总能得到一个最大值,这个值,一定是排在了这个数组的最后一个,所以,最后面的一个我们是不需要比较的,这样无形中也就减少了运算。

从代码实现上来看,冒泡排序的时间复杂度为:O(n2);简单的说执行速度,取决于for循环的次数,链表的大小。

选择排序(Selection sort

选择排序是一种很直观简单暴力的排序算法,简单的说,就是,先遍历一遍数据,把最小的数据找出来,交换位置,放在第一位,然后在从把后面的链表继续遍历,找出最小数据,然后在,交换位置,继续遍历后续链表。知道全部遍历完成

常见排序算法(一)插图1

    常见排序算法(一)插图2 

public static void main(String[] args) {
    int[] a = new int[]{9, 2, 7, 8, 5, 6, 3, 4, 1};


    for (int i = 0; i < a.length; i++) {
        int min = i;
        for (int j = i; j < a.length; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
        printArrays(a);

    }


}

 

从代码实现上来看,选择排序的时间复杂度为:O(n2);简单的说执行速度,取决于for循环的次数,链表的大小。

上面的排序,我们不难看出,每次排序,其实我们不仅可以找到最小值,还可以找到最大值,这种情况,我们可以将排序算法优化下

public static void main(String[] args) {
    int[] a = new int[]{4, 2, 1, 7, 5, 8, 3, 9, 6, 8, 7, 0, 9, 2, 3,10,2,23,1,2,3,2,2,2,2};

    for (int i = 0; i < a.length – i; i++) {

        int min = i;
        int max = i;
        for (int j = i; j < a.length – i; j++) {

            if (a[min] > a[j]) {
                min = j;
            }
            if (a[max] < a[j]) {
                max = j;
            }
        }
        if (min != max) {

            int maxTemp = a[a.length – i – 1];
            a[a.length – i – 1] = a[max];
            a[max] = maxTemp;

            int temp = a[i];
            if (a[i] > a[min]) {
                a[i] = a[min];
                a[min] = temp;
            }
            printArrays(a);

        }
    }

}

每次排序同时将最小的放在最前面,将最大的放在最右边,循环的时候,也不需要每次都循环到链表的最后段,每次循环都踢掉链表的两端,在进行排序操作.

实际上这两种写法,在效率上相差并不大,下面那种虽然在循环次数上变少了,但是循环类的操作变复杂了。之所以这样写,只是说明下,我么并不是只能每次找最小的数,也可以按照需要,变换写法。

插入排序(Insertion Sort)

   插入排序是一种最简单的排序算法,在数据量小的情况下,是一种非常有效的排序方式,

他的核心思想,保证轮询到的数据前面的链表部分是顺序的,将需要比较的数字和前面的排序完成的链表进行比较,插入到一个合适的位置。

常见排序算法(一)插图3

常见排序算法(一)插图4

public static void main(String[] args) {

    int[] a = new int[20];
    for (int i = 0; i < 20; i++) {
        int random = (int) (Math.random() * 10);
        a[i] = random;
    }

    for (int i = 1; i < a.length; i++) {

        int current = a[i];
        int seq = i;
        while (seq > 0) {
            int temp = a[seq – 1];
            if (current >= temp) {
                break;
            } else {
                a[seq – 1] = current;
                a[seq] = temp;
            }
            seq–;
        }
    }
    printArrays(a);

}

 

插入排序比较适合.属于稳定的排序,适合于数据量小,部分数据有序的情况排序。他比较依赖于原链表的混乱程度。

当链表是有序的,也就是最优情况下,每个数只要和前面的一个数想比较,就可以了。这时候的时间复杂度是O(n);

当然逆向来说,如果链表是有序的,但是和我们需要排序的规则是相反的,那么每个数字都要和前面的所有数字比较。这个时候,时间复杂度就变成了O(n2)

 

 

发表评论

电子邮件地址不会被公开。