【数据结构】八大排序

排序

排序是一种非常重要的根本算法，在校招和工作中都非常的实用，它在日常生存中无处不在。本章将先容八大根本排序。
所谓排序，就是将一串序列按照某种递增递减的关系，使该序列成为一个有序的序列。常见并实用的排序有如下八种。

 
1 插入排序

1.1 直接插入排序

根本思想

直接插入排序是最简朴的插入排序，例如摸扑克牌时，必要将摸到的牌按顺序插入到已有的牌中，这里便运用了直接插排的思想。
插入排序的界说：把待排的元素按规则逐个插入到一个有序序列中，直到全部元素插完为止，得到一个新的有序序列。

代码实现

首先有一个有序数组，此外有一个元素待插入到该数组中。

• 只要当前元素大于待插元素，就将当前元素向后移动一位，
  
• 直到当前元素比待插元素小或相称大概下标越界，然后退出循环，
  
• 将待插元素插入当前下标位置的下一个位置。
  

1. //1. 单趟排序 -- 针对一个元素的排序
2. void InsertSort(int* a, int n)
3. {
4.         int end = n - 2;
5.         int x = a[end + 1];
6.    
7.         while (end >= 0)
8.     {
9.                 if (a[end] > x)
10.                         a[end + 1] = a[end];
11.                 else
12.                         break;
13.         
14.         end--;
15.         }
16.         a[end + 1] = x;
17. }

复制代码

  如上是直接插入排序的单趟排序，一次只能让一个元素有序。排序是让序列中全部元素都有序，也就是要调用多次单趟排序，使全部元素有序。
  所以排序一般分为内外两层循环，内循环调整当前待插元素位置，而外循环决定调整待插元素。
最开始                                    e                         n                         d                         =                         0                              end=0                  end=0，也就是不存在已排好的数据，

• 将数组的尾部元素                                         e                            n                            d                                  end                     end 的下一个元素当作待插元素                                         x                                  x                     x ，再将待插元素运用单趟排序插入数组中。
  
• 将数组尾部下标                                         e                            n                            d                                  end                     end 向后挪一位，重复上述过程。
  
• 以此类推，直到                                         e                            n                            d                                  end                     end 指向整个数组的尾部，整个数组就都有序。
  

故只要加一个外循环，控制标识尾部指针                                         e                            n                            d                                  end                     end 遍历为                                         [                            0                            ,                            n                            −                            1                            )                                  [0,n-1)                     [0,n−1)，这样便能完成对整个数组的排序。

1. void InsertSort(int* a, int n)
2. {
3.     //外循环 - 多趟排序
4.         for (int i = 0; i < n - 1; i++)
5.     {
6.                 int end = i;
7.                 int x = a[end + 1];
8.         //内循环 - 单趟排序
9.                 while (end >= 0)
10.         {
11.                         if (a[end] > x)
12.             {
13.                                 a[end + 1] = a[end];
14.                                 end--;
15.                         }
16.                         else
17.                                 break;
18.                 }
19.                 a[end + 1] = x;
20.         }
21. }

复制代码

复杂度分析

• 最好环境为数组有序或接近有序，但仍需遍历一遍，时间复杂度为                                        O                            (                            n                            )                                  O(n)                     O(n)，
  
• 最坏环境为数组逆序，全部元素都要调整，时间复杂度为                                        O                            (                                       n                               2                                      )                                  O(n^2)                     O(n2) 。
  

   外循环循环                                         n                                  n                     n 次，内循环次数从1开始逐次增加。故总循环次数为等差数列之和                                         1                            +                            2                            +                            …                            +                            n                            −                            1                                  1+2+…+n-1                     1+2+…+n−1。
  无额外空间斲丧，空间复杂度为                                    O                         (                         1                         )                              O(1)                  O(1) 。
   直接插排对于数组接近有序的环境非常的快，而在数组完全逆序的环境下表现非常慢。
   
1.2 希尔排序

直接插排在数据不接近有序的环境下表现的不尽人意。故Shell想出在直接插排的前面举行预排序，使得数据接近有序，这样直接插排的性能就得到优化，这就是希尔排序。
分组预排

先预排序数组，使数组变得接近有序（大的尽量在背面，小的尽量在前面），此时再去直接插排。
按gap分组，对分组产生的“小数组”，利用直接插入排序。

• 假设 gap 为5，则每五个元素分成一组，将一组的元素当作一个数组，忽略数组中其他元素。
  

代码实现

1. void shell_sort(int* a , int n)
2. {
3.     int gap = n;
4.     while (gap > 0) // gap不断减小分组预排多次
5.     {
6.             //gap/=2；
7.         gap = gap / 3 + 1; // 保证最后一定gap=1执行最后一次直接插排
9.         for (int j = 0; j < gap; j++)
10.         {
11.             for (int i = j; i < n - gap; i += gap)
12.             {
13.                 int end = i;
14.                 int x = a[end + gap];
16.                 while (end >= j)
17.                 {
18.                     if (a[end] > x)
19.                         a[end + gap] = a[end];
20.                     else
21.                         break;
23.                     end -= gap;
24.                 }
26.                 a[end + gap] = x;
27.             }
28.         }
29.     }
30. }

复制代码

  对于预排序来说，gap越大，结果越差，但时间斲丧越小；而gap越小，结果越好，但时间斲丧就越大。
  由于直接插排的复杂度特点，可能渐渐减小的希排复杂度比一次直接插排的复杂度更低。故实验多次预排来优化预排结果。控制 gap 不绝减小到1，最后 gap==1 时实验最后的直接插排。
简化版本

1. void ShellSort(int* a, int n)
2. {
3.         int gap = n;
4.         while (gap > 0)
5.     {
6.                 gap = gap / 3 + 1;
7.         
8.                 for (int i = 0; i < n - gap; i++)
9.         {
10.                         int end = i;
11.                         int x = a[end + gap];
12.                         while (end >= 0)
13.             {
14.                                 if (a[end] > x)
15.                                         a[end + gap] = a[end];
16.                                 else
17.                                         break;
18.                
19.                 end -= gap;
20.                         }
21.             
22.                         a[end + gap] = x;
23.                 }
24.         }
25. }

复制代码

简化了控制多组的循环，原来是一组一组排，酿成了多组一起排。
复杂度分析

   希排的时间复杂度分析较为复杂，下面简朴推理一
  多组预排，最好环境下仅遍历一遍数组，时间复杂度为                                   O                         (                         n                         )                              O(n)                  O(n)。
在控制多组预排的循环中，若gap/=2，大概预排                                    l                         o                                   g                            2                                  n                              log_2n                  log2​n 次；若gap=gap/3+1，大概预排                                    l                         o                                   g                            3                                  n                              log_3n                  log3​n 次。
每次预排的gap不绝的变化，导致复杂度较难计算，研究表明希排的复杂度为                                         O                            (                            n                            l                            o                            g                            n                            )                                  O(nlogn)                     O(nlogn)，大概为                                         O                            (                                       n                               1.3                                      )                                  O(n^{1.3})                     O(n1.3)。
   虽然希尔排序用的都是直接插入排序，但希尔排序的精华在于其思想非常的难得，这使得排序的复杂度得到质的优化。
   
2 选择排序

选择排序是每次选出一个最值，将其放到固定的位置上。而“怎样选”就是直接选排和堆排的区别了。
2.1 直接选择排序

   选择排序是全部排序中最简朴的排序之一。
  根本思想

• 遍历一遍，选出规定范围内的最大值和最小值，
  
• 将最大值和范围末尾元素交换，将最小值和范围起始元素交换，
  
• 将起始和末尾的位置“排除”出数组，进一步缩小范围。
  

再重复上述步调直到选完为止。

代码实现

简朴版：一次找一个极值。

1. void SelectSort(int* a, int n)
2. {
3.     int end = n - 1;
4.         while (end > 0)
5.     {
6.                 int max_i = 0;
7.                 for (int i = 0; i <= end; i++)
8.         {
9.                         if (a[i] > a[max_i])
10.                                 max_i = i;
11.                 }
12.                 Swap(&a[max_i], &a[end]);
13.                 end--;
14.         }
15. }

复制代码

提拔版：一次找两个极值。

1. //1.
2. void SelectSort(int* a, int n)
3. {
4.         int begin = 0, end = n - 1;
5.         while (begin < end)
6.     {
7.                 int min_i = begin, max_i = begin;
8.         // 找最值
9.                 for (int i = begin; i <= end; i++)
10.         {
11.                         if (a[i] < a[min_i])
12.                                 min_i = i;
13.                         if (a[i] > a[max_i])
14.                                 max_i = i;
15.                 }       
16.         // 交换
17.                 Swap(&a[min_i], &a[begin]);
18.                 if (max_i == begin) // 修正
19.                         max_i = min_i;
20.                 Swap(&a[max_i], &a[end]);
21.         
22.                 ++begin, --end;
23.         }
24. }

复制代码

一次遍历找两个最值的方法在交换时存在隐患，可能存在如下环境：
最大值与尾元素交换时，尾元素可能刚好又是最小值，就导致不测将最小值放到了原本最大值的位置。min_i就失效了，因此要修正min_i为max_i。
复杂度分析

一次找一个最值和找两个最值，二者的复杂度具体算式分别为：
                                                    T                               1                                      (                            n                            )                            =                            n                            +                            n                            −                            1                            +                            .                            .                            .                            +                            0                                                         T                               2                                      (                            n                            )                            =                            n                            +                            n                            −                            2                            +                            n                            −                            4                            +                            .                            .                            .                            +                            0                                  T_1(n)=n+n-1+...+0\quad\quad T_2(n)=n+n-2+n-4+...+0                     T1​(n)=n+n−1+...+0T2​(n)=n+n−2+n−4+...+0
时间复杂度都是                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)，找一个和找两个的优化仅仅在量上优化。
直接选排在最好环境和最坏环境一样，都必要一次不差地将范围内全部元素遍历一遍，故最好环境的时间复杂度仍是                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)。
也就是说，直接选排在任何环境下的复杂度都是                                         O                            (                                       n                               2                                      )                                  O(n^2)                     O(n2)，所以直接选排的结果比直接插排差。
2.2 堆排序

根本思想

堆排序要先对数组建堆再不绝向下调整，建堆时间复杂度为                                    O                         (                         n                         )                              O(n)                  O(n)。排升序建大堆，排降序建小堆。

• 向下调整算法要求结点的左右子树都是堆，故从后往前遍历，从第一个非叶子结点开始向下调整建堆。
  
• 建堆完成后，把堆顶元素和尾元素交换，再向下调整将次大的数调至堆顶，直至调整完数组。
  

   数组首尾元素交换，堆顶的最值就被放在了数组末尾，尾指针减1，再向下调整把次大的数调整到堆顶，再首尾交换，次大的数就放在了倒数第二位置。
  依此类推，直到尾指针指向数组首元素，就排完了整个数组。
  

代码实现

1. void AdjustDown(int* a, int n, int parent)
2. {
3.         int child = parent * 2 + 1;
4.         while (child < n)
5.     {
6.         if (child + 1 < n && a[child + 1] > a[child])
7.                         child++;
8.         
9.                 if (a[child] > a[parent])
10.                         Swap(&a[child], &a[parent]);
11.                 else
12.                         break;
13.         
14.         parent = child;
15.         child = parent * 2 + 1;
16.         }
17. }
18. void HeapSort(int* a, int n)
19. {
20.         //建堆
21.         for (int i = (n - 1 - 1) / 2; i >= 0; i--)
22.                 AdjustDown(a, n, i);
23.    
24.         //堆排序
25.         for (int i = n - 1; i > 0; i--)
26.     {
27.                 Swap(&a[0], &a[i]);
28.                 AdjustDown(a, i, 0);
29.         }
30. }

复制代码

复杂度分析

虽然堆排序也是选择排序，但堆排序利用了堆的性质大幅缩减了比力的次数，到达了                                    O                         (                         n                         l                         o                         g                         n                         )                              O(nlogn)                  O(nlogn)。可见堆排和希排属于同一级别的排序。
 
3 交换排序

交换排序就是通过交换两个元素来修正序列的顺序。快速排序和冒泡排序都是交换排序，区别在于怎样交换这两个元素。
3.1 冒泡排序

根本思想

相邻两数举行比力，满足交换条件就交换。每趟排序将一个最值放到末尾。
   

• 第一趟排序比力前                                              n                               −                               1                                      n-1                        n−1 数，共比力                                              n                               −                               1                                      n-1                        n−1 次，将最大数放到第                                              n                                      n                        n 个位置；
  
• 第二趟排序比力前                                              n                               −                               2                                      n-2                        n−2 数，共比力                                              n                               −                               2                                      n-2                        n−2 次，将次最大数放到第                                              n                               −                               1                                      n-1                        n−1 个位置；
  
• 第                                              i                                      i                        i 趟排序比力前                                              n                               −                               i                                      n-i                        n−i 数，共比力                                              n                               −                               i                                      n-i                        n−i 次，将次最大数放到第                                              n                               −                               i                               +                               1                                      n-i+1                        n−i+1 个位置；
  

  共排序                                    n                         −                         1                              n-1                  n−1 趟，每趟排序比上一趟少比力                                    1                              1                  1 个数，共将                                    n                         −                         1                              n-1                  n−1 个数放到末尾，最后一个自然放到了开头。

代码实现

1. void Bubble_sort(int arr[], int size)
2. {
3.         int j,i,tmp;
4.         for (i = 0; i < size-1;i ++)//size-1是因为不用与自己比较，所以比的数就少一个
5.         {
6.                 int flag = 0;
7.                 for (j = 0; j < size-1 - i; j++)        //size-1-i是因为每一趟就会少一个数比较
8.                 {
9.                         if (arr[j] > arr[j+1])//这是升序排法，前一个数和后一个数比较，如果前数大则与后一个数换位置
10.                         {
11.                                 tmp= arr[j];
12.                                 arr[j] = arr[j+1];
13.                                 arr[j+1] = tmp;
14.                                 flag = 1;
15.                                
16.                         }
17.                 }
18.                 if (flag == 0)                        //如果某一趟没有交换位置，则说明已经排好序，直接退出循环
19.                                 break;       
20.         }
22. }

复制代码

通过加上no_swap的判断条件优化，单趟排序竣事后如果一次交换都没发生，就阐明数组已经有序，就可以停止排序了。
复杂度分析

冒泡排序的时间复杂度为                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2) ，其最好环境即数组顺序有序的环境下，时间复杂度为                                    O                         (                         n                         )                              O(n)                  O(n)。
插排 选排 冒泡比力

首先，直接选排的时间复杂度不绝是都是                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)，所以选择排序的服从是最差的。其次，直接插排和冒泡排序在最坏环境下也都是                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)，所以应对比一下二者的一般环境下的表现：
当数组顺序有序时，直接插排和冒泡都是                                    O                         (                         n                         )                              O(n)                  O(n)。当数组接近有序时，此时二者的原理差异就体现出优劣了：
以 $ 1 \quad2\quad3\quad4\quad6\quad5$ 为例：

• 冒泡排序必要两趟排序，第一趟比力                                         n                            −                            1                                  n-1                     n−1 次将6放到末尾，第二趟比力                                         n                            −                            2                                  n-2                     n−2 次确认完全有序，共比力了                                         n                            −                            1                            +                            n                            −                            2                                  n-1+n-2                     n−1+n−2 次。
  
• 直接插排共排序5趟，前4趟每趟比力1次共4次，第5趟时，5和6、4和5 发生比力，一共比力了                                        n                            −                            2                            +                            2                            =                            n                                  n-2+2=n                     n−2+2=n 次。
  

冒泡排序每趟都要从头开始比力到最终位置，而插入排序只会从无序的部分开始向前比力。冒泡排序是”从后向前排“，插入排序是”从前向后排“。

   从箭头的长度可以看出，冒泡排序每趟排序都是从头遍历到后才完成一趟排序，就算前半部分呈有序状之后每趟同样会再遍历一遍。
  插入排序时从前向后排序，当数组接近有序时每趟排序只会比力2次，之后的排序不会重复遍历之前已排好的有序部分。
  让二者排序一个很长的前半部分有序后半部分无序的数组时二者的区别就体现出来了。
 
3.2 快速排序

快速排序是对冒泡排序的一种改进，在思想上具有巨大进步，是 Hoare 提出的一种整体思绪类似于二叉树结构的一种排序方法，距今大约有60年之久。
根本思想

快速排序的递归思想类似于二叉树结构的遍历。

• 任取待排数组中的某个元素作为关键字key，
  
• 通过一趟排序将该数组分割成两部分，左数组的全部元素均小于该关键值，右数组的全部元素均大于该关键值。
  

这就是一趟排序的流程，再对所得两个子数组分别重复上述过程，直至整个数组有序。
每次单趟排序都让数组整体更有序一些。快速排序的实现必须先理解清楚单趟排序，之后每趟排序都是最初的单趟排序的缩小版。
1. Horae 版本

一般选最左边或最右边的元素作为关键字key。

单趟排序完成后，使数组中比key小的元素在数组的左边，比key大的在数组的右边，最后关键字key也到了最终位置。

单趟排序的作用是将关键字key放到正确位置，趁便整理了一下数组使之更加有序。类似于冒泡排序的将最大值放到尾处的最终位置，都是一趟排序排好一个数。

1. // 递归版本1. Horae 版本
2. int Partition1(int* a, int left, int right)
3. {
4.         int keyi = left;
5.         while (left < right)
6.     {
7.                 while (left < right && a[right] >= a[keyi]) // 右找小
8.                         --right;
9.                 while (left < right && a[left] <= a[keyi])  // 左找大
10.                         ++left;
12.                 Swap(&a[left], &a[right]); // 左右交换
13.         }
14.    
15.         Swap(&a[keyi], &a[left]); // 交换key
16.         return left;
17. }

复制代码

在找左找右的代码中，有两个必须注意的问题，

• 移动下标的循环条件必须加上left<right的条件，防止下标越界，
  
• a[left]<=a[keyi]要加上即是的环境，以免指针遇到与key相称的元素无法移动，造成死循环。
  
• keyi记录key元素的下标而不是值，因为最后交换必要下标。
  

   看到这里，可以先把下面的排序主函数用上，实现完整的快排。跳转到快排主函数
  左右先走问题分析

   当左右下标相遇后的该位置的值要与key交换，但有没有可能左右下标相遇位置的元素比key大，导致这个比key大的数被换到了左边呢？
  不会出现这样的问题，因为在左右指针移动时，有这样的规定：

• 选最左边的值作key时，右边的下标r先走，包管左右相遇时的值比key要小。
  
• 选最右边的值作key时，左边的下标l先走，包管左右相遇时的值比key要大。
  

我们以选最左边作key，右边先走为例表明一下，在左右下标移动的过程中，无非有两种环境：

• 特殊环境：数组中无比key小的数，右下标一次性就到了最左边与左下标相遇。这样key与key举行交换。
  
• 一般环境：数组中心有比key小的数，右下标经历几番妨害才与左下标相遇。
  
  
  
  • 要么最后右到了左的位置，该左下标的值一定已在上一轮交换中被换成比key小的数。
    
  • 要么最后左到了右的位置，此位置的值自然比key小。
    
  
  

只要按照左作key右先走、右作key左先走的规定，就不会堕落。

2. 挖坑法

   挖坑法是针对单趟排序 Hoare 版本的简化变形。
  

   左边挖坑右边填，右边挖坑左边填。
  一样是左边作key右边先走，右边作key左边先走，同样以选最左边作key为例。

• 将最左边的值用临时变量 key 生存起来，形成一个坑位。
  
• 右下标先走，找比 key 小的值，找到放到左边的坑位中，自身又形成了一个坑位。
  
• 左下标再走，找比 key 大的值，找到放到右边的坑位中，自身又形成了一个坑位。
  

以此类推，左右下标相遇后停止循环，再将key中的值放到当前下标所在位置的坑位中，就完成了单趟排序。

1. //2. 挖坑法
2. int Partition2(int* a, int left, int right)
3. {
4.         int key = a[left];
5.         int pivot = left   // 定义坑位
6.         
7.         while (left < right)
8.     {
9.                 while (left < right && a[right] >= key)
10.                         --right;
11.                 a[pivot] = a[right]; // 右下标的值放到左边的坑位中
12.                 pivot = right;
13.                
14.                 while (left < right && a[left] <= key)
15.                         ++left;
16.                 a[pivot] = a[left]; // 左下标的值放到右边的坑位中
17.                 pivot = left;
18.         }
19.    
20.         a[pivot] = key;
21.         return pivot;
22. }

复制代码

  挖坑法更简朴流行，所以一般选择题所遇到的排序问题，默认都观察挖坑法。
  3. 前后指针法

   前后指针版比力难以理解，但是代码比力简朴。涉及到双指针的问题，一般拆开看，思考每个指针的作用，再放到一起看就明了了。
  

• 左边作key，cur起始位置在第2个元素，prev指向cur前1个位置，排序有效区间是第2个元素到尾元素。
  
• 右边作key，cur起始位置在第1个元素，prev指向cur前1个位置，排序有效区间是首元素到倒数第2个元素。
  

• cur向后遍历数组，找比 key 小的元素（升序）。找到后++prev，再交换 cur 和 prev 的元素。
  
• cur遍历完数组后，将 key 与 prev 元素交换。
  

   左边作key时可直接交换，右边作key时先++prev，将大的值交换到右边。
  

由上图可以看出：

• cur的使命就是遍历数组找比key小的值；
  
• prev的使命是紧跟比key大的值，以便举行交换。包管                                         [                            k                            e                            y                            i                            +                            1                            ,                            p                            r                            e                            v                            ]                                  [keyi+1,prev]                     [keyi+1,prev] 的值比                                         a                            [                            k                            e                            y                            i                            ]                                  a[keyi]                     a[keyi] 小，                                         [                            p                            r                            e                            v                            ,                            c                            u                            r                            ]                                  [prev,cur]                     [prev,cur] 的值比                                         a                            [                            k                            e                            y                            i                            ]                                  a[keyi]                     a[keyi] 大。
  

整个过程看起来就是，cur 把比 key 小的数往左放，prev 把比 key 大的数向右推。

1. //左边作key
2. int Partition(int* a, int left, int right)
3. {
4.     int keyi = left;
5.         int cur = left + 1, prev = cur - 1;
6.    
7.         while (cur <= right) // 有效区间
8.     {
9.                 if (a[cur] < a[keyi] && ++prev != cur) // cur找小
10.                         Swap(&a[cur], &a[prev]);
11.                 ++cur;
12.         }
13.    
14.     Swap(&a[keyi], &a[prev]);
15.     return prev;
16. }
18. //右边作key
19. int Partition(int* a, int left, int right)
20. {
21.     int keyi = right;
22.         int cur = left, prev = cur - 1;
23.    
24.     while (cur < right) // 有效区间
25.     {
26.         if (a[cur] < a[keyi] && ++prev != cur) // cur找小
27.             Swap(&a[cur], &a[prev]);
28.         ++cur;
29.     }
30.    
31.     Swap(&a[keyi], &a[++prev]); // 把大的换到右边
32.     return prev;
33. }

复制代码

  前后指针版本可能较难理解，但实现却是最简朴的，一般面试的时间都可以写这种。
  递归版本

单趟排序之后，分出了左右子区间，倘若左右子区间都是有序的，那么整个排序就完成了。
至于左右子区间怎么使其有序，则是再将左右子区间分别视为一个数组，继承对其实验单趟排序。不绝分割直至所得“数组”仅有一个元素时默认排序完成。
这便是整体排序的递归结构，类似于二叉树的前序遍历。

1. void QuickSort(int* a, int left, int right)
2. {
3.     if (left >= right) // 区间只有一个值或区间不存在
4.                 return;
6.         int keyi = Partition1(a, left, right); // 单趟排序
7.         QuickSort(a, left, keyi - 1);          // 递归左区间
8.     QuickSort(a, keyi + 1, right);         // 递归右区间
9. }

复制代码

从上述代码看出，每次排序都将数组分成这样的三部分                                    [                         l                         e                         f                         t                         ,                         k                         e                         y                         −                         1                         ]                              [left, key-1]                  [left,key−1] 和                                    k                         e                         y                              key                  key 和                                    [                         k                         e                         y                         +                         1                         ,                         r                         i                         g                         h                         t                         ]                              [key+1, right]                  [key+1,right]。key 所在位置已经排好序，再对前后两个子区间举行分治，递归调用即可。

复杂度分析

快速排序的时间复杂度和key的选择有很大的关系。如果每次我们都选到整个数组的中位数，也就是最佳环境，此时递归结构如图所示：

• 时间复杂度就是数组长度乘二叉树高度，即                                              n                               ∗                               l                               o                               g                               n                               =                               O                               (                               n                               l                               o                               g                               n                               )                                      n*logn = O(nlogn)                        n∗logn=O(nlogn)。
  
• 因为要建立栈桢，空间复杂度为                                         O                            (                            l                            o                            g                            n                            )                                  O(logn)                     O(logn) 。
  

   固然上述的复杂度建立在每次都选到数组中位数的环境，是最佳环境。
  快排的缺陷和优化

• 如果每次 key 都是整个数组的最值，那么每趟排序就不能使数组整体相对有序，这样复杂度就酿成                                        O                            (                                       n                               2                                      )                                  O(n^2)                     O(n2)。可用三数取中优化。
  
• 递归结构越到底层递归次数越多，而越到底层排序区间越小，这样递归的性价比太低，可用小区间优化解决。
  
• 当数组元素完全相同时，根本快排无法优化要利用三路划分，复杂度为                                        O                            (                                       n                               2                                      )                                  O(n^2)                     O(n2)，应提前避免这种环境。
  

三数取中

快排复杂度非常依赖key的值，最优环境是每次都选到或接近中位数的元素递归后呈现二叉树的结构。
最差环境则是数组顺序有序或接近有序时仍每次选择最左或最右边的最值作为key，如图所示：

这种环境下快排类似于冒泡排序，时间复杂度为                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)。此时若数据量大递归太多还轻易栈溢出。
   那怎样解决快排面对数组有序的选key问题呢？解决方案叫三数取中。
  选出整个数组的最左、最右、中心三者的中心数作key。

1. void GetMidIndex(int* a, int left, int right)
2. {
3.     int midi = left + ((right - left) >> 1);
4.     //取中逻辑
5.     if (a[left] < a[right])   /** left < right **/
6.     {
7.         if (a[midi] < a[left])       //mid < left < right
8.             return left;
9.         else if (a[midi] < a[right]) //left < mid < right
10.             return midi;
11.         else                         //left < right < mid
12.             return right;
13.     }
14.     else                      /** left >= right **/
15.     {
16.                 if (a[midi] > a[left])       //mid > left >= right
17.                         return left;
18.                 else if (a[midi] > a[right]) //left >= mid >= right
19.                         return midi;
20.                 else                         //left > right > mid
21.                         return right;
22.     }
23. }
24. void QuickSort(int* a, int left, int right)
25. {
26.     //...
27.    
28.     //三数取中
29.         int midi = GetMidIndex(a, left, right);
30.     Swap(&a[left], &a[midi]);
31.    
32.     //...
33. }

复制代码

三数取中尽量包管了选到的key不大不小尽量是中心值，以尽量包管递归结构是一棵完美的二叉树，避免了数组有序时的最坏环境。
小区间优化

如图所示，当递归深到一定层次的时间，递归的区间就愈发的小，但递归的次数却多了起来。
   假设有1000个数，最后一行接近                                                    2                               9                                            2^9                     29 次调用，倒数第二行接近                                                    2                               8                                            2^8                     28 次调用。占了总次数的绝大部分，而最后两层却只为排好几个数。代价太大。
  为了避免这样的环境，镌汰递归次数，可以利用小区间优化。
小区间优化是指，当递归区间小到一定程度时（例如仅有10个元素），利用其他排序举行排序，以镌汰递归次数。

1. //递归版本
2. void QuickSort(int* a, int left, int right)
3. {
4.         if (left >= right)
5.                 return;
7.         //小区间优化
8.         if (right - left < 10) {
9.         InsertSort(a + left, right - left + 1);
10.         return;
11.     }
12.        
13.         int keyi = Partition3(a, left, right);
14.         QuickSort(a, left, keyi - 1);
15.         QuickSort(a, keyi + 1, right);
16. }

复制代码

小区间意味着数组接近有序，而直接插排对接近有序的数组排序结果最好，所以小区间优化选择利用直接插排。
非递归版本

复杂递归一般难以用循环实现，快排的二叉树形递归称为双路递归。双路递归可以用栈的结构模仿。
将排序区间的左右下标生存到栈中，按照先入后出的特点，先入右区间再入左区间，让单趟排序函数读取栈里的左右下标来排序数组。

1. void QuickSortNonR(int* a, int left, int right)
2. {
3.         Stack st;
4.         StackInit(&st);
5.    
6.         StackPush(&st, left);
7.         StackPush(&st, right);
8.    
9.         while (!StackEmpty(&st))
10.     {
11.                 // 读取左右下标
12.         int end = StackTop(&st);
13.                 StackPop(&st);
14.                 int begin = StackTop(&st);
15.                 StackPop(&st);
16.                
17.                 int keyi = Partition1(a, begin, end);
18.                 // [begin,keyi-1] keyi [keyi+1,end]
19.                
20.                 if (keyi + 1 < end) // 保证区间长度>1
21.         {
22.                         StackPush(&st, keyi + 1);
23.                         StackPush(&st, end);
24.                 }
25.                 if (begin < keyi - 1) // 保证区间长度>1
26.         {
27.                         StackPush(&st, begin);
28.                         StackPush(&st, keyi - 1);
29.                 }
30.         }
31.    
32.         StackDestroy(&st);
33. }

复制代码

1. void QuickSortNonR(int* a, int left, int right)
2. {
3.     stack<int> s;
4.     s.push(left);
5.     s.push(right);
7.     while (!s.empty())
8.     {
9.         int end = s.top();
10.         s.pop();
11.         int bgn = s.top();
12.         s.pop();
14.         int keyi = partition(a, bgn, end);
16.         if (keyi + 1 < end)
17.         {
18.             s.push(keyi + 1);
19.             s.push(end);
20.         }
21.         if (bgn < keyi - 1)
22.         {
23.             s.push(bgn);
24.             s.push(keyi - 1);
25.         }
26.     }
27. }

复制代码

  非递归就是把原本存入递归栈帧中的区间左右下标存入栈结构中，每次循环即相当于一次递归。
   
4 归并排序

归并操作在此并不是第一次出现，合并两个有序数组的操作就叫做归并。合并有序数组

归并两个数组，就是每次选出最小值放到新数组中，单趟排序复杂度为                                    O                         (                         n                         )                              O(n)                  O(n)。
根本思想

   怎样归并数组的左右子序列是有序的呢？
  这便要利用递归分治的思想：

• 一个数组看作两个分开的区间，如果这两个区间有序就可以举行归并；
  
• 这两个区间再分开当作四个区间，若这四个区间有序就可以举行归并；……
  
• 如此循环往复，当区间只有一个元素或没有时就以为是有序的。
  

由上图可以看出：

• 先递归分解数组，不绝对半拆分成多个区间，直至区间内仅有一个元素或没有元素。
  
• 再归并合并区间，先将最小的序列归并成有序序列，两个有序的序列不绝合并，直至整个数组完成合并。
  

递归版本

1. //递归子函数
2. void _MergeSort(int* a, int left, int right, int* tmp)
3. {
4.     if (left >= right)
5.         return;
6.        
7.     // 递归
8.     int mid = (left + right) >> 1;
9.    
10.     _merge_sort(a, left, mid, tmp);      // [left , mid  ]
11.     _merge_sort(a, mid + 1, right, tmp); // [mid+1, right]
12.    
13.         // 归并
14.     int i = left;
15.     int i1 = left, i2 = mid + 1;
16.     while (i1 <= mid && i2 <= right)
17.         tmp[i++] = a[i1] < a[i2] ? a[i1++] : a[i2++];
19.     while (i1 <= mid)
20.         tmp[i++] = a[i1++];
21.     while (i2 <= right)
22.         tmp[i++] = a[i2++];
24.     memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
25. }
27. //归并排序主函数
28. void MergeSort(int* a, int n)
29. {
30.         int* tmp = (int*)malloc(sizeof(int) * n);
31.     assert(tmp);
32.    
33.         _MergeSort(a, 0, n - 1, tmp);
35.         free(tmp);
36.         tmp = NULL;
37. }

复制代码

递归分解到只有一个元素时，开始两两归并成一个数组。具体是归并到新数组tmp中，再逐个拷贝回a数组。

非递归版本

   快排非递归利用栈是因为每次排序区间的下标是不确定的，只能入栈来解决。归并的非递归不消借助其他数据结构，因为归并排序是严格的二分，排序区间的下标是确定的。
  不消递归我们就可以跳过递归分解的步调，直接将数组划分区间。第一次循环11归并，第二次循环22归并，第三次循环44归并，知道整个数组归并完成。

1. void MergeSortNonR(int* a, int n)
2. {
3.     int* tmp = new int[n];
5.     int ranger = 1;
6.     while (ranger < n)
7.     {
8.         for (int begin = 0; begin < n; begin += ranger * 2)
9.         {
10.             // [bgn, bgn+rgr-1] [bgn+rgr, bgn+rgr*2-1]
11.             int i1 = begin, i2 = begin + ranger;
12.             int i = begin;
13.             while (i1 < begin + ranger && i2 < begin + ranger * 2)
14.                 tmp[i++] = a[i1] < a[i2] ? a[i1++] : a[i2++];
16.             while (i1 < begin + ranger)
17.                 tmp[i++] = a[i1++];
18.             while (i2 < begin + ranger * 2)
19.                 tmp[i++] = a[i2++];
21.             memcpy(a + begin, tmp + begin, sizeof(int) * (ranger * 2));
22.         }
23.         ranger *= 2;
24.     }
26.     delete[] tmp;
27. }

复制代码

这样固然简朴，但是如果数组的长度不是2的次方，就存在越界访问的问题。
   如果数组有10个元素，在22归的时间就会出现越界访问。同理，如果数组有奇数个元素，11归的时间就越界。
  可见问题是，没有处置惩罚好数组末尾处归并区间越界的问题。
实际上，归并左右区间                                    [                         b                         e                         g                         i                         n                         1                         ,                         e                         n                         d                         1                         ]                         [                         b                         e                         g                         i                         n                         2                         ,                         e                         n                         d                         2                         ]                              [begin1,end1][begin2,end2]                  [begin1,end1][begin2,end2] 中只有                                    b                         e                         g                         i                         n                         1                              begin1                  begin1 不会越界。其他都有越界的可能。故统共有三种环境：
环境解决方案                                                  e                                  n                                  d                                  1                                          end1                           end1 越界修正                                                  e                                  n                                  d                                  1                                          end1                           end1为数组末尾，屏蔽                                                   [                                  b                                  e                                  g                                  i                                  n                                  2                                  ,                                  e                                  n                                  d                                  2                                  ]                                          [begin2,end2]                           [begin2,end2]。                                                  b                                  e                                  g                                  i                                  n                                  2                                          begin2                           begin2 越界屏蔽                                                   [                                  b                                  e                                  g                                  i                                  n                                  2                                  ,                                  e                                  n                                  d                                  2                                  ]                                          [begin2,end2]                           [begin2,end2]。                                                  e                                  n                                  d                                  2                                          end2                           end2 越界修正                                                  e                                  n                                  d                                  2                                          end2                           end2为数组末尾。

1. void MergeSortNonR(int* a, int n)
2. {
3.     int* tmp = new int[n];
5.     int ranger = 1;
6.     while (ranger < n)
7.     {
8.         for (int i = 0; i < n; i += ranger * 2)
9.         {
10.             // [i, i+rgr-1] [i+rgr, i+rgr*2-1]
11.             int b1 = i, b2 = i + ranger;
12.             int e1 = i + ranger - 1, e2 = i + 2 * ranger - 1;
14.             if (e1 >= n) {       // end1 越界
15.                 e1 = n-1;
16.                 b2 = n, e2 = n - 1;
17.             }
18.             else if (b2 >= n) {  // begin2 越界
19.                 b2 = n, e2 = n - 1;
20.             }
21.             else if (e2 >= n) {  // end2 越界
22.                 e2 = n - 1;
23.             }
25.             int j = i;
26.             while (b1 <= e1 && b2 <= e2)
27.                 tmp[j++] = a[b1] < a[b2] ? a[b1++] : a[b2++];
29.             while (b1 <= e1)
30.                 tmp[j++] = a[b1++];
31.             while (b2 <= e2)
32.                 tmp[j++] = a[b2++];
34.             memcpy(a + i, tmp + i, sizeof(int) * (e2 - i + 1)); // 灵活区间长度
35.         }
36.         
37.         //memcpy(a, tmp, sizeof(int) * n);
38.         ranger *= 2;
39.     }
41.     delete[] tmp;
42. }

复制代码

• 拷贝区间长度e2-i+1而不是e2-b1+1，因为b1在归并过程中已被改变。
  
• 固然，end1和begin2越界的环境，也可以直接break。因为末尾区间不会被归并只会拷过来拷回去，但要记得此时不能归并完整个数组再拷贝，会把随机值拷贝回去。
  

1. void MergeSortNonR(int* a, int n)
2. {
3.     int* tmp = new int[n];
5.     int ranger = 1;
6.     while (ranger < n)
7.     {
8.         for (int i = 0; i < n; i += ranger * 2)
9.         {
10.             int b1 = i, b2 = i + ranger;
11.             int e1 = i + ranger - 1, e2 = i + 2 * ranger - 1;
13.             if (e1 >= n)        // end1 越界
14.                     break;
15.             else if (b2 >= n)   // begin2 越界
16.                     break;
17.             else if (e2 >= n)   // end2 越界
18.                                 e2 = n - 1;
20.             int j = i;
21.             while (b1 <= e1 && b2 <= e2)
22.                 tmp[j++] = a[b1] < a[b2] ? a[b1++] : a[b2++];
24.             while (b1 <= e1)
25.                 tmp[j++] = a[b1++];
26.             while (b2 <= e2)
27.                 tmp[j++] = a[b2++];
29.             memcpy(a + i, tmp + i, sizeof(int) * (e2 - i + 1)); // 灵活区间长度
30.         }
31.         
32.         ranger *= 2;
33.     }
35.     delete[] tmp;
36. }

复制代码

复杂度分析

从归并排序的剖析图看，归并排序和快排类似，都是二叉树形的双路递归。区别是快排是“先序”，归并是“后序”。

所以归并排序的时间复杂度是严格的                                         O                            (                            n                            l                            o                            g                            n                            )                                  O(nlogn)                     O(nlogn)，空间复杂度是                                    O                         (                         n                         )                              O(n)                  O(n)。
   快排的时间复杂度依赖选key所以不是严格的                                        O                            (                            n                            l                            o                            g                            n                            )                                  O(nlogn)                     O(nlogn)。
  归并排序的空间复杂度，精确来说要加上栈桢的斲丧，是                                        O                            (                            n                            +                            l                            o                            g                            n                            )                                  O(n+logn)                     O(n+logn)，但                                        O                            (                            l                            o                            g                            n                            )                                  O(logn)                     O(logn)太小可以忽略。
  因为归并排序有额外的空间斲丧，故实际中用的并不多。
 
5 计数排序

根本思想

计数排序不比力元素，而是统计每个元素的出现次数。

• 根据数组中元素的范围，开发充足的空间。
  
• 将数组中的元素按数值无重复地映射到新空间的下标上。统计并存储元素出现的次数。
  
• 根据元素出现的次数，将元素写回到原数组中。
  

相对映射：

• 根据数组元素中的最大值和最小值，二者之间的区间范围就是映射空间的巨细。
  
• 映射位置是元素值                                         x                                  x                     x 减去最小值                                         m                            i                            n                                  min                     min。
  

代码实现

1. void count_sort(int* a, int n)
2. {
3.     // 求范围
4.     int max = a[0], min = a[0];
5.     for (int i = 0; i < n; i++)
6.     {
7.         max = std::max(max, a[i]);
8.         min = std::min(min, a[i]);
9.     }
10.         // 统计个数
11.     int range = max - min + 1;
12.     int* count = new int[range];
13.     memset(count, 0, sizeof(int) * range);
14.        
15.     for (int i = 0; i < n; i++)
16.         count[a[i] - min]++;
17.         // 写回数组
18.     int pos = 0;
19.     for (int i = 0; i < range; i++)
20.     {
21.         while (count[i]--)
22.             a[pos++] = i + min;
23.     }
24. }

复制代码

复杂度分析

两次遍历数组足以完成计数排序，时间复杂度为                                    O                         (                         m                         a                         x                         (                         n                         ,                           r                         a                         n                         g                         e                         )                         )                              O(max(n,\;range))                  O(max(n,range))。
也意味着计数排序恰当数据范围比力会合的整数数组。如果数组元素如果有正有负也不恰当计数排序。
 
复杂度稳固性分析

稳固性的界说：
如果能包管相同的元素的相对位置稳固就是稳固的，反之就是不稳固的。如果该排序能做到稳固，那它就是稳固的，反之则是不稳固的。
稳固性的意义：
稳固性只在特殊的环境下有价值，一般没什么用。
对于一个整数，数字的值属性就是其全部意义。但对于复杂的类型，位置的改变可能会违背我们的需求规则。
   好比考试结果分数相同的环境下就要看交卷的早晚，如果如果更改位置就无法包管交卷早的在前面交卷迟的在背面了。
  排序时间复杂度空间复杂度稳固性表明直接插排                                                  O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)稳固如果想等，直接在背面停住希尔排序                                                  O                                  (                                               n                                     1.3                                              )                                          O(n^{1.3})                           O(n1.3)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)不稳固分组预排，可能变更位置直接选排                                                  O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)不稳固交换的时间，可能会把背面的换到前面来堆排                                                  O                                  (                                  n                                  l                                  o                                  g                                  n                                  )                                          O(nlogn)                           O(nlogn)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)不稳固向下调整时，可能会改变相对位置冒泡排序                                                  O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)稳固如果相称，不会发生交换快排                                                  O                                  (                                  n                                  l                                  o                                  g                                  n                                  )                                          O(nlogn)                           O(nlogn)                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)不稳固单趟排序相互交换无法包管稳固性归并排序                                                  O                                  (                                  n                                  l                                  o                                  g                                  n                                  )                                          O(nlogn)                           O(nlogn)                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)稳固归并操作就是稳固的
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。