更新中，未完待续 考研凉凉的结果就是不仅失去了应届生走校招的机会，而且还因为疫情走不了，僵。因为接下来准备找一份安全相关的C/C++开发工作，所以在刷了段时间题后，把排序算法重新复习整理一下。之前虽然学习过，但是现在一些不经常用的东西很快就忘了细结了，只能偶尔复习一下。
本文主要以十大经典排序算法 为参考文章来进行复习，使用C++实现，代码都经过了测试。
冒泡排序(Bubble Sort) 冒泡排序，选择排序和插入排序算是我使用最多的三种排序方法了，因为实现起来简单，惭愧惭愧。
流程就是比较相邻的元素，如果前面的比后面的大，就把他们交换一下。
这样一轮交换结束后，最后一个元素是所有数字里最大的，最坏情况下即数组是逆序的情况下，所有第一轮需要比较和交换n-1次，第二轮是n-2次，以此类推，最后总的比较和交换的次数是1+2+..+n-1=n(n-1)/2次，时间复杂度是O($n^2$)，每次对换需要一个temp，所以空间复杂度是O(1)，由于对换的时候可以对相同元素选择不对换，所以是稳定的排序。
i = n - 2
class Sort {public : vector <int > BubbleSort (vector <int > array ) int n = array .size (); for (int i = 0 ; i < n - 1 ; i ++){ for (int j = 0 ; j < n - i - 1 ; j ++){ if (array [j] > array [j + 1 ]){ int temp = array [j]; array [j] = array [j + 1 ]; array [j + 1 ] = temp; } } } return array ; } };
选择排序(Selection Sort) 找到最小的一个元素放在第一个位置，然后循环剩下的元素，或者找最大的放最后一个位置。
比较次数和冒泡实际上是一样的，也是n-1 + n-2 + … + 1 = n * (n - 1) / 2次，时间复杂度是O($n^2$)，空间复杂度是O(1)
class Sort {public : vector <int > SelectionSort (vector <int > array ) int n = array .size (); for (int i = 0 ; i < n; i ++){ int min = i; for (int j = i + 1 ; j < n; j ++){ if (array [j] < array [i]){ min = j; } } int temp = array [i]; array [i] = array [min ]; array [min ] = temp; } return array ; } };
插入排序(Insertion Sort) 插入排序是对每一个元素，从开头开始扫描，找到合适的位置插入
由于对每个元素，都需要向后移动1+2+..+n-1=n*(n-1) / 2次数据，所以时间复杂度也是O($n^2$)，空间复杂度是O(1)
class Sort {public : vector <int > InsertionSort (vector <int > array ) int n = array .size (); for (int i = 1 ; i < n; i++) { int temp = array [i]; int front = i - 1 ; while (front >= 0 && array [front] > temp) { array [front + 1 ] = array [front]; front--; } array [front + 1 ] = temp; } return array ; } }
希尔排序(Shell Sort) 插入排序的改进，优先比较距离近的元素，所以又叫缩小增量排序，说白了就是把插入排序中，一个一个比较改成从第n个开始比较，作为增量，直到这个增量变为1，因此增量序列是$t_1，t_2，t_3…t_n$，当i < j时有$t_i > t_j$，$t_n = 1$
目前为止还没有一个最好的增量序列，希尔提出的序列是$t1=n/2$, $t {i+1}=t_i/2$，最坏情况下的时间复杂度是O($n^2$)，n在特定范围的时候，时间复杂度是O($n^1.3$)，空间复杂度是O(1)
class Sort {public : vector <int > ShellSort (vector <int > array ) int n = array .size (); for (int t = n / 2 ; t > 0 ; t /= 2 ){ for (int i = 0 ; i < t; i ++){ for (int j = i + t; j < n; j += t){ if (array [j] < array [j - t]){ int temp = array [j], k; for (k = j - t; k >= 0 && array [k] > temp; k -= t){ array [k + t] = array [k]; } array [k + t] = temp; } } } } return array ; } };
快速排序(Quick Sort) 快速排序是对冒泡排序的改进，基于分治法思想，先选取一个元素作为基准，通过一趟排序，把整个列表划分为独立的两部分，前半部分均小于基准，后半部分大于基准，这时，基准所在的位置是最终结果的位置，整个过程称为一趟快速排序，接下来分别对前后两个子表递归重复上述过程，直至每个部分只有一个元素或者为空为止。
快速排序的空间复杂度取决于递归调用栈的深度，最好情况下是$\lceil\log_2(n+1)\rceil$，最坏情况下需要进行n-1次递归，栈深度为O(n)，因此空间复杂度在最坏情况下为O(n)，评价情况下为O($\log_2n$)。
时间复杂度在最坏情况下，划分的两个部分完全不对称，即一部分是n-1个元素，另一部分是0个元素，在数组完全逆序或者基本有序的情况下，得到最坏情况的时间复杂度O($n^2$)。
有很多方法可以提高快速排序的效率。第一种方法是在子序列的规模较小的时候就换用直接插入排序。第二方法是尽量选择一个可以均匀划分序列的基准，比如从头尾及中间选取三个元素，然后取其中间值作为基准，或者随机从序列中选择一个基准。
class Sort {public : vector <int > QuickSort (vector <int > array ) QuickSortRecursion(array , 0 , array .size () - 1 ); return array ; } private : void QuickSortRecursion (vector <int > &array , int low, int high) if (low < high) { int pivotpos = Partition(array , low, high); QuickSortRecursion(array , low, pivotpos - 1 ); QuickSortRecursion(array , pivotpos + 1 , high); } } int Partition (vector <int > &array , int low, int high) int pivot = array [low]; while (low < high) { while (low < high && array [high] >= pivot) --high; array [low] = array [high]; while (low < high && array [low] <= pivot) ++low; array [high] = array [low]; } array [low] = pivot; return low; } }
堆排序(Heap Sort) 堆排序是一种树形的选择排序，在排序过程中，把待排序的序列看作一颗完全二叉树的顺序存储结构，利用二叉树来选择值最大或最小的元素。
堆存在两种情况：
根结点小于左右子结点，称为小根堆
根结点大于左右子结点，称为大根堆
首先要建立一个大根堆，方法就是先找到最后一个结点的父结点，由于堆是一个完全二叉树，所以最后一个结点的下标的父结点应该是$\lfloor length/2 - 1 \rfloor$(下标从0开始)，接着比较最后一个结点和其父结点的值，若大于父结点则交换。对这个父结点和它前面的结点重复上述过程，就完成了初始建堆。
建堆完成后，所有的数据组成一个大根堆，根结点是最大的元素，将其放在数组末尾，也就是把根结点和最后一个结点交换，交换完成后，堆的结构被破坏，需要重新调整。
除去已经排好序的最大的结点，其他结点作为一个堆重新进行调整直至成为大根堆。由于只修改了根结点，所以只需要对根结点进行一次向下调整即可。重复把最大元素调整到数组末尾，即可得到一个有序序列。
建堆的时间复杂度为O(n)，所以可以利用建堆找出很多数中的最大的几个数字。建好堆后对堆调整了n-1次，每次调整的时间复杂度取决于二叉树的高度，所以堆排序的时间复杂度为O($n\log_2(n)$)，由于使用了常数个辅助单位，所以空间复杂度是O(1)，由于在筛选的时候可能把值相同的元素互相调换，所以是一种不稳定的排序。
class Sort {public : vector <int > HeapSort (vector <int > array ) int len = array .size (); BuildMaxHeap(array , len); for (int i = len - 1 ; i > 0 ; i--) { int temp = array [i]; array [i] = array [0 ]; array [0 ] = temp; AdjustDown(array , 0 , i); } return array ; } private : void BuildMaxHeap (vector <int > &array , int len) for (int i = len / 2 - 1 ; i >= 0 ; i--) { AdjustDown(array , i, len); } } void AdjustDown (vector <int > &array , int k, int len) int temp = array [k]; for (int i = k * 2 + 1 ; i < len; i = i * 2 + 1 ) { if (i + 1 < len && array [i] < array [i + 1 ]) { i++; } if (temp >= array [i]) { break ; } else { array [k] = array [i]; k = i; } } array [k] = temp; } };
归并排序(Merge Sort) 归并排序基于一种全新的思想，即将两个或两个以上的有序表组合成一个新的有序表，假定有n个元素待排序，可以看作是n个有序表，然后两个两个归并，得到$\lceil n/2 \rceil$个长度为1或2的有序表，继续两两归并直到合并为一个长度为n的有序表，这种方法称为二路归并，如果是多个有序表归并则称为n路归并。
由于需要用到n个辅助空间，所以空间复杂度是O(n)，每趟归并的时间复杂度是O(n)，进行$\lceil log_2n \rceil$次归并，所以时间复杂度是O($n\log_2n$)$，因为排序不会改变相同元素的相对位置，所以是稳定的排序。
class Sort {private : void Merge (vector <int > &temp, vector <int > &array , int low, int mid, int high) int i = 0 , j = 0 , k = 0 ; for (i = low; i <= high; i ++){ temp[i] = array [i]; } for (i = low, j = mid + 1 , k = i; i <= mid && j <= high; k ++){ if (temp[i] <= temp[j]){ array [k] = temp[i ++]; }else { array [k] = temp[j ++]; } } while (i <= mid){ array [k ++] = temp[i ++]; } while (j <= high){ array [k ++] = temp[j ++]; } } void MergeSortTemp (vector <int > &temp, vector <int > &array , int low, int high) if (low < high){ int mid = (low + high) / 2 ; MergeSortTemp(temp, array , low, mid); MergeSortTemp(temp, array , mid + 1 , high); Merge(temp, array , low, mid, high); } } public : vector <int > MergeSort (vector <int > array ) vector <int > temp (array .size (), 0 ) MergeSortTemp(temp, array , 0 , array .size () - 1 ); } };
计数排序(Counting Sort) 桶排(Bucket Sort) 基数排序(Radix Sort)