这些算法都有一个有趣的性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们把这类排序算法称为 Comparison sorts比较排序。

01 bubble sort 冒泡排序 稳定

Bubble Sort(冒泡排序)是一种简单直观的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为 越大/越小 的元素会经由交换慢慢 “浮” 到数列的顶端(右边)。

冒泡排序，排序n轮，每一轮遍历一遍数组。当发现两个连续数字顺序不对时，交换他们。如果是正序排列，每一次swap，减少一个逆序对。

应用：

  1. 整个冒泡排序进行了几次swap，就是数列中有多少逆序对

冒泡排序给我的感觉就像 ‘Abandon’ 在托福单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

什么时候最快 比较排序 - 图1，当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）
什么时候最慢 比较排序 - 图2，当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）

时间复杂度：比较排序 - 图3
空间复杂度：比较排序 - 图4
bubbleSort.gif

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int a[110], n;
  7. void bubble_sort01(){
  8.     for (int i = 0; i < n; i++)                  //枚举有几趟冒泡
  9.         for (int j = 0; j < n - 1; j++)
  10.             if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
  11. }
  13. void bubble_sort02(){
  14.     for (int i = 0; i < n; i++)                  //枚举有几趟冒泡
  15.         for (int j = 0; j < n - i - 1; j++)   //每一趟j的终点发生优化
  16.             if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
  17. }
  19. void bubble_sort03(){
  20.     for (int i = n - 1; i > 0; i--)          //枚举每趟冒泡的终点
  21.         for (int j = 0; j < i; j++)
  22.             if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
  23. }
  25. void bubble_sort04(){
  26.     for (int i = n - 1; i > 0; i--){          //枚举每趟冒泡的终点
  27.         bool flag = false;                    //立一个flag
  28.         for (int j = 0; j < i; j++)              //如果一趟下来没有交换，    
  29.         if (a[j] > a[j + 1]){                 //就表示已经有序
  30.                 swap(a[j], a[j + 1]);
  31.                 flag = true;
  32.             }
  34.         if (!flag) break;
  35.     }
  36. }
  38. int main(){
  39.     cin >> n;
  40.     for (int i = 0; i < n; i++) cin >> a[i];
  42.     bubble_sort04();
  44.     for (int i = 0; i < n; i++) cout << a[i] << ' ';
  45.     puts("");
  47.     return 0;
  48. }
  50. /*
  51. 5  
  52. 3 4 2 1 5
  54. 1 2 3 4 5 
  55. */

第一轮过后，最大数字被放在了正确的位置上。k轮过后，k个最大的数字被放在了正确的位置上。n轮过后，n个数字（这个数组）被放在了正确位置上。

需要注意的是，冒泡排序只交换相邻两个数字。在整个冒泡排序的过程中，进行了几次swap操作，就表示序列当中，有几个逆序对。

如果，整个序列是倒序的，如果要冒泡成正序，交换次数是1+2+3...+(n-1) = n*(n-1)/2

02 selection sort 选择排序 不稳定

选择排序是一种简单直观的排序算法，无论什么数据进去都是比较排序 - 图6的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤：

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

为什么不稳定呢？

  1. 例如：
  2. 5 3 5 2 4
  4. 第一趟排序，第1个5 和 2发生交换
  5. 2 3 5 5 4
  7. 但是，这样两个5的先后顺序发生了改变。所以，不稳定

时间复杂度：比较排序 - 图7
空间复杂度：比较排序 - 图8
selectionSort.gif

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int a[110], n;
  7. void selection_sort(){
  8.     for (int i = 0; i < n; i++)
  9.         for (int j = i + 1; j < n; j++)          //枚举未排序的部分
  10.             if (a[j] < a[i]) swap(a[j], a[i]);   //把最小的交换到a[i]上
  11. }
  13. int main(){
  14.     cin >> n;
  15.     for (int i = 0; i < n; i++) cin >> a[i];
  17.     selection_sort();
  19.     for (int i = 0; i < n; i++) cout << a[i] << ' ';
  20.     puts("");
  22.     return 0;
  23. }
  25. /*
  26. 5  
  27. 3 4 2 1 5
  29. 1 2 3 4 5 
  30. */

03 insertion sort 插入排序 稳定

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。
insertion-sort-1-animate-example.svg

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入

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

应用：

  1. 插入排序，插在哪个位置，其实是一个遍历的过程，这个遍历是就近遍历，遍历到合适的位置，就会停下来。如果是一个已经排好序的序列，更改了某一个值，想要快速的得到新的序列，那么可以对变更的值，进行向左找位置，向右找位置，O(n)的时间或者更小，完成新的排序（《插入排序》）

时间复杂度：比较排序 - 图11
空间复杂度：比较排序 - 图12
insertionSort.gif

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int a[110], n;
  7. void insertion_sort(){
  8.     for (int i = 1; i < n; i++){   //从第二个数a[1]开始
  9.         int t = a[i];
  11.         int j = i - 1;
  12.         while (j >= 0 && a[j] > t){
  13.             a[j + 1] = a[j];      //依次往后坐一位
  14.             j--;
  15.         }
  17.         a[j + 1] = t;             //跳出while时，j指向的是第一个a[j]<=t的位置
  18.     }
  19. }
  21. int main(){
  22.     cin >> n;
  23.     for (int i = 0; i < n; i++) cin >> a[i];
  25.     insertion_sort();
  27.     for (int i = 0; i < n; i++) cout << a[i] << ' ';
  28.     puts("");
  30.     return 0;
  31. }
  33. /*
  34. 5  
  35. 3 4 2 1 5
  37. 1 2 3 4 5 
  38. */
  1. // 二分插入排序
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. int a[110], n;
  9. void insertion_sort(){
  10.     for (int i = 1; i < n; i++){   // 从第二个数a[1]开始
  11.         int t = a[i];
  13.         // 二分找到要插入的位置
  14.         int l = 0, r = i - 1, best = 0;
  15.         while (l <= r){
  16.             int mid = (l + r) >> 1;
  17.             if (a[mid] < t){
  18.                 l = mid + 1;
  19.                 best = mid + 1;
  20.             }
  21.             else r = mid - 1;
  22.         }
  24.         for (int j = i - 1; j >= best; j--) a[j + 1] = a[j];
  26.         a[best] = t;        
  27.     }
  28. }
  30. int main(){
  31.     cin >> n;
  32.     for (int i = 0; i < n; i++) cin >> a[i];
  34.     insertion_sort();
  36.     for (int i = 0; i < n; i++) cout << a[i] << ' ';
  37.     puts("");
  39.     return 0;
  40. }
  42. /*
  43. 5  
  44. 3 4 2 1 5
  46. 1 2 3 4 5 
  47. */

例题，2075：【21CSPJ普及组】插入排序（sort）

  1. // 插入排序的应用，如何做到O(n)的时间复杂度，琢磨
  2. // 快排为什么不行，只能50pts，滥用sort()的危害是什么？

04 shell sort 希尔排序 不稳定

希尔排序是希尔 (Donald Shell) 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破比较排序 - 图14的第一批算法之一。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为比较排序 - 图15的排序（冒泡排序或插入排序），可能会进行 n 次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用 i += step_size 而不是 i++ ）。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

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

希尔排序耗时的操作有：比较 + 后移赋值
1) 最好情况：
序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即比较排序 - 图16
2) 最坏情况：
希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是比较排序 - 图17。已知最好的最坏时间复杂度为比较排序 - 图18
3) 平均时间复杂度：比较排序 - 图19

时间复杂度：最好比较排序 - 图20，最坏比较排序 - 图21，平均比较排序 - 图22根据步长序列的不同而不同，
空间复杂度：比较排序 - 图23
https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
image.png
Sorting_shellsort_anim.gif

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. int a[110], n;
  7. void shell_sort(int a[], int len){
  8.     int h = 1;
  9.     while (h < len / 3) h = h * 3 + 1;
  11.     while (h >= 1){
  12.         for (int i = h; i < len; i++)
  13.             for (int j = i; j >= h && a[j] < a[j - h]; j -= h)
  14.                 swap(a[j], a[j - h]);
  16.         h /= 3;
  17.     }
  18. }
  20. int main(){
  21.     cin >> n;
  22.     for (int i = 0; i < n; i++) cin >> a[i];
  24.     shell_sort(a, n);
  26.     for (int i = 0; i < n; i++) cout << a[i] << ' ';
  27.     puts("");
  29.     return 0;
  30. }
  32. // 比较神奇，shell_sort可以过1e5的数据
  33. // https://www.acwing.com/problem/content/description/787/

05 merge sort 归并排序 分治 逆序对 稳定

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

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
  • 自下而上的迭代

算法步骤：

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

应用：

  1. 两个有序的序列，可以O(n)的时间复杂度，合并成一个有序的序列。使用的就是归并排序的合并环节
  2. 求逆序对的个数
  3. 两两相邻比较，比较完，又要排个序。O(nlogn)就是快排，O(n)可以考虑合并的方式(《瑞士轮》)

时间复杂度：比较排序 - 图26
空间复杂度：比较排序 - 图27
mergeSort.gif

  1. // 代码实现，见分治
  3. void merge_sort(int q[], int l, int r)
  4. {
  5.     if (l >= r) return;
  7.     int mid = l + r >> 1;
  8.     merge_sort(q, l, mid);
  9.     merge_sort(q, mid + 1, r);
  11.     int k = 0, i = l, j = mid + 1;
  12.     while (i <= mid && j <= r)
  13.         if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
  14.         else tmp[k ++ ] = q[j ++ ];
  16.     while (i <= mid) tmp[k ++ ] = q[i ++ ];
  17.     while (j <= r) tmp[k ++ ] = q[j ++ ];
  19.     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
  20. }

例题，1955：【11NOIP普及组】瑞士轮

06 quick sort 快速排序 分治 不稳定

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法过程：

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

算法过程简化版：
两个哨兵，一个从左向右走，一个从右向左走
相遇后，左边都比 j 小，右边都比 j 大

快速排序的最坏运行情况是 O(n²)，比如说有序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(logn)，所以适合在数据集比较大且无序的时候使用。

空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为比较排序 - 图29，其空间复杂度也就为比较排序 - 图30，最坏情况，需要进行 n‐1 递归调用，其空间复杂度为比较排序 - 图31，平均情况，空间复杂度也为比较排序 - 图32。

特殊，对单链表进行快排，是稳定的。

时间复杂度：比较排序 - 图33
空间复杂度：比较排序 - 图34
quickSort.gif

  1. // 代码实现，见分治
  3. void quick_sort(int q[], int l, int r)
  4. {
  5.     if (l >= r) return;
  7.     int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
  8.     while (i < j)
  9.     {
  10.         do i ++ ; while (q[i] < x);
  11.         do j -- ; while (q[j] > x);
  12.         if (i < j) swap(q[i], q[j]);
  13.     }
  14.     quick_sort(q, l, j), quick_sort(q, j + 1, r);
  15. }
  1.     int x = -5;
  2.     cout << (x >> 1) << '\n';  // 向下取整，向负方向取整
  3.     cout << (x / 2) << '\n';   // 向0取整

例题，1938：【07NOIP普及组】奖学金

  1. 方法1，用STL排序，构造一个结构体，做自定义排序
  2. 时间复杂度是O(nlogn)
  4. 方法2，使用选择排序的思路。先从1到n搜索，利用“打擂台”的方法，找到最优的学生，
  5. 把他和学员为1的同学交换。然后再从2到n搜索，找到剩下学生中最优的，放到第2个位置
  6. 重复5次，就找到最优的5个人。时间复杂度是O(kn)
  8. 方法3，使用插入排序的思路。建立一个长度为5的答案数组来维护前5名(初始假设有5个总分为0的学生)，
  9. 然后将每个学生和答案数组中从后往前比较，将这名学生插入到合适的位置(也有可能连第5名都比不过直接淘汰)
  10. 时间复杂度是O(kn)
  12. 此题k是一个固定的常数，当k较小，这是一个好的选择。如果k较大，就是所说的常数较大。
  13. 在常数特别大的情况下，低阶复杂度算法可能实际效果不如高阶复杂度算法。

07 heap sort 堆排序 不稳定

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

分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤：

  1. 创建一个堆 H[0……n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。

时间复杂度：最好O(nlogn)，最坏O(nlogn)，平均O(nlogn)
空间复杂度：O(1)
heapSort.gif
Sorting_heapsort_anim.gif

堆排序是一个优秀的算法，但是在实际应用中，快排的性能一般会优于堆排序。堆有一个常见的应用：作为高效的优先队列(priority queue)。优先队列是一种用来维护一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字(key)。主要用途：能够O(1)时间返回堆顶元素。

  1. // 会用STL  priority_queue 默认大根堆
  3. // 如何使用小根堆
  4. // 插入的数值，放负数，转为小根堆
  5. // 或者自定义struct，重载小于符号
  7. // 这块知识放在STL展开，在图论求最短路时会应用