算法基础之8大排序算法最优解-必读 - 后端精进之路

算法是面试考察的重点，基础算法更是基础，只有打好了基础才可能在此之上深入学习。这里总结了最常见的排序算法，每个都进行了详细分析，大家可以好好研究吸收。

算法的稳定性：通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

1.1 插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤：

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。)

复杂度： 时间复杂度O(n^2), 空间复杂度O(1)；排序时间与元素已排序的程度有关。最佳情况，输入数组是已经排好序的数组，运行时间是O(n)； 最坏情况，输入数组是逆序，运行时间是O(n^2)。
稳定性： 相等元素的前后顺序没有改变，从原无序序列出去的顺序仍是排好序后的顺序，所以插入排序是稳定的。

// insertion sort
/* 如果要改成范型，可以将函数声明改成如下：
   public <T extends Comparable<? super T>> void insertionSort(T [] a)
  对于函数中出现的比较等操作，可以替换为a.compareTo(b)， 如果a.compareTo(b) < 0 则代表a < b
*/
public void insertionSort(int [] a) {
        int j;

        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            for (j = i; j > 0 && temp < a[j-1]; j--) {
                a[j] = a[j-1];
            }

            a[j] = temp;
        }
    }

1.2 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

算法步骤：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1;
• 按增量序列个数k，对序列进行k 趟排序;
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

复杂度： 最坏情形：O(N2)，选择N是2的幂，这使得除最后一个增量是1以外的增量都是偶数。此时如果数组的偶数位置上有N/2个同是最大的数，而在基数位置上有N/2个同为最小的数，由于除最后一个增量外所有的增量都是偶数，因此当我们在最后一趟排序之前，N/2个最大的元素仍在偶数位置上，而N/2个最小的元素也还是在奇数位置上。于是，在最后一趟排序开始之前第i个最小的数（i<=N/2）在位置2i-1上，将第i个元素恢复到其正确的位置需要在数组中移动i-1个间隔，这样仅仅将N/2个元素放在正确的位置上至少需要O(N2)的工作。

稳定性： 由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。所以shell排序是不稳定的排序算法。

    // shell sort
    public static void shellSort(int [] a) {
        int j;

        for (int gap = a.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < a.length; i++) {
                int temp = a[i];

                for (j = i; j >= gap && temp < a[j - gap]; j -= gap) {
                    a[j] = a[j-gap];
                }
                a[j] = temp;
            }
        }
    }

1.3 选择排序与冒泡排序

1.3.1 选择排序

算法步骤：

• 首先在未排序序列中找到最小元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

复杂度： 时间复杂度O(n^2), 空间复杂度O(1)
稳定性： 排序时间与输入无关，最佳情况，最坏情况都是如此, 不稳定

1.3.2 冒泡排序

可以看成是选择排序的相反过程，每次找到最大的元素放到数组的末尾
算法步骤：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

复杂度： 时间复杂度O(n^2), 空间复杂度O(1)，排序时间与输入无关，最好，最差，平均都是O(n^2)
稳定性： 稳定，相同元素经过排序后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

改进：在排序过程中，执行完当前的第i趟排序后，可能数据已全部排序完备，但是程序无法判断是否完成排序，会继续执行剩下的(n-1-i)趟排序。
解决方法：设置一个flag位, 如果一趟无元素交换，则 flag = 0; 以后再也不进入第二层循环。

    // select sort
    public static void selectSort(int [] a) {
        int i, j, min;
        int temp;

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

            for (j = i+1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }

            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

    // bubble sort O(N*N)
    public static void bubbleSort(int [] a) {
        int i, j;
        int temp;

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

1.4 归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法步骤：

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针达到序列尾
• 将另一序列剩下的所有元素直接复制到合并序列尾

复杂度： 时间复杂度 O(nlogn), 空间复杂度O(n) +O(logn)
稳定性： 稳定，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。

    // Merger sort
    public static void mergeSort(int [] a) {
        int [] tempArray = new int [a.length];

        mergeSort(a, tempArray, 0, a.length-1);
    }

    public static void mergeSort(int [] a, int [] tempArray, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(a, tempArray, left, center);
            mergeSort(a, tempArray, center+1, right);
            merge(a, tempArray, left, center+1, right);
        }
    }

    public static void merge(int [] a, int [] tempArray, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int tempPos = leftPos;
        int elementNum = rightEnd - leftPos + 1;

        // Main loop
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (a[leftPos] < a[rightPos])
                tempArray[tempPos++] = a[leftPos++];
            else
                tempArray[tempPos++] = a[rightPos++];
        }

        while (leftPos <= leftEnd)
            tempArray[tempPos++] = a[leftPos++];

        while (rightPos <= rightEnd)
            tempArray[tempPos++] = a[rightPos++];

        // Copy tempArray back
        for (int i = 0; i < elementNum; i++, rightEnd--)
            a[rightEnd] = tempArray[rightEnd];
    }

1.5 快速排序

在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤：

• 从数列中挑出一个元素，称为 “基准”(pivot).
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
• 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

复杂度： 时间复杂度 O(nlogn) 空间复杂度O（logn）
稳定性： 快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻，可能会打乱稳定性

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

    private static int median3(int [] a, int left, int right) {
        int center = (left + right) / 2;

        if (a[center] < a[left])
            swap(a, left, center);

        if (a[right] < a[left])
            swap(a, left, right);

        if (a[right] < a[center])
            swap(a, center, right);

        // Place pivot at position right-1
        swap(a, center, right-1);

        return a[right-1];
    }

    public static void swap(int [] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void quickSort(int [] a, int left, int right) {
        if (left < right) {
            int pivot = median3(a, left, right);

            int i = left, j = right - 1;
            while (i < j) {
                while (a[++i] < pivot);
                while (a[--j] > pivot);

                if (i < j)
                    swap(a, i, j);
                else
                    break;
            }

            swap(a, i, right-1);

            quickSort(a, left, i-1);
            quickSort(a, i+1, right);
        }
    }

1.6 堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序的平均时间复杂度为Ο(nlogn)。

算法过程分为两个步骤：
第一步，以线性时间建立一个Max堆，时间花费O(N)；
第二步，通过将堆中的最后一个元素与第一个元素交换，缩减堆的大小并进行下滤，来执行N-1次DeleteMax操作，当算法终止时，数组则以所排的顺序包含这些元素。由于每个DeleteMin花费时间O(logN)，因此总的运行时间是O(NlogN)。

复杂度： 时间复杂度 O(nlogn) 空间复杂度O(1)
稳定性： 不稳定，发生在下滤的过程中

    private static int leftChild(int i) {
        return 2*i + 1;
    }

    private static void percDown(int [] a, int i, int n) {
        int child;
        int temp;

        for (temp = a[i]; leftChild(i) < n; i = child) {
            child = leftChild(i);

            // Find the larger child
            if (child+1 < n && a[child] < a[child+1])
                child++;

            // if temp is less than the child, then the percolate will be done
            if (temp < a[child])
                a[i] = a[child];
            else
                break;
        }

        a[i] = temp;
    }
    
    private static void heapSort(int [] a) {
        // 从最后一个有叶子结点的结点开始下滤调整，建立一个Max堆
        for (int i = a.length/2 - 1; i >= 0; i--)
            percDown(a, i, a.length);

        for (int i = a.length-1; i > 0; i--) {
            // 将最大元素放到最后
            swap(a, 0, i);
            // 调整root结点的位置，进行下滤
            percDown(a, 0, i);
        }
    }

1.7 桶排序

算法思想： 是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。

1. 桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。
2. 然后基于某种映射函数F, 将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。
3. 接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]....B[M] 中的全部内容即是一个有序序列。

性能分析： 平均时间复杂度为线性的 O(n+C) 最优情形下，桶排序的时间复杂度为O(n)。桶排序的空间复杂度通常是比较高的，额外开销为O(n+m)（因为要维护 M 个数组的引用）。

对 N 个关键字进行桶排序的时间复杂度分为两个部分：
(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是 O(n)。
(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为 ∑ O(ni*logni) 。其中 ni 为第 i个桶的数据量。

很显然，第 (2) 部分是桶排序性能好坏的决定因素。这就是一个时间代价和空间代价的权衡问题了。

1.8 基数排序

假设我们有一些二元组(a,b)，要对它们进行以a 为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为 MSD(Most Significant Dight) 排序。

第二种方式是从最低有效关键字开始排序，称为 LSD(Least Significant Dight)排序 。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD 方法往往比 MSD 简单而开销小。下文介绍的方法全部是基于 LSD 的。

通常，基数排序要用到计数排序或者桶排序。使用计数排序时，需要的是Order数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。

复杂度： 时间复杂度O(n)(实际上是O(d(n+k)) d是位数，O(n+k)为每次桶排序的复杂度)

1.8 总结

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

关于时间复杂度：

1. 平方阶(O(n^2))排序
   各类简单排序:直接插入、直接选择和冒泡排序;
2. 线性对数阶(O(nlog2n))排序
   快速排序、堆排序和归并排序;
3. O(n^(1+§))排序,§是介于0和1之间的常数。
   希尔排序
4. 线性阶(O(n))排序
   基数排序，此外还有桶、箱排序。
5. 关于稳定性：
   稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序
   不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

---

更多面试技巧，深度好文，欢迎关注『后端精进之路』，立刻获取最新文章和面试合集资料。