本篇文章总结一下各种常见的排序算法，并对各种算法的原理、复杂度、稳定性等性质进行分析；最后我们看一下这些算法在实际生产中的应用

文章目录

• 1. 选择排序
• 2. 堆排序
• 3. 插入排序
• 4. 希尔排序
• 5. 冒泡排序
• 6. 快速排序
• 7. 归并排序
• 8. 计数排序
• 9. 桶排序
• 10. 基数排序
• 11. 小结
• 12. 排序算法的实际应用

1. 选择排序

【算法思想】
选择排序算法的思路很简单，假设数组的长度是 N ( N > = 0 ) N(N>=0) N(N>=0)，选择排序算法需要执行 N − 1 N-1 N−1趟：

• 第一趟：在array[ 0 ] … array[ N-1 ] 中找到一个最大的数，把它和array[ N-1 ]交换；
• 第二趟：在array[ 0 ] … array[ N-2 ] 中找到一个最大的数，把它和array[ N-2 ]交换；
• …
• 第N-1趟：在array[ 0 ] … array[ 1 ] 中找到一个最大的数，把它和array[ 1 ]交换；

经过 N − 1 N-1 N−1趟的操作后，对于任何array[index] ( 1 < = i n d e x < = N − 2 1<=index<=N-2 1<=index<=N−2)，都有

• a r r a y [ i n d e x ] < = a r r a y [ i n d e x + 1 ] array[index] <= array[index+1] array[index]<=array[index+1]成立，这是因为 a r r a y [ i n d e x + 1 ] array[index+1] array[index+1]是 a r r a y [ 0 ] . . . a r r a y [ i n d e x + 1 ] array[ 0 ] ... array[ index+1 ] array[0]...array[index+1]中的最大值；
• a r r a y [ i n d e x − 1 ] < = a r r a y [ i n d e x ] array[index-1] <= array[index] array[index−1]<=array[index]成立，这是因为 a r r a y [ i n d e x ] array[index] array[index] 是 a r r a y [ 0 ] . . . a r r a y [ i n d e x ] array[ 0 ] ... array[ index ] array[0]...array[index] 中的最大值；
• 特别的，当index是 N − 2 N-2 N−2时，有 a r r a y [ N − 2 ] < = a r r a y [ N − 1 ] array[N-2] <= array[N-1] array[N−2]<=array[N−1]；

对于0，有 a r r a y [ 0 ] < = a r r a y [ 1 ] array[0]<=array[1] array[0]<=array[1]成立（因为 a r r a y [ 1 ] array[1] array[1] 是 a r r a y [ 0 ] . . . a r r a y [ 1 ] array[ 0 ] ... array[ 1 ] array[0]...array[1] 中的最大值），因此整个数组有序。

【实现代码】

    public void insertionSort(int[] array){
        if(array==null || array.length<=1)return;
        int n = array.length, i ,j ,maxIndex;
        //选择排序需要依次找到最大的，第二大的，。。。第n-1大的 分别放在索引n-1,n-2 ... 1处
        //我们依次枚举这些索引，找到最大的元素放进去就可以了
        for(i = n-1; i>0; --i){
            //从0 到 i中 找一个最大的放到i的位置上，默认认为0号元素是最大的，然后循环中不断更新它
            maxIndex = 0;
            for(j=1; j<=i; ++j)
                if(array[maxIndex]<array[j])maxIndex = j;
            if(maxIndex != i && array[maxIndex] != array[i]) swap(array,maxIndex,i);
        }

    }

    public void swap(int[] array,int i,int j){
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

gif展示，虽然图上每次选的是最小的，但是不影响

【时间复杂度】
需要执行 N − 1 N-1 N−1趟，第一趟需要比较 N − 1 N-1 N−1次，第一趟需要比较 N − 2 N-2 N−2次，… 最后一趟需要比较1次，因此总的比较次数：
s u m = ∑ i = 1 N − 1 i = N ( N − 1 ) 2 sum = \sum_{i=1}^{N-1}{i} = \frac{N(N-1)}{2} sum=i=1∑N−1​i=2N(N−1)​
因此时间复杂度 O ( N 2 ) O(N^2) O(N2)。

其实很多数组在排序之前，都是部分有序的，但是插入排序没有利用到数组部分有序，因此任何情况下，时间复杂度都是 O ( N 2 ) O(N^2) O(N2)。

【空间复杂度】

O ( 1 ) O(1) O(1)

【稳定性】

排序算法的稳定性概念：如果某个排序算法，不影响相同的记录在排序之前的相对顺序，那么这个排序算法就是稳定的，否则不稳定。

它的意思是说，例如在排序之前，数组是这样的 [1, 3, 2, 4, 5A, 7, 9, 5B, 20]
(数组有两个5，分别使用5A和5B区分)，从小到大排序之后，要保证5A出现在5B前面， 即：[1, 2, 3, 4, 5A, 5B, 7, 9, 20]， 而不是：[1, 2, 3, 4, 5B, 5A, 7, 9, 20]。

上面的概念应该好理解，但是稳定性的有什么意义呢？

1. 基数排序 基数排序的思想这里先简单提一下，它的思想大概是(暂且考虑两位整数的排序)，先排序个位数，然后在排序十位数，如果个位数排序好了，在排序十位数的时候，就需要使用稳定的排序算法，才可以得到正确的结果。例如有四个数，15，16，17， 18，十位数都是1，如果使用不稳定的排序算法对十位数进行排序，可能就会使得15跑到16后面，而稳定的排序算法就会在关键字相同时，保留原有的顺序。

2. 复杂对象的多重排序 例如有很多商品对象，里面有价格(price)和销量(amount)字段，如果最初的顺序是按照价格从小到大排序的，即最初的顺序是有意义的，那现在要求对这个商品序列按照销量从小到大排序，既然原来的顺序是有意义的，那么当销量相同时，就不应该更改原来的价格顺序，即要保证价格还是从小到大的，这时就需要使用到稳定的排序算法。

假设在某一趟的排序中，在 a r r a y [ 0 ] . . . a r r a y [ i ] , 1 < = i < = N − 1 array[ 0 ] ... array[ i ], 1<=i<=N-1 array[0]...array[i],1<=i<=N−1，中找到了一个最大的值所在的索引是maxIndex，此时需要把 a r r a y [ m a x I n d e x ] array[ maxIndex ] array[maxIndex]和 a r r a y [ i ] array[ i ] array[i]进行交换，如果在maxIndex和i之间存在一个索引j，并且 a r r a y [ j ] = = a r r a y [ i ] array[ j ] == array[ i ] array[j]==array[i]，则交换之后， a r r a y [ i ] array[ i ] array[i]就会出现在 a r r a y [ j ] array[ j ] array[j]的前面。

例如：数组 {1, 8, 4, 6, 2, 3, 2}
第一轮肯定要把8(红色)和2(绿色)进行交换，在8和最后一个数之间还有一个2(黄色)，这样交换以后，就会导致绿色的2排到黄色的2之前。
{1, 2, 4, 6, 2, 3, 8}

所以选择排序不稳定。

选择排序的思想是每一趟都从一个范围中找到一个最大的，然后放在指定位置来实现的，寻找最大值的过程是采用逐个比较的方法，时间复杂度是线性的，有没有一种办法能加快这个过程呢？有的，下面我们来看堆排序。

2. 堆排序

【铺垫】
讲堆排序之前，先说一下堆数据结构。(如果有已经知道了堆的大佬，请跳过。)，在说堆之前，先说两个特殊的二叉树：

• 满二叉树
  顾名思义，树上结点满了的二叉树；准确来说，一个有 k , k > = 1 k,k>=1 k,k>=1层且有 2 k − 1 2^k -1 2k−1个结点的二叉树（实际上，有k层，最多只有 2 k − 1 2^k -1 2k−1个结点）

• 完全二叉树
  对二叉树从1开始，自上而下，自左而右的依次编号，如果某一个二叉树它的编号依次可以和满二叉树一一对应，那么这个二叉树就是完全二叉树

因此满二叉树是一个特殊的完全二叉树。

堆就是一颗完全二叉树，因为完全二叉树结构很规整，可以直接用数组存储，所以堆又叫数组存储的二叉树。堆在数组中存储的方式，还是按照上面的编号顺序，依次存放到数组的0，1，2…N-1的位置上。

设堆的结点个数为N，数组索引范围[0，N-1]，有关堆存储的几点性质：

• 对于任意一个结点，其索引 i i i，其父节点索引(如果有的话) p p p，左孩子索引(如果有的话) l l l，右孩子索引(如果有的话) r r r，且 i , p , l , r ∈ [ 0 , N − 1 ] i,p,l,r\in[0,N-1] i,p,l,r∈[0,N−1]那么有
  p = ⌊ i − 1 2 ⌋ l = 2 i + 1 r = l + 1 p=\lfloor\frac{i-1}{2}\rfloor\\ l = 2i+1\\ r = l+1 p=⌊2i−1​⌋l=2i+1r=l+1成立
• 堆的层数 L = ⌈ log ⁡ 2 ( N + 1 ) ⌉ L = \lceil\log_{2}{(N+1)}\rceil L=⌈log2​(N+1)⌉
• 叶子结点的索引范围： [ N 2 , N − 1 ] [\frac{N}{2},N-1] [2N​,N−1]

上面三条结论的简单证明，如果不感兴趣可以跳过：

对于第一个结论，只需要证明 l = 2 i + 1 l = 2i+1 l=2i+1即可。对于满二叉树，它每一层的节点数是 L ( h ) = 2 h − 1 , h ∈ [ 1 , + ∞ ) L(h) = 2^{h-1},h\in[1,+\infty) L(h)=2h−1,h∈[1,+∞)，每层节点数成等比数列，前N层的节点数之和： S ( N ) = ∑ i = 1 N 2 i − 1 = 2 N − 1 （ 运 用 等 比 数 列 求 和 ） S(N) = \sum_{i=1}^{N}{2^{i-1}} = 2^{N}-1（运用等比数列求和） S(N)=∑i=1N​2i−1=2N−1（运用等比数列求和），可以得到 S ( N ) S(N) S(N)只是比第N+1层的节点数 2 N + 1 − 1 = 2 N 2^{N+1-1}=2^{N} 2N+1−1=2N少了1，所以 S ( N ) = L ( N + 1 ) − 1 S(N) = L(N+1)-1 S(N)=L(N+1)−1，也就是说，某一层的节点数等于前面所有层的节点数+1。因为索引从0开始，所以每个元素的索引表示它前面的所有元素的个数。我们只需要知道在编号为 i i i的结点的左孩子前面，还有几个元素即可。设索引为 i i i的结点所在的层编号是 h h h，这一层第一个结点的索引为 k k k，且令 o f f s e t = i − k offset = i-k offset=i−k，表示在第h层，在i之前还有offset个结点。那么前h层，一共有 k + ( k + 1 ) = 2 k + 1 k+(k+1)=2k+1 k+(k+1)=2k+1个结点，i的左孩子一定在h+1层，那个它距离h+1层第一个结点的偏移是 2 o f f s e t = 2 i − 2 k 2offset = 2i-2k 2offset=2i−2k，那么在l之前一共有 2 k + 1 + 2 i − 2 k = 2 i + 1 2k+1+2i-2k=2i+1 2k+1+2i−2k=2i+1个结点，即l的索引是 2 i + 1 2i+1 2i+1。

第二个结论，层数为h的满二叉树的结点总数为 2 h − 1 2^{h}-1 2h−1，如果堆是一个满二叉树，结点个数为 N N N，那么层数显然是整数，即 log ⁡ 2 ( N + 1 ) \log_{2}{(N+1)} log2​(N+1)，否则，堆的最后一层没有排满，但是也占据一层，所以层数是小数，但是大于 log ⁡ 2 ( N + 1 ) \log_{2}{(N+1)} log2​(N+1)，所以取 ⌈ log ⁡ 2 ( N + 1 ) ⌉ \lceil\log_{2}{(N+1)}\rceil ⌈log2​(N+1)⌉。

第三个结论 设最后一个具有子结点的索引是k，如果：

• N是偶数，则N-1是奇数，由于右孩子的索引是 2 i + 2 2i+2 2i+2是偶数，所以最后一个具有子结点的结点，没有右孩子，只有左孩子，那么其左子结点索引 2 k + 1 2k+1 2k+1，则 2 k + 1 < N = > k < = ⌊ N − 1 2 ⌋ 2k+1<N=>k<=\lfloor\frac{N-1}{2}\rfloor 2k+1<N=>k<=⌊2N−1​⌋，剩下的都是叶子结点，叶子节点的索引范围 [ ⌊ N − 1 2 ⌋ + 1 , N − 1 ] [\lfloor\frac{N-1}{2}\rfloor+1,N-1] [⌊2N−1​⌋+1,N−1]，由于N是偶数， ⌊ N − 1 2 ⌋ + 1 = N 2 \lfloor\frac{N-1}{2}\rfloor+1 = \frac{N}{2} ⌊2N−1​⌋+1=2N​，即叶子节点的索引范围 [ N 2 , N − 1 ] [\frac{N}{2},N-1] [2N​,N−1]。
• N是奇数，则N-1是偶数，则最后一个具有子结点的结点有右孩子，即 2 k + 2 < N = > k < N − 2 2 = > k < = ⌊ N 2 ⌋ − 1 2k+2<N=>k<\frac{N-2}{2}=>k<=\lfloor\frac{N}{2}\rfloor-1 2k+2<N=>k<2N−2​=>k<=⌊2N​⌋−1，即叶子节点的索引范围 [ ⌊ N 2 ⌋ , N − 1 ] [\lfloor\frac{N}{2}\rfloor,N-1] [⌊2N​⌋,N−1].

当N是奇数时， ⌊ N 2 ⌋ = N 2 \lfloor\frac{N}{2}\rfloor=\frac{N}{2} ⌊2N​⌋=2N​，综上，叶子结点的范围 [ N 2 , N − 1 ] [\frac{N}{2},N-1] [2N​,N−1]；可以看出几乎一半都是叶子结点。

最大堆：设堆结点个数 N ∈ [ 1 , + ∞ ) , N \in [1, +\infty), N∈[1,+∞),对任何一个结点的索引 i ∈ [ 0 , N − 1 ] i \in [0, N-1] i∈[0,N−1]，其父节点索引(如果存在的话) p ( i ) p(i) p(i)，有 a r r a y [ i ] < = a r r a y [ p ( i ) ] array[i]<=array[p(i)] array[i]<=array[p(i)]成立

最小堆：设堆结点个数 N ∈ [ 1 , + ∞ ) , N \in [1, +\infty), N∈[1,+∞),对任何一个结点的索引 i ∈ [ 0 , N − 1 ] i \in [0, N-1] i∈[0,N−1]，其父节点索引(如果存在的话) p ( i ) p(i) p(i)，有 a r r a y [ i ] > = a r r a y [ p ( i ) ] array[i]>=array[p(i)] array[i]>=array[p(i)]成立

显然一个排序的数组就是一个最大堆/最小堆，反之不真。

对于一个最大堆来说，堆顶的元素就是最大的元素，最小堆亦然。下面我们以最大堆为例，说明堆的操作，假设堆的元素个数 N N N。

1. 如何把一个数组整理成最大堆？上浮(shift_up)和下沉(shift_down)操作
   对于任何一个元素，如果其值大于其父元素，根据大顶堆的定义，此时应该把当前元素和其父元素交换，然后再考查其父元素是不是大于其父元素的父元素；否则结束，这个操作称为元素上浮，代码如下：
   

    /**
     * 把索引为shiftUpIndex的堆元素上浮
     * @param heap 存储堆的数组
     * @param N 堆元素个数
     * @param shiftUpIndex 等待上浮的元素索引
     */
    public void shiftUp(int[] heap, int N, int shiftUpIndex) {
        //边界校验
        if (shiftUpIndex >= N) return;
        //暂存等待上浮的元素的值
        int t = heap[shiftUpIndex], parentIndex;
        
        //只要等待上浮的元素索引大于0（因为索引为0的元素是堆顶了，没法上浮） 就不断考察其父元素和当前元素的大小关系
        while (shiftUpIndex > 0) {
            parentIndex = (shiftUpIndex - 1) >> 1;
            //对于最大堆来说，如果父元素小于子元素，则子元素上浮，把父元素的值赋值给子元素
            if (heap[parentIndex] < t) {
                heap[shiftUpIndex] = heap[parentIndex];
                //更新等待上浮元素的索引
                shiftUpIndex = parentIndex;
            } else {
                //否则上浮结束
                break;
            }
        }
        heap[shiftUpIndex] = t;
    }
   

   
   对于任何一个元素，如果其值小于其某个元素，根据大顶堆的定义，此时应该把当前元素和其两个子元素中最大的那个元素交换，然后再考查被交换的子元素是不是小于它的某个子元素；否则结束，这个操作称为元素下沉
   

   /**
   * 把索引为shiftUpIndex的堆元素下沉
   * @param heap 存储堆的数组
   * @param N 堆元素个数
   * @param shiftDownIndex 等待下沉的元素索引
   */
   public void shiftDown(int[] heap, int N, int shiftDownIndex) {
      //边界校验 对于索引大于等于N/2的元素，是叶子结点，叶子结点不需要下沉
      int leafBound = N >> 1;
      if (shiftDownIndex >= leafBound || shiftDownIndex < 0) return;
      //暂存等待下沉的元素的值
      int t = heap[shiftDownIndex], childIndex;
   
      //只要等待下沉的元素索引小于叶子元素的索引边界（因为超过叶子元素的索引边界的元素就是叶子元素了，没法下沉） 就不断考察其最大的子元素和当前元素的大小关系
      while (shiftDownIndex < leafBound) {
          childIndex = (shiftDownIndex << 1) + 1;
          if(childIndex + 1 < N && heap[childIndex + 1] > heap[childIndex])childIndex++;
          //对于最大堆来说，如果子元素大于当前元素，则当前元素下沉，把子元素的值赋值给当前元素
          if (heap[childIndex] > t) {
              heap[shiftDownIndex] = heap[childIndex];
              //更新等待下沉元素的索引
              shiftDownIndex = childIndex;
          } else {
              //否则下沉结束
              break;
          }
      }
      heap[shiftDownIndex] = t;
   }
   

   上浮和下沉时间复杂度：这个与元素所在堆的层次有关
   最好情况下，元素是在倒数第二层，最多只需要进行一次比较即可，是 O ( 1 ) O(1) O(1)，
   最坏情况下，元素是在第一层(堆顶)，最多需要比较 堆的层数-1 次，根据上面的结论2，即 ⌈ log ⁡ 2 ( N + 1 ) ⌉ − 1 = O ( log ⁡ 2 N ) \lceil\log_{2}{(N+1)}\rceil-1 = O(\log_{2}{N}) ⌈log2​(N+1)⌉−1=O(log2​N)；
   假设元素在第 l ∈ [ 1 , ⌈ log ⁡ 2 ( N + 1 ) ⌉ ] l\in[1,\lceil\log_{2}{(N+1)}\rceil] l∈[1,⌈log2​(N+1)⌉]层，最多需要比较 堆的层数-l次。
   
   空间复杂度： O ( 1 ) O(1) O(1)；
   
   当一个元素上浮时，就有一个元素下沉，上浮和下沉是相对的。
   
   如何把一个数组整理成一个最大堆呢？可以使用上浮，也可以下沉，这里使用下沉举例，因为叶子结点是不需要下沉的，所以根据最大堆的要求，把所有的非叶子结点都下沉操作一遍即可。代码如下：

   /**
    * 把数组调整成最大堆
    * @param heap 调整之前的数组
    * @param N 堆元素个数
    */
   public void adjustHeap(int[] heap, int N){
       if(N <= 1)return;
       // N/2-1 是最后一个非叶子结点的索引
       for(int i = (N>>1)-1; i>=0; --i)
           shiftDown(heap, N, i);
   }
   

   时间复杂度，最好 O ( N ) O(N) O(N)，最坏情况下：也是 O ( N ) O(N) O(N)。

   最坏情形证明如下：设堆层数 L L L，第 i ∈ [ 1 , L ] i\in[1, L] i∈[1,L]层的元素最多需要比较的次数是 L − i L-i L−i，第 i i i层的元素个数最多是 2 i − 1 2^{i-1} 2i−1，所以所有的非叶子结点下沉最多需要比较次数 S = ∑ i = 1 L − 1 2 i − 1 ( L − i ) S=\sum_{i=1}^{L-1}{2^{i-1}(L-i)} S=∑i=1L−1​2i−1(L−i)，代入 L = log ⁡ 2 ( N + 1 ) L =\log_{2}{(N+1)} L=log2​(N+1)，整理得到 S = N + 1 − log ⁡ 2 N + 1 − 1 S=N+1-\log_2{N+1}-1 S=N+1−log2​N+1−1，因此时间复杂度 O ( N ) O(N) O(N)

   
   空间复杂度： O ( 1 ) O(1) O(1)。

2. 向堆末尾添加元素
   向堆中添加元素，一般都是添加在末尾，然后把最后的这个结点上浮即可。

   /**
    * 向堆中添加元素
    * @param heap 存储堆的数组
    * @param N 堆中的元素个数
    * @param node 新加入的结点
    */
   public void heapInsertion(int[] heap, int N, int node){
       if(N==heap.length)
           throw new UnsupportedOperationException("堆数组已满");
       heap[N] = node;
       shiftUp(heap,N+1,N);
   }
   

   平均时间复杂度 O ( log ⁡ 2 N ) O(\log_{2}{N}) O(log2​N)

3. 移除堆顶元素
   移除的方法是，把堆顶元素和最后一个元素交换，然后堆元素个数减一，最后让新的堆顶元素下沉。

   /**
    * 移除堆顶元素
    * @param heap 保存堆的数组
    * @param N 堆中的元素个数
    * @return 堆顶元素
    */
   public int pop(int[] heap, int N){
       //把最后一个元素赋值给堆顶，返回原堆顶
       //最后下沉新的堆顶元素，调整堆
       int ans = heap[0];
       heap[0] = heap[N-1];
       shiftDown(heap,N-1,0);
       return ans;
   }
   

   平均时间复杂度 O ( log ⁡ 2 N ) O(\log_{2}{N}) O(log2​N)

前面说了这么多，大概介绍了一下堆是什么以及操作，其实堆的操作不只这几个，这里只是介绍了堆排序需要用到的，下面我们看一下堆排序的思想：

【算法思想】
我们只需要把一个待排序的数组整理成最大堆，然后不断pop即可（没错，就这么简单