几种常见的排序算法

排序算法概述

常见的排序算法整体上可以分为两大类，比较类排序和非比较类排序，如下所示：

下表是不同排序算法的复杂度对比

相关的一些概念：

• 稳定/不稳定，如果 a=b，并且 a 在 b 之前，排序后能保证 a b 顺序不会变化就是稳定排序，如果有可能造成 a b 顺序互换就是不稳定排序
• 时间复杂度，对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

冒泡排序

两个数比较大小，较大的数下沉，较小的数冒起来。

排序过程：

• 从后向前进行冒泡，第1次遍历即可将最小的元素移至第一位
• 重复上面的步骤对剩余的 n-1 个元素进行冒泡，得到第二小的元素放在第二位
• 以此类推直到最后一个元素排序完成

注意也可以从前向后将最大的值先移至最后一位，道理相同！

Java 示例

public static void maopaoSort(int[] arr){
    int temp;
    for (int i = 0; i < arr.length-1; i++) { //因为是两两比较，所以一共冒泡 n-1 趟
        for (int j = arr.length-1; j > i; j--) { //从最后一个元素开始冒，冒到上次已经排好序的位置 i 即可
            if (arr[j] < arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

动图演示

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

排序算法不稳定，是冒泡排序的一种改进，由于从两端向中间比较，且每次移动的距离较远，因此可以减少移动次数，所以比较快； 时间复杂度为 O(n*log2(n)), 由于使用递归方法，因此需要一个 O(log2(n)) 的栈空间。

Java 示例代码

public static void quickSort(int a[], int low, int high) {  // 这里其实 low = 0；high = r.length-1; 但是后面要用递归，需要指定不同的边界
    int i, j, temp;   //temp 用于保存基准元素
    if(low < high) {   // 这里确保待比较的元素个数大于 1
        i = low;
        j = high;
        temp = a[i];  // 令第一个数据为基准
        while(i<j) {
            while(i<j && a[j]>=temp) j--; // 从数组的右端向左依次和基准比较，直到遇到小于基准的数或者比较完依然没遇到。
                          // 注意，相等的时候也要换过去，这也造成快排不具有稳定性
            if(i<j){    // 如果在没比较完之前遇到，则：
                a[i] = a[j]; i++;  // 右侧较小的数挪到数组左侧去，注意这里不用交换，因为基准数已经保存在变量 temp 里了
            }
            while(i<j&&a[i]<=temp) i++; // 然后又从左侧向右开始和基准比较
            if(i<j){a[j] = a[i]; j--;   // 直到遇到大于基准的数，将其挪到数组右侧去
            }
        }
        a[i] = temp; // 直到 i 和 j 相遇时第一圈比完，这个位置就应该是基准在数组排序中的位置，且此时 i=j
        if(low < i-1) quickSort(a,low,i-1); // 最后对基准左侧和右侧的数据不断重复上述过程
        if(high > j+1) quickSort(a,j+1,high); // 注意 if 里的判断条件, 因为此时 r[i] or r[j] 已经不需要再比较
    }

}

动图演示

简单选择排序

选择排序的算法思想很简单，先找出最小的数放在左侧第一位，再从剩下 n-1 个数中找到最小的数放在左侧第二位，以此类推；该排序法不稳定 (例如序列 5 8 5 2 9，第一次选择后第一个 5 会被交换到第二个 5 之后)；时间复杂度 O(n^2) 。

看上去和冒泡差不多，只不过比较的过程中只记录最小记录的下标，每趟比完后再将找到的最小元素交换到有序队列的队尾。

Java 示例代码

public static void selectSort(int a[]){
    int i, j, minIndex, temp;  
    for(i=0; i<a.length; i++){
        minIndex = i;
        for(j=i+1; j<a.length; j++){
            if(a[j] < a[minIndex]){
                minIndex = j;
            }
        }
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

堆排序

堆排序也是一种选择排序，是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

动图示意

直接插入排序法

将待排序的记录逐个插入到已经排好序的序列的适当位置，直到全部插入完为止。一般认为第一个值已排好序，从第二个值开始向其中插入；时间复杂度 O(n^2)；空间复杂度 O(1)，因为只使用了一个 temp 临时变量的辅助空间。

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2-5

Java 示例代码

public static void insertSort(int a[]){
    int i,j,temp;
    for(i=1; i<a.length; i++){
        j=i-1;
        temp = a[i];  // 这里必须用一个临时变量存储 arr[i], 因为后面的 while 会改变其值
        while(j>=0 && a[j]>temp) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

动图演示

希尔排序

1959 年 Shell 发明，第一个突破 O(n2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

先掌握不同排序算法的思想，代码实现还需要一个熟练的过程！

总结

除了选择排序多一个最小下标的辅助参量 minIndex，其他排序都是用到 i, j, temp 这三个辅助量；很容易理解选择排序和冒泡排序都是两重循环，而插入排序则使用 while 为待插入元素腾位置，快速排序则要用递归；其中选择排序和快速排序不稳定，而冒泡和插入则是稳定排序。

参考

• 十大经典排序算法（动图演示）