这或许是东半球讲十大排序算法最好的一篇文章

作者 | 不该相遇在秋天

责编 | 程序员小吴

冒泡排序

冒泡排序无疑是最为出名的排序算法之一,从序列的一端开始往另一端冒泡(你可以从左往右冒泡,也可以从右往左冒泡,看心情),依次比较相邻的两个数的大小(到底是比大还是比小也看你心情)。

冒泡排序动图演示

冒泡排序动图演示

图解冒泡

以 [ 8,2,5,9,7 ] 这组数字来做示例,上图来战:

从左往右依次冒泡,将小的往右移动

冒泡排序1

冒泡排序1

首先比较第一个数和第二个数的大小,我们发现 2 比 8 要小,那么保持原位,不做改动。位置还是 8,2,5,9,7 。

指针往右移动一格,接着比较:

冒泡排序2

冒泡排序2

比较第二个数和第三个数的大小,发现 2 比 5 要小,所以位置交换,交换后数组更新为:[ 8,5,2,9,7 ]。

指针再往右移动一格,继续比较:

冒泡排序3

冒泡排序3

比较第三个数和第四个数的大小,发现 2 比 9 要小,所以位置交换,交换后数组更新为:[ 8,5,9,2,7 ]

同样,指针再往右移动,继续比较:

冒泡排序4

冒泡排序4

比较第 4 个数和第 5 个数的大小,发现 2 比 7 要小,所以位置交换,交换后数组更新为:[ 8,5,9,7,2 ]

下一步,指针再往右移动,发现已经到底了,则本轮冒泡结束,处于最右边的 2 就是已经排好序的数字。

通过这一轮不断的对比交换,数组中最小的数字移动到了最右边。

接下来继续第二轮冒泡:

冒泡排序5

冒泡排序5

冒泡排序6

冒泡排序6

冒泡排序7

冒泡排序7

由于右边的 2 已经是排好序的数字,就不再参与比较,所以本轮冒泡结束,本轮冒泡最终冒到顶部的数字 5 也归于有序序列中,现在数组已经变化成了[ 8,9,7,5,2 ]。

冒泡排序8

冒泡排序8

让我们开始第三轮冒泡吧!

冒泡排序9

冒泡排序9

冒泡排序10

冒泡排序10

由于 8 比 7 大,所以位置不变,此时第三轮冒泡也已经结束,第三轮冒泡的最后结果是[ 9,8,7,5,2 ]

紧接着第四轮冒泡:

冒泡排序11

冒泡排序11

9 和 8 比,位置不变,即确定了 8 进入有序序列,那么最后只剩下一个数字 9 ,放在末尾,自此排序结束。

代码实现

public static void sort(int arr[]){
    for( int i = 0 ; i < arr.length - 1 ; i++ ){
        for(int j = 0;j < arr.length - 1 - i ; j++){
            int temp = 0;
            if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡的代码还是相当简单的,两层循环,外层冒泡轮数,里层依次比较,江湖中人人尽皆知。

我们看到嵌套循环,应该立马就可以得出这个算法的时间复杂度为O(n2)。

冒泡优化

冒泡有一个最大的问题就是这种算法不管不管你有序还是没序,闭着眼睛把你循环比较了再说。

比如我举个数组例子:[ 9,8,7,6,5 ],一个有序的数组,根本不需要排序,它仍然是双层循环一个不少的把数据遍历干净,这其实就是做了没必要做的事情,属于浪费资源。

针对这个问题,我们可以设定一个临时遍历来标记该数组是否已经有序,如果有序了就不用遍历了。

public static void sort(int arr[]){
    for( int i = 0;i < arr.length - 1 ; i++ ){
        boolean isSort = true;
        for( int j = 0;j < arr.length - 1 - i ; j++ ){
            int temp = 0;
            if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSort = false;
            }
        }
        if(isSort){
            break;
        }
    }
}

选择排序

选择排序的思路是这样的:首先,找到数组中最小的元素,拎出来,将它和数组的第一个元素交换位置,第二步,在剩下的元素中继续寻找最小的元素,拎出来,和数组的第二个元素交换位置,如此循环,直到整个数组排序完成。

至于选大还是选小,这个都无所谓,你也可以每次选择最大的拎出来排,也可以每次选择最小的拎出来的排,只要你的排序的手段是这种方式,都叫选择排序。

选择排序动画演示

选择排序动画演示

图解选排

我们还是以[ 8,2,5,9,7 ]这组数字做例子。

第一次选择,先找到数组中最小的数字 2 ,然后和第一个数字交换位置。(如果第一个数字就是最小值,那么自己和自己交换位置,也可以不做处理,就是一个 if 的事情)

选择排序1

选择排序1

第二次选择,由于数组第一个位置已经是有序的,所以只需要查找剩余位置,找到其中最小的数字5,然后和数组第二个位置的元素交换。

选择排序2

选择排序2

第三次选择,找到最小值 7 ,和第三个位置的元素交换位置。

选择排序3

选择排序3

第四次选择,找到最小值8,和第四个位置的元素交换位置。

选择排序4

选择排序4

最后一个到达了数组末尾,没有可对比的元素,结束选择。

如此整个数组就排序完成了。

代码实现

public static void sort(int arr[]){
    for( int i = 0;i < arr.length ; i++ ){
        int min = i;//最小元素的下标
        for(int j = i + 1;j < arr.length ; j++ ){
            if(arr[j] < arr[min]){
                min = j;//找最小值
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

双层循环,时间复杂度和冒泡一模一样,都是O(n2)

插入排序

插入排序的思想和我们打扑克摸牌的时候一样,从牌堆里一张一张摸起来的牌都是乱序的,我们会把摸起来的牌插入到左手中合适的位置,让左手中的牌时刻保持一个有序的状态。

那如果我们不是从牌堆里摸牌,而是左手里面初始化就是一堆乱牌呢? 一样的道理,我们把牌往手的右边挪一挪,把手的左边空出一点位置来,然后在乱牌中抽一张出来,插入到左边,再抽一张出来,插入到左边,再抽一张,插入到左边,每次插入都插入到左边合适的位置,时刻保持左边的牌是有序的,直到右边的牌抽完,则排序完毕。

图解插排

数组初始化:[ 8,2,5,9,7 ],我们把数组中的数据分成两个区域,已排序区域和未排序区域,初始化的时候所有的数据都处在未排序区域中,已排序区域是空。

插入排序1

插入排序1

第一轮,从未排序区域中随机拿出一个数字,既然是随机,那么我们就获取第一个,然后插入到已排序区域中,已排序区域是空,那么就不做比较,默认自身已经是有序的了。(当然了,第一轮在代码中是可以省略的,从下标为1的元素开始即可)

插入排序2

插入排序2

第二轮,继续从未排序区域中拿出一个数,插入到已排序区域中,这个时候要遍历已排序区域中的数字挨个做比较,比大比小取决于你是想升序排还是想倒序排,这里排升序:

插入排序3

插入排序3

第三轮,排 5 :

插入排序4

插入排序4

第四轮,排 9 :

插入排序5

插入排序5

第五轮,排 7

插入排序6

插入排序6

排序结束。

代码实现

public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int value = arr[i];
        int j = 0;//插入的位置
        for (j = i-1; j >= 0; j--) {
            if (arr[j] > value) {
                arr[j+1] = arr[j];//移动数据
            } else {
                break;
            }
        }
        arr[j+1] = value; //插入数据
    }
}

从代码里我们可以看出,如果找到了合适的位置,就不会再进行比较了,就好比牌堆里抽出的一张牌本身就比我手里的牌都小,那么我只需要直接放在末尾就行了,不用一个一个去移动数据腾出位置插入到中间。

所以说,最好情况的时间复杂度是 O(n),最坏情况的时间复杂度是 O(n2),然而时间复杂度这个指标看的是最坏的情况,而不是最好的情况,所以插入排序的时间复杂度是 O(n2)。

希尔排序

希尔排序这个名字,来源于它的发明者希尔,也称作“缩小增量排序”,是插入排序的一种更高效的改进版本。

我们知道,插入排序对于大规模的乱序数组的时候效率是比较慢的,因为它每次只能将数据移动一位,希尔排序为了加快插入的速度,让数据移动的时候可以实现跳跃移动,节省了一部分的时间开支。

图解希尔排序

待排序数组 10 个数据:

希尔排序1

希尔排序1

假设计算出的排序区间为 4 ,那么我们第一次比较应该是用第 5 个数据与第 1 个数据相比较。

希尔排序2

希尔排序2

调换后的数据为[ 7,2,5,9,8,10,1,15,12,3 ],然后指针右移,第 6 个数据与第 2 个数据相比较。

希尔排序3

希尔排序3

指针右移,继续比较。

希尔排序4

希尔排序4

希尔排序5

希尔排序5

如果交换数据后,发现减去区间得到的位置还存在数据,那么继续比较,比如下面这张图,12 和 8 相比较,原地不动后,指针从 12 跳到 8 身上,继续减去区间发现前面还有一个下标为 0 的数据 7 ,那么 8 和 7 相比较。

希尔排序6

希尔排序6

比较完之后的效果是 7,8,12 三个数为有序排列。

希尔排序7

希尔排序7

当最后一个元素比较完之后,我们会发现大部分值比较大的数据都似乎调整到数组的中后部分了。

假设整个数组比较长的话,比如有 100 个数据,那么我们的区间肯定是四五十,调整后区间再缩小成一二十还会重新调整一轮,直到最后区间缩小为 1,就是真正的排序来了。

希尔排序8

希尔排序8

指针右移,继续比较:

希尔排序9

希尔排序9

重复步骤,即可完成排序,重复的图就不多画了。

我们可以发现,当区间为 1 的时候,它使用的排序方式就是插入排序。

代码实现

public static void sort(int[] arr) {
    int length = arr.length;
    //区间
    int gap = 1;
    while (gap < length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for (int i = gap; i < length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            //跨区间排序
            while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap = gap / 3;
    }
}

可能你会问为什么区间要以 gap = gap*3 + 1 去计算,其实最优的区间计算方法是没有答案的,这是一个长期未解决的问题,不过差不多都会取在二分之一到三分之一附近。

归并排序

归并字面上的意思是合并,归并算法的核心思想是分治法,就是将一个数组一刀切两半,递归切,直到切成单个元素,然后重新组装合并,单个元素合并成小数组,两个小数组合并成大数组,直到最终合并完成,排序完毕。

归并排序动画演示

归并排序动画演示

图解归并排序

我们以[ 8,2,5,9,7 ]这组数字来举例

归并排序1

归并排序1

首先,一刀切两半:

归并排序2

归并排序2

再切:

归并排序3

归并排序3

再切

归并排序4

归并排序4

粒度切到最小的时候,就开始归并

归并排序5

归并排序5

归并排序6

归并排序6

归并排序7

归并排序7

数据量设定的比较少,是为了方便图解,数据量为单数,是为了让你看到细节,下面我画了一张更直观的图可能你会更喜欢:

归并排序8

归并排序8

代码实现

我们上面讲过,归并排序的核心思想是分治,分而治之,将一个大问题分解成无数的小问题进行处理,处理之后再合并,这里我们采用递归来实现:

    public static void sort(int[] arr) {
        int[] tempArr = new int[arr.length];
        sort(arr, tempArr, 0, arr.length-1);
    }

    /**
     * 归并排序
     * @param arr 排序数组
     * @param tempArr 临时存储数组
     * @param startIndex 排序起始位置
     * @param endIndex 排序终止位置
     */
    private static void sort(int[] arr,int[] tempArr,int startIndex,int endIndex){
        if(endIndex <= startIndex){
            return;
        }
        //中部下标
        int middleIndex = startIndex + (endIndex - startIndex) / 2;

        //分解
        sort(arr,tempArr,startIndex,middleIndex);
        sort(arr,tempArr,middleIndex + 1,endIndex);

        //归并
        merge(arr,tempArr,startIndex,middleIndex,endIndex);
    }

    /**
     * 归并
     * @param arr 排序数组
     * @param tempArr 临时存储数组
     * @param startIndex 归并起始位置
     * @param middleIndex 归并中间位置
     * @param endIndex 归并终止位置
     */
    private static void merge(int[] arr, int[] tempArr, int startIndex, int middleIndex, int endIndex) {
        //复制要合并的数据
        for (int s = startIndex; s <= endIndex; s++) {
            tempArr[s] = arr[s];
        }

        int left = startIndex;//左边首位下标
        int right = middleIndex + 1;//右边首位下标
        for (int k = startIndex; k <= endIndex; k++) {
            if(left > middleIndex){
                //如果左边的首位下标大于中部下标,证明左边的数据已经排完了。
                arr[k] = tempArr[right++];
            } else if (right > endIndex){
                //如果右边的首位下标大于了数组长度,证明右边的数据已经排完了。
                arr[k] = tempArr[left++];
            } else if (tempArr[right] < tempArr[left]){
                arr[k] = tempArr[right++];//将右边的首位排入,然后右边的下标指针+1。
            } else {
                arr[k] = tempArr[left++];//将左边的首位排入,然后左边的下标指针+1。
            }
        }
    }

我们可以发现 merge 方法中只有一个 for 循环,直接就可以得出每次合并的时间复杂度为 O(n) ,而分解数组每次对半切割,属于对数时间 O(log n) ,合起来等于 O(log2n) ,也就是说,总的时间复杂度为 O(nlogn) 。

关于空间复杂度,其实大部分人写的归并都是在 merge 方法里面申请临时数组,用临时数组来辅助排序工作,空间复杂度为 O(n),而我这里做的是原地归并,只在最开始申请了一个临时数组,所以空间复杂度为 O(1)。

快速排序

快速排序的核心思想也是分治法,分而治之。它的实现方式是每次从序列中选出一个基准值,其他数依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,然后再对左边和右边的两组数分别选出一个基准值,进行同样的比较移动,重复步骤,直到最后都变成单个元素,整个数组就成了有序的序列。

图解快排

我们以[ 8,2,5,0,7,4,6,1 ]这组数字来进行演示

首先,我们随机选择一个基准值:

快速排序1

快速排序1

与其他元素依次比较,大的放右边,小的放左边:

快速排序2

快速排序2

然后我们以同样的方式排左边的数据:

快速排序3

快速排序3

继续排 0 和 1 :

快速排序4

快速排序4

由于只剩下一个数,所以就不用排了,现在的数组序列是下图这个样子:

快速排序5

快速排序5

右边以同样的操作进行,即可排序完成。

单边扫描

快速排序的关键之处在于切分,切分的同时要进行比较和移动,这里介绍一种叫做单边扫描的做法。

我们随意抽取一个数作为基准值,同时设定一个标记 mark 代表左边序列最右侧的下标位置,当然初始为 0 ,接下来遍历数组,如果元素大于基准值,无操作,继续遍历,如果元素小于基准值,则把 mark + 1 ,再将 mark 所在位置的元素和遍历到的元素交换位置,mark 这个位置存储的是比基准值小的数据,当遍历结束后,将基准值与 mark 所在元素交换位置即可。

代码实现:

public static void sort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

private static void sort(int[] arr, int startIndex, int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    //切分
    int pivotIndex = partitionV2(arr, startIndex, endIndex);
    sort(arr, startIndex, pivotIndex-1);
    sort(arr, pivotIndex+1, endIndex);
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];//取基准值
    int mark = startIndex;//Mark初始化为起始下标

    for(int i=startIndex+1; i<=endIndex; i++){
        if(arr[i]<pivot){
            //小于基准值 则mark+1,并交换位置。
            mark ++;
            int p = arr[mark];
            arr[mark] = arr[i];
            arr[i] = p;
        }
    }
    //基准值与mark对应元素调换位置
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

双边扫描

另外还有一种双边扫描的做法,看起来比较直观:我们随意抽取一个数作为基准值,然后从数组左右两边进行扫描,先从左往右找到一个大于基准值的元素,将下标指针记录下来,然后转到从右往左扫描,找到一个小于基准值的元素,交换这两个元素的位置,重复步骤,直到左右两个指针相遇,再将基准值与左侧最右边的元素交换。

我们来看一下实现代码,不同之处只有 partition 方法:

```
public static void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}

top Created with Sketch.