1. 排序的概念1.1 常见的排序算法1.2 排序算法的评价指标复杂度评价排序算法的第一大指标就是时间复杂度和空间复杂度它衡量算法的时间效率和空间效率。稳定性假定在待排序的数据元素中有两个元素 Ri 和 Rj它们对应的关键字为 ki 和 kj 且 ki kj排序前 Ri 在 Rj 的前面排序后可以保证 Ri 依旧在 Rj 的前面相对顺序不变则称这个排序算法是稳定的。1.3 内部排序和外部排序^ 由于待排序的记录数量不同使得排序过程中涉及的存储器不同可以将排序方法分为两大类内部排序待排序的记录存放在计算机随机存储器内存中进行排序的过程。内部排序关注任 何让复杂度更低。外部排序待排序的记录数据量太大以致内存一次不能容纳全部记录在排序过程中需要对外 存硬盘进行访问的排序过程。外部排序关注如何使读写硬盘的次数更少。^ DDR5内存的读写速度可以达到 50-100GB/s机械硬盘HDD的读写速度80-200MB/s顶级固态硬盘SSD读写速度约为 7-14GB/s内存的速度是顶级固态硬盘 5-10倍所以外排影响的是读写硬盘的次数。1.4 排序过程动图网站^ 新加波国立大学计算机学院的教授 Steven Halim 博士牵头创建的https://visualgo.net/en/sorting^ 美国旧金山大学计算机科学系的官方网站https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html2. 插入排序2.1 直接插入排序2.1.1 思想及过程插入排序类似于玩扑克牌等插牌过程每次将一个待排序的元素按照其关键字大小插入到前面已排好序的序列中按照该这种方式将所有元素全部插入完成即可。单次插入思想 [0,end] 为有序区间将 end1 位置的关键字插入到 [0,end] 有序区间达到 [0,end1] 区间有序。// [0,end]有序 end1位置的值插入[0,end]保持有序 int end; int tmp a[end 1]; while (end 0) { if (tmp a[end]) { a[end 1] a[end]; end--; } else { // 挪动结束跳出循环 break; } } a[end 1] tmp;^ 整体插入思想a. 直接插入排序最开始是将 [0,0] 做为第一个有序区间将 1 位置的值插入到 [0,0]这样 [0,1] 区间就有序了b. 再把 2 位置插入到 [0,1]这样 [0,2] 区间就有序了c. 以此类推不断重复上述过程直到 [0,n-2] 有序最后把 n-1 位置插入到 [0,n-2] 区间这样 [0,n-1] 序列就整体有序了2.1.2 代码实现void InsertSor(int* a, int n) { // 将 [1,n-1] 位置的值依次插入到前面的有序区间 for (int i 0; i n - 1; i) { // [0,end]有序 end1位置的值插入[0,end]保持有序 int end i; int tmp a[end 1]; while (end 0) { if (tmp a[end]) { a[end 1] a[end]; end--; } else { break; } } a[end 1] tmp; } } void PrintArray(int* a, int n) { for (int i 0; i n; i) { printf(%d , a[i]); } printf(\n); } void TestInserSort() { int a[] { 2,3,5,6,7,9 }; InsertSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); }2.1.3 复杂度和稳定性^ 直接插入排序最好情况为正序如要排升序序列本身为升序则每次不需要挪动数据数据间比较 n-1 次则时间复杂度为 O(n)^ 直接插入排序最坏情况为逆序如要排升序序列本身为降序则挪动数据的次数是一个 1 至 n-1 的等差数列则时间复杂度为 O(n^2)^ 直接插入排序只需要常数个辅助变量空间复杂度为 O(1)^ 从上述结论可见直接插入排序比较挑序列的原始顺序当序列顺序有序或接近顺序有序时效率较高^ 直接插入排序只要 end1 位置的值插入到 [0,end] 序列比较时相等则插入到相等值的后面位置则可以保持稳定性2.1.4 折半插入排序^ 下一个要插入的元素是 keykey 前面的 [0,end] 为有序区间。直接插入排序是从后面往前逐个比较如果 key 非常小则比较次数较多如果使用二分查找在前面有序区间确认待插入元素 key 的位置则可以减少元素间的比较次数这种方式叫做折半插入排序。^ 折半插入排序在逆序时减少了元素的比较次数但是并没有减少挪动数据的次数其次在正序时比较次数反而会变多挪动数据的次数不变总之整体时间复杂度依旧是 O(n^2)。代码实现void InsertSortMid(int* a, int n) { // [0,n-1] for (int i 0; i n - 1; i) { // [0,end]有序 end1位置的值插入[0,end]保持有序 int end i; int key a[end 1]; // 利用二分查找找待插入元素在前面已有部分的位置 int left 0, right end; while (left right) { int mid (right left) / 2; if (key a[mid]) right mid - 1; else left mid 1; } // 将[left,end]之间的元素整体往后挪动一个位置 for (int j end; j left; j--) a[j 1] a[j]; // 插入 key a[right 1] key; } }2.2 希尔排序2.2.1 思想及过程^ 希尔排序是直接插入排序的一种改进又称缩小增量排序是1959年由 Donald Shell 提出来的。^ 直接插入排序在逆序的情况下每次单趟插入都需要大量挪动数据。希尔排序是将待排序序列下标按照增量d分为若干组对每组数据分别进行直接插入排序。然后再不断缩小增量d当d1时上述过程就是直接插入排序保证数据有序。这样最后一趟d1时效率就很高了。^ 总结一下希尔排序的本质是先痛过预排序d1让待排序序列接近有序最后再通过直接插入排序d1快速让序列有序。^ 假设d3时随机数组进行预排序过程展示^ 假设d3时逆序数组进行预排序过程展示^ 假设d1时所以数据看作一组就是直接插入排序2.2.2 代码实现^ Shell 提出的缩小增量方案为 dd/2;^ Knuth 提出的缩小增量方案为 dd/31;^ Sedgewick 提出的缩小增量方案为和组合交错子序列^ Knuth 的方案高效简洁应用非常广泛在很多算法教科书和实际工程代码中都能见到它的身影。void ShellSort(int* a, int n) { int d n; while (d 1) { // 1 保证最后一个 d 一定是 1 // d 1 时是预排序 // d 1 时是直接插入排序 d d / 3 1; // 缩小增量 // 关键点i 控制了多个间隔为 d 的组串联并行插入排序 for (int i 0; i n - d; i) { int end i; int tmp a[end 1]; while (end 0) { if (tmp a[end]) { a[end d] a[end]; end - d; } else { break; } } a[end d] tmp; } } }2.2.3 复杂度和稳定性^ 希尔排序的时间复杂度和稳定性相比于直接插入排序要复杂得多。因为它依赖于“增量序列”的选择并且涉及一些尚未完全解决的数学问题。直到今天对于一些增量序列其精确的时间复杂度仍难是一个开放的研究问题。^ Shell 提出的缩小增量方案为 dd/2如果数组恰好在奇数位置均是很小的数偶数位置均是很大的数且增量序列由公因子那么前几轮预排序几乎没有起到什么作用直到最后一轮d1时数据几乎还是乱的导致插入排序近乎满负荷运行从而退化成平方级复杂度最坏情况下复杂度经过证明为 O()平均情况时间复杂度经过证明为 O()。^ Knuth 提出的缩小增量方案为 dd/31最坏情况时间复杂度经过严格证明为 O() 而平均情况时间复杂度为 O() 至今尚未得到严格的数学证明但是包括Knuth 本人在内内的多位科学家通过复杂的数学分析给出了非常接近这个结论的论证大量实验数据也和这个结论吻合。^ Sedgewick 提出的缩小增量方案为和组合交错子序列最坏情况时间复杂度为 O() 而平均情况复杂度经过证明为 O() 。^ 理论而言 Sedgevick 的增量方案为最优方案但是实践中 Knuth 更简洁且效率也很不错所以在教学和实践中我们一般都使用 Knuth 的方案。^ 结论在面试中被问到希尔排序的实践复杂度时我们可以达到它取决于增量序列的选择在优良增量序列下可达到 O() 和 O() 之间。^ 希尔排序只需要常数个辅助变量空间复杂度为 O(1)。3. 选择排序3.1 简单选择排序3.1.1 思想及过程^ 每一趟在待排的 n-i1 i1,2,……,n-1个元素中找关键码最小或最大的元素作为有序序列的第i个元素等到第 n-1 趟排完之后待排序区间中就剩一个元素就无需再选区间就有序了3.1.2 代码实现void SelectSort(int* a, int n) { for (int i 0; i n - 1; i) { // 在区间 [i1,n-1] 中找到最小元素的位置 int mini i; for (int j i 1; j n; j) { if (a[j] a[mini]) mini j; } // 如果mini不在区间最左侧即i位置将mini位置的最小值与元素i位置的值交换 if (mini ! i) { int tmp a[i]; a[i] a[mini]; a[mini] tmp; } } }3.1.3 复杂度和稳定性^ 无论待排序序列为正序逆序乱序每趟都需要去比较选出最小数据累积比较次数为1至n-1的等差数列所以简单选择排序时间复杂度为 O()。^ 简单选择排序只需要常数个辅助变量空间复杂度为 O(1)。^ 简单选择排序无法保持稳定性如{5650203}我们可以遍历一遍选出第一个0交换到最左边的位置保持0的相对顺序但是在交换过程中5的相对顺序就被破坏了。3.2 堆排序^ 堆排序也是一种选择排序简单选择排序每次使用暴力遍历选出最小或者最大的数而堆排序则数组逻辑上看做完全二叉树建堆/调堆后选出最大或最小的数实现排序。^ 堆排序优势是通过建堆/调堆选数效率极高时间复杂度为 O(nlogn)。^ 堆排序只需要常数个辅助变量空间复杂度为 O(1)。^ 堆排序无法保持稳定性如{2122}建堆后排序把堆顶的数据换到最后位置则相对顺序就乱了。3.2.1 代码实现void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } // 向下调整算法 void AdjustDown(int* a, int n, int parent) { // 假设法逻辑child 先指向左孩子 int child parent * 2 1; // child n 超出数组的范围说明孩子不存在 // parent 指向叶子结点调整到叶子结点 while (child n) { // 左右孩子比较找出大的那个孩子 if (child 1 n a[child 1] a[child]) { child; } // 孩子大于父亲将大的孩子调整到父亲位置 if (a[child a[parent]]) { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } } void HeapSort(int* a, int n) { // 升序建大堆 // 降序减小堆 for (int i (n - 1 - 1) / 2; i 0; i--) { AdjustDown(a, n, i); } int j 1; while (j n) { // 选出的第j大/小的数据换到倒数第j个位置 Swap(a[0], a[n - j]); AdjustDown(a, n - j, 0); j; } }4.交换排序4.1 冒泡排序4.1.1 思想及过程^ 单趟冒泡假设排升序冒泡的过程是从前往后或从后往前两两比较相邻元素的值直到序列中相邻元素比较交换完成称为一趟冒泡。^ 整体冒泡假设排升序一趟冒泡结束后会将最大元素放在区间最后即最大元素已经排列好了。下一趟冒泡可以对除最大元素外的子序列从前往后继续冒泡结束后次大元素就可以排列好。以此类推共 n-1 趟冒泡后序列就排好了。注意最后一趟区间中只有一个元素本趟冒泡可以不需要因此是 n-1 趟冒泡过程。4.1.2 代码实现void BubbleSort(int* a, int n) { for (int j 0; j n; j) { int flag 0; for (int i 1; i n - j; i) { if (a[i - 1] a[i]) { int tmp a[i - 1]; a[i - 1] a[i]; a[i] tmp; flag 1; } } // flag 0 代表在上一趟冒泡排序中两两比较一次都没有交换 // 则说明这段序列已经有序 if (flag 0) break; } }4.1.3 复杂度和稳定性^ 最坏情况下序列逆序累积比较次数为1至n-1的等差数列所以冒泡时间复杂度为 O().^ 最好情况下序列正序比较n-1次没有发生交换时间复杂度为 O(n)。^ 冒泡排序只需要常数个辅助变量空间复杂度为 O(1)。^ 冒泡排序比较时前一个元素等于后一个元素时不交换则可以保持稳定性。4.2 快速排序4.2.1 思想及过程^ 快速排序由C.A.R.Hoare在1960年提出的是基于分治思想。它是在待排序区间中任取一个元素作为枢轴或称基准值通常选取区间首元素然后按照基准值大小将区间中元素分割称左右两部分左侧区间中元素小于等于基准值右侧区间中元素大于等于基准值即基准值已经放在了最终该放的位置上该过程称为一次单趟划分。划分结束后在对基准值左右两端子区间重复执行上述过程的过程一般使用递归直到子区间只要一个值或者不存在。挖坑法单趟划分严蔚敏教科书1. 假设用最左边的值做枢轴基准值把最左边的 23 保存到 pivotkey 左边就形成了第一个坑2. right 找比基准值pivotkey 小的找到后放到 left 指向的坑那么 right 位置就成为新的坑3. left 找到比基准值pivotkey 大的找到后放到 right 指向的坑那么 left 职位就成为新的坑4. 不断重复 2 和 3 的步骤直到 left 和 right 相遇left 和 right 相遇一定是在坑最后把 pivotkey 放到这个位置就完成了单趟划分// 挖坑法 int PartitionDigHole(int* a, int left, int right) { // 保存基准值left 位置形成第一个坑 int pivotkey a[left]; // 相遇则结束相遇位置一定是一个坑 while (left right) { // 右边找小 while (left right a[right] pivotkey) --right; // 右边的小的放到左边的坑right 形成新的坑 a[left] a[right]; // 左边找大 while (left right a[left] pivotkey) left; // 左边的大的放到右边的坑left 形成新的坑 a[right] a[left]; } // 基准值放到相遇位置的值 a[left] pivotkey; return left; } void QuickSort(int* a, int left, int right) { if (left right) return; int pivotkeyi PartitionDigHole(a, left, right); // 递归左右区间 QuickSort(a, left, pivotkeyi - 1); QuickSort(a, pivotkeyi1 ,right); }Lomnto 的单趟划分算法导论1. 假设用最右边的值做枢轴基准最左边也是可以的处理细节微调即可2. 最开始 prve 和 cur 一前一后指向区间开始位置3. cur 找到比 pivotkey 小的值跟 prve 位置的值交换prve 一定是比 pivotkey 小的值所以这里相当于比 pivotkey 小于或等于的值换到前面把大于 pivotkey 的值换到后面4. 不断重复3步骤直到 cur 走到右边界 pivotkey 位置结束交换 prev 和 pivotkey 位置的值这就把 pivotkey 换到了中间pivotkey 左边区间小于 pivotkey右边区间大于 pivotkeyvoid Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } // Lomuto 前后指针 int PartitonLomtuo(int* a, int left, int right) { int pivotkey a[right]; int prve left - 1; int cur left; while (cur right) { // cur找小找到比pivotkey小的值则根prev位置的值交换 // prve的后一个指向的一定是比pivotkey大的值 if(a[cur] pivotkey prve ! cur) Swap(a[prve], a[cur]); cur; } Swap(a[prve1], a[right]); return prve 1; } void QuickSort(int* a, int left, int right) { if (left right) return; int pivotkeyi PartitonLomtuo(a, left, right); // 递归左右区间 QuickSort(a, left, pivotkeyi - 1); QuickSort(a, pivotkeyi 1, right); }Hoare 的单趟划分工业实践1. 假设用最左边的值做枢轴基准值pivotkey2. low 找比 pivotkey 大或等的值high 找比 pivotkey 的值找到后交换两个位置的值这样大的就换到右边小的就换到左边3. 不断重复2的步骤直到 low 和 high 相遇或交错结果时 high 一定指向最后一个小于等于pivotkey 的值4. 序列被分割为 [left,high] 和 [high1,right][left,high]的值小于等于pivotkey[high1,right]大于等于pivotkeyHoare的方法单趟分割并没有确定 pivotkey 作为主元分割区间所以递归时一定哟啊注意左右区间包含分割点 high这点根挖坑法和Lomuto法是不一样的一定要注意5. Hoare法单趟并没有分割出pivotkey中作为主元分割所以理论而言选pivotkey可以是区间任意位置的值void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } // Hoare 左右指针 int PartitionHoare(int* a, int left, int right) { // 选择第一个元素作为pivotkey int pivotkey a[left]; int low left - 1; int high right 1; while (true) { // 从左向右找第一个 pivotkey 的元素 do { low; } while (a[low] pivotkey); // 从右向左找第一个 pivotkey 的元素 do { high--; } while (a[high] pivotkey); // 如果相遇或交叉返回high if (low high) return high; // 把小的换到左边大的换到右边 Swap(a[low], a[high]); } } void QuickSortHoare(int* a, int left, int right) { if (left right) return; int pivoti PartitionHoare(a, left, right); QuickSortHoare(a, left, pivoti); QuickSortHoare(a, pivoti 1, right); }4.2.2 复杂度和稳定性^ 快速排序效率取决于基准值的选取如果每次选择的基准值恰巧都能将区间中元素分割成左右几乎相等的两部分快排的效率会达到最优整个递归过程展开近似一棵平衡二叉树。整体而言对每层序列进行划分为O(n)递归的深度为因此最好情况时间复杂度为O(nlogn)空间复杂度O(logn)^ 快速排序效率取决于基准值的选取如果每次选择的基准值恰巧是区间的最小值或最大值有序是就会快排的效率会达到最坏n个数据的区间被划分为n-1个和0个的子区间整体划分是一个 1到n的等差数列因此最坏情况时间复杂度为O()空间复杂度为O(n)^ 快速排序选取每个数为基准值的概率为则可以推导出平均时间复杂度的递推公式这个推导过程较为复杂需要用到一些概率论/离散数学/微积分等知识进行推导有兴趣的可以用AI或者看《算法导论》相关章节这里我给一个结论是快速排序的平均时间复杂度为O(nlogn)快速排序基本是同级中平均性能最优的排序^ 快速排序每次选取区间最左边或者最右边的值做基准值有序时一定会出现最坏情况所以我们可以针对性的优化一下: a. 三数取中每次取区间的最左边/最右边/中间位置的三个值中的中位数作为基准值这样有序场景就会瞬间变为最好情况 b. 随机选基准值每次单趟划分时利用随机函数在区间内随机选取一个值作为基准值^ 快速排序无法保持稳定性。如{22222}单趟划分以后相对顺序就乱了5. 归并排序5.1 思想及过程^ 归并的含义是将两个或两个以上的有序表合并成一个新的有序表。链表归并可以直接取结点下来归并数组归并则必须结束一个额外的数组空间归并归并后再拷贝回去1. begin1 和 begin2 分别指向a数组两段有序区间的开始位置i指向tmp数组的开始位置2. begin1 和 begin2位置的值比较取小相等取begin1)的值赋值到tmp[i]3. 不断重复2步骤直到其中一个区间结束最后把还没有结束的区间的值依次拷贝到tmp数组^ 如果一个数组分成两个子数组子数组有序了两个子数组归并一下整体就有序了那么如何让子数组有序呢我们类似快排用分治的思想即可不断递归划分数组直到子数组为1个直到区间时返回递归回退时进行归并。5.2 代码实现void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin end) return; int mid (begin end) / 2; // 递归划分[begin,min][mid1,bengin] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid1, end); int begin1 begin, end1 mid; int begin2 mid 1, end2 end; int i begin; while (begin1 end1 begin2 end2) { if (a[begin1 a[begin2]]) { // 加上 是为了保持稳定性 tmp[i] a[begin1]; } else { tmp[i] a[begin2]; } } // 剩下还没有结束的区间拷贝到tmp数组 while (begin1 end1) { tmp[i] a[begin1]; } while (begin2 end2) { tmp[i] a[begin2]; } // 归并到tmp区间的值拷贝回a原数组 memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc fail); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp NULL; }5.3 复杂度和稳定性^ 归并的过程两个有序子数组的时间复杂度为 O(n)。^ 和快速排序类似归并排序的递归调用过程也是一棵二叉平衡树。归并排序不存在最好和最差情况因为它划分是每次均分且数组数据分布不会影响它归并的复杂度所以归并排序整体累计层每层归并合计 O(n)则归并排序整体时间复杂度为 O(nlongn)。^ 归并排序的空间复杂度为 O(n)。^ 归并排序在归并比较相等时让前半区间的值先归并则可以保持稳定性。6. 计数排序6.1 思想及过程^ 计数排序是一种非比较型的整数排序算法。它的核心思想不是通过“比较”元素的大小来决定顺序。而是通过统计每个元素出现的次数直接计算出该元素在最终有序数组中的位置。^ 如下图所示遍历a数组a[i]值映射到count计数数组对应位置计数数组中的值是多少就是对count对应位置count[a[i]],这样a数组遍历完以后count数组就统计了a数组中值出现了几次。6.2 代码实现void CountSort(int* a, int n) { int min a[0], max a[0]; for (int i 1; i n; i) { if (a[i] min) min a[i]; if (a[i] max) max a[i]; } int range max - min 1; int* count (int*)calloc(range, sizeof(int)); if (count NULL) { perror(calloc fail); return; } // 统计元素次数 for (int i 0; i n; i) { count[a[i] - min]; } // count[i] 记录映射值x的个数 for (int i 1; i range; i) { // 当前位置等于前面次数的累加和 count[i] count[i - 1]; } int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc fail); return; } for (int i n - 1; i 0; i--) { tmp[count[a[i] - min] - 1] a[i]; count[a[i] - min]--; } memcpy(a, tmp, sizeof(int) * n); free(count); free(tmp); }8. 内部排序的总结