目录1.排序的概念2.插入排序2.1直接插入排序2.1.1核心思想及代码实现2.1.2复杂度和稳定性2.2折半插入排序2.2.1核心思想及代码实现2.2.2复杂度和稳定性2.3希尔排序2.3.1核心思想及代码展示2.3.2缩小增量方案2.3.3复杂度和稳定性3.选择排序3.1简单选择排序3.1.1核心思路及代码实现3.1.2复杂度和稳定性3.2堆排序3.2.1核心思想及代码实现3.2.2复杂度和稳定性4.交换排序4.1冒泡排序4.1.1核心思路及代码实现4.1.2复杂度和稳定性4.2快速排序4.2.1核心思想及代码实现4.2.2复杂度和稳定性5.归并排序5.1核心思想及代码实现5.2复杂度和稳定性6.计数排序6.1核心思想及代码实现6.2复杂度和稳定性1.排序的概念排序Sorting顾名思义就是将一组杂乱无章的“数据”记录按照某个特定的“关键字”Key重新排列成一个有序序列的过程。1.1 排序算法的评价指标时空复杂度稳定性相同值的元素排序后相对顺序是否保持不变。1.2内部排序和外部排序内部排序所有数据都能加载到内存中完成排序。内部排序关注如何让复杂度更低。外部排序数据量巨大如几十TB无法全部装入内存必须借助磁盘文件和多路归并分批次排序。外部排序关注如何使读写硬盘的次数更少。1.3排序过程动图网站Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgoComparison Sorting Visualization2.插入排序2.1直接插入排序2.1.1核心思想及代码实现将数组逻辑上分为两个区间左侧是有序区初始只有一个元素右侧是无序区剩下的元素。每轮循环抓牌从无序区取出第一个元素(key)挪位在有序区从后往前扫描把比key大的值往后移动一位插入当遇到第一个比key小或相等的元素时停止移动将key插入到这个元素后面的空位上代码实现void InserSort(int* a, int n) { // 外层循环控制有序区间的范围 // i 表示当前有序区间的最后一个元素下标初始时有序区间只有 a[0]即 i0 // 循环条件 i n-1确保要取出的 key a[end 1] 不会越界 for (int i 0;i n - 1;i) { int end i; int key a[end 1]; // 内层循环在有序区 [0, end] 中从后往前扫描 while (end 0) { if (key a[end])// 写成 keya[end] 会影响稳定性 { a[end 1] a[end]; end--; } else { // 如果 key a[end]说明找到了插入位置 break; } } // 1. 如果是 break 退出end 指向最后一个 key 的元素key 插入到 end1 // 2. 如果是 end -1 退出key 比所有元素都小插入到最前面所以这句代码不可以放到else里 a[end 1] key; }注意1.if (keya[end])//这句写成if (keya[end])会影响稳定性2.a[end 1] key;//这句代码不能写在else里否则当key 比所有元素都小时该句不执行2.1.2复杂度和稳定性时间复杂度最坏情况逆序如要排升序序列本身为降序时间复杂度为O(n^2)最好情况正序如要排升序序列本身为升序则时间复杂度为O(n)平均情况O(n^2)空间复杂度O(1)总结直接插入排序看序列的原始顺序当序列有序或接近有序时效率较高稳定性稳定2.2折半插入排序2.2.1核心思想及代码实现利用“已排序区间是有序的”这一特性将查找插入位置的过程从顺序查找改为折半查找二分查找从而减少了比较次数。代码实现#include stdio.h // 折半插入排序升序稳定 void binaryInsertionSort(int arr[], int n) { int i, j, left, right, mid, temp, pos; for (i 1; i n; i) { temp arr[i]; // 取出待插入元素 left 0; right i - 1; // 已排序区间的左右边界 // 1. 二分查找插入位置严格大于保证稳定性 while (left right) { mid (left right) / 2; if (arr[mid] temp) { right mid - 1; // 继续在左半部分找 } else { left mid 1; // 相等时向右找保证稳定 } } pos left; // 最终插入位置 // 2. 元素后移从 i-1 到 pos倒序移动 for (j i - 1; j pos; j--) { arr[j 1] arr[j]; } // 3. 插入元素 arr[pos] temp; } }2.2.2复杂度和稳定性时间复杂度折半插入排序减少了比较次数但移动次数不变因此总时间复杂度依然是O(n^2)稳定性稳定总结折半插入排序的优化效果有限2.3希尔排序2.3.1核心思想及代码展示希尔排序是直接插入排序的改进又称缩小增量排序预排序分组选定一个增量gap将相隔gap个位置的元素归为一组共分成gap组。组内插入对每一组分别进行直接插入排序。缩小增量将gap缩小重复上述分组排序过程。最后冲刺当gap 1时全体元素视为一组进行最后一次直接插入排序。此时数组已经基本有序因此最后一次的移动次数极少。代码实现void ShellSort(int* a, int n) { int gap n; while (gap 1)//采用下面的方法缩小增量这里就不能写 1否则会死循环 { //1.采用 gap gap/3 1 增量序列 gap gap / 3 1; // 2.外层循环遍历所有组的起始位置代表 gap 个不同的分组gap是几就有几组 for (int j 0;j gap;j) { // 3.内层循环对当前起始位置为 j 的这一组进行直接插入排序 for (int i j;i gap n;i gap) { int end i; int key a[end gap]; // 组内向前比较并移动将 key 插入到已排序的组内正确位置 while (end 0) { if (key a[end]) { a[end gap] a[end]; end - gap; } else { break; } } a[end gap] key; } } } }更简单的写法void ShellSort(int* a, int n) { int gap n; while (gap 1) { gap gap / 3 1; // 以下为交替处理所有组的插入排序等价于分组处理 for (int i 0;i gap n;i) { int end i; int key a[end gap]; while (end 0) { if (key a[end]) { a[end gap] a[end]; end - gap; } else { break; } } a[end gap] key; } } }2.3.2缩小增量方案方案增量生成公式时间复杂度优缺点Shell 增量gap gap / 2O(n^2)缺点1.增量序列不互质在变成 gap1之前奇数位置的元素和偶数位置的元素永远被隔离开。如果奇数位置全是小数偶数位置全是大数那么前几轮预排几乎没有作用2.所以最坏时间复杂度依然是O(n^2)Knuth 增量最常用d d / 3 1O(n^(3/2))优点增量之间互质跳跃更均匀预排序效果好公式简单工程实现友好。Sedgwick 增量9⋅4^i−9⋅2^i19⋅4^i−9⋅2^i1 和 4^i−3⋅2^i1最快缺点太复杂2.3.3复杂度和稳定性时间复杂度如上表稳定性不稳定。由于分组是跳跃式的相同元素可能被分到不同组中独立排序无法保证它们的相对顺序。3.选择排序3.1简单选择排序3.1.1核心思路及代码实现简单选择排序每次从待排序的序列中选出最小或最大的那个放到最前面。将数组分为已排序区左侧和未排序区右侧。每一轮从未排序区中找出最小元素的下标。将该最小元素与未排序区的第一个元素交换位置。已排序区扩大一位未排序区缩小一位。重复此过程直到所有元素排完。选择排序和插入排序的区别插入排序是“拿一张牌插入到已排好的牌堆中”选择排序是“在剩下的牌堆里翻出最小的那张直接放到牌堆末尾”。代码实现void SelectSort(int* a, int n) { // 外层循环控制已排序区的边界 // i 表示未排序区的第一个元素下标同时也是本轮要放置最小值的位置 // 只需执行 n-1 轮因为最后一个元素会自动就位 for (int i 0; i n - 1; i) { int min i; // 假设当前未排序区的第一个元素下标 i是最小值 // 内层循环在未排序区 [i, n-1] 中遍历找出真正最小值的下标 // j 从 i1 开始因为 a[i] 已经作为初始候选 for (int j i 1; j n; j) { // 如果发现更小的元素更新 min 为新的下标 if (a[j] a[min]) { min j; } } // 如果找到的最小值不是 a[i]即 min ! i则交换两者 // 如果 min i说明 a[i] 本身就是最小值无需交换节省操作 if (min ! i) { int tmp a[i]; a[i] a[min]; a[min] tmp; } } }3.1.2复杂度和稳定性时间复杂度无论数组是否有序每趟都需要去比较选出最小的数据比较次数恒为 n(n−1)/2所以时间复杂度为O(n^2)稳定性不稳定。如5 8 5 23.2堆排序3.2.1核心思想及代码实现升序建大堆降序建小堆这里排升序建堆将待排序数组重新排列构建成一个大堆。使堆顶元素成为全局最大值。排序将堆顶最大值与堆的最后一个元素交换此时最大值归位。将堆的大小减 1排除已归位的最大值并对新的堆顶执行向下调整使其重新变成大堆。重复上述过程直到堆中只剩 1 个元素排序完成。代码实现void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } //向下调整算法 void AdjustDown(int* a,int n,int parent) { int child parent * 2 1; while (child n)//没有孩子可以比较就结束 { //选出较大的孩子 if (child 1 n a[child] a[child 1]) { child; } if (a[parent] a[child]) { Swap(a[parent], a[child]); 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 (n - j 0) { Swap(a[0], a[n - j]); AdjustDown(a, n - j, 0); j; } }3.2.2复杂度和稳定性时间复杂度O(nlogn)稳定性不稳定。堆排序的交换是跳跃式的比如堆顶和堆尾交换可能跨越很长的距离打乱相同元素的相对顺序。4.交换排序4.1冒泡排序4.1.1核心思路及代码实现重复遍历数组依次比较相邻的两个元素如果顺序错误就交换直到整个数组有序。每一趟从数组开头开始依次比较相邻的两个元素a[j]和a[j1]。如果a[j] a[j1]升序就交换它们。经过第一趟最大值一定会“冒泡”到数组的最后一个位置。下一趟只需要遍历到倒数第二个位置因为最后一个已经最大了。重复n-1趟数组就有序了。代码实现void BubbleSort(int* a, int n) { // 1.外层循环控制排序的趟数 // 每排完一趟就有一个最大的数沉到末尾所以最多需要 n-1 趟 // 这里用 i 记录已经排好的元素个数i 从 0 开始 for (int i 0; i n - 1; i) { int flag 0; // 2.内层循环进行相邻元素的两两比较 // 因为末尾已经排好了 i 个元素所以内层只需要比较前 n-i-1 个 for (int j 0; j n - i - 1; j) { // 使用 而不是 保证了稳定性相等的元素不会交换位置 if (a[j] a[j 1]) { int tmp a[j]; a[j] a[j 1]; a[j 1] tmp; flag 1; } } // 3. 若没有发生交换说明已经有序 if (flag 0) break; } }4.1.2复杂度和稳定性时间复杂度最坏逆序序列比较次数为1到n-1的等差数列O(n^2)最好正序序列比较n-1次没有发生交换时间复杂度为O(n)稳定性if (a[j]a[j 1]); // 使用而不是时是稳定的相等的元素不会交换位置4.2快速排序4.2.1核心思想及代码实现采用分治思想在待排序任选一个元素作为基准值基准值左边比它小右边比它大升序然后对左右两边分别递归地重复这个过程直到子区间不能再划分。选基准Key从待排序区间中选出一个元素作为“基准值”pivot。分区Partition将区间内的元素重新排列使得所有比基准小的元素都在基准左边所有比基准大的元素都在基准右边。此时基准元素就已经归位了它就在最终排序后的正确位置上。递归分治对基准左边和右边的两个子区间分别递归地重复第1、2步直到子区间只剩一个元素整个数组就有序了。找基准值及分区1. 挖坑法挖坑将最左侧元素取出来作为基准值 pivot。此时这个位置就变成了一个“空坑”填左坑从右向左找小找到比 pivot 小的元素放到左边的坑里此时右边被挖的位置就形成了新的“空坑”。填右坑从左向右找大找到比 pivot 大的元素放到右边的坑里此时左边被挖的位置就形成了新的“空坑”。重复左右指针不断向中间移动交替“挖坑-填坑”。填回基准当左右指针相遇left right此时这个位置就是基准值的位置将其填入int PartitionDigHole(int* a, int left, int right) { // 1. 挖坑把最左边的元素挖出来 int pivot a[left]; // 2. 循环条件左右指针未相遇 while (left right) { // 3. 从右向左找小填左边的坑 while (left right a[right] pivot) { right--; } a[left] a[right]; // 4. 从左向右找大填右边的坑 while (left right a[left] pivot) { left; } a[right] a[left]; } // 5. 左右指针相遇left right把 pivot 放入最后的坑 a[left] pivot; // 返回基准值归位的下标 return left; }2. Lomuto法基准值假设选最右边的元素为基准值 pivot。prev指向小于基准值的最后一个元素。一开始指向区间最左侧的前一位,即 left-1cur从最左边开始向右找比基准值小的值与 prev 的下一个元素交换。终止当 cur 遍历到基准值的前一个位置即 right - 1时循环停止。此时prev 指向最后一个小于 pivot 的元素。归位最后将基准值交换到 prev 的下一个位置基准值完成归位。int PartitionLomuto(int* a, int left, int right) { // 1. pivoti 记录基准值的下标 // 2. cur 指向当前正在扫描的元素 // 3. prev 指向 小于基准区域的最后一个元素 int pivoti right; int cur left; int prev left - 1; // 4. 循环遍历区间 [left, right-1] while (cur right) { //后面这句防止自己和自己交换 if (a[cur] a[pivoti] prev ! cur) { int tmp a[cur]; a[cur] a[prev]; a[prev] tmp; } cur; } // 5. 循环结束将基准值a[pivoti]交换到 prev 1 位置 int tmp a[pivoti]; a[pivoti] a[prev]; a[prev] tmp; return prev; }代码实现void QuickSort(int* a, int left, int right) { // 当左边界 右边界时说明当前区间无效或只有一个元素 // 情况1left right区间内只有1个元素天然有序直接返回 // 情况2left right区间为空比如基准在左边界时左子区间为空直接返回 if (left right) return; // 调用分区函数 // 作用选取基准值并将区间内元素重新排列使得 // 1. a[pivotkeyi] 已经是最终排序后的正确元素基准归位 // 2. [left, pivotkeyi-1] 范围内的所有元素都 基准值 // 3. [pivotkeyi1, right] 范围内的所有元素都 基准值 // 返回值基准值最终归位的数组下标即分界点 int pivotkeyi PartitionDigHole(a, left, right); //int pivotkeyi PartitionLomuto(a, left, right); //递归排序左右子区间 QuickSort(a, left, pivotkeyi - 1); QuickSort(a, pivotkeyi 1, right); }每轮排序的核心是先通过分区操作使基准值归位确定其最终下标将当前区间拆分为左右两个子区间然后递归地对这两个子区间反复执行相同的归位操作层层缩小待排序范围直至所有子区间都不可再分元素个数为 0 或 1。当所有子区间均递归有序时整个数组就有序了。总结快速排序本质上就是逐个让基准值归位的过程。4.2.2复杂度和稳定性时间复杂度最坏时间复杂度快排效率取决于基准值的选取如果每次选的基准都是最大或最小值快排的效率达到最坏时间复杂度为O(n^2)平均时间复杂度O(nlogn)空间复杂度O(logn)递归调用栈的深度对应二叉树的高度稳定性不稳定 。分区过程中存在跨距离交换。比如 1 1 1 15.归并排序5.1核心思想及代码实现归并排序是将两个或两个以上的有序表 合成一个新的有序表的过程。链表可以尾插归并数组则要开辟辅助数组进行排序。分解将待排序数组从中间一分为二分成左右两个子数组。解决递归地对左右两个子数组分别进行归并排序直到子数组长度为 1天然有序。合并将两个已经有序的子数组合并成一个更大的有序数组需要借助额外的辅助数组。注意写代码时注意控制细节与快排的区别快排的划分是按“值”基准左边小、右边大归并的划分是按“位置”直接取中间下标。快排在“合并”阶段啥都不用干原地归位归并在“合并”阶段需要干大量的搬移工作。代码实现// 归并排序的子函数 // begin 当前区间左边界闭区间 // end 当前区间右边界闭区间 void _Merge(int* a, int begin, int end, int* tmp) { // 1.当区间内没有元素或只剩一个元素时天然有序直接返回 if (begin end) return; // 2.分解 int mid (begin end) / 2; // 将当前区间分为[ begin, mid],[ mid1, end] // 不能划分为 [begin, mid - 1],[mid, end] 否则会死循环 int begin1 begin, end1 mid; int begin2 mid 1, end2 end; // 3.解决 // 注意这里必须先递归排完左右两边再执行合并。 // 只有左右子区间内部都有序了下面的二路归并才有意义。 _Merge(a, begin1, end1, tmp); _Merge(a, begin2, end2, tmp); // 4.归并 // 此时左子区间[begin1, end1] 和右子区间[begin2, end2] 已各自有序 // 要将这两个有序数组合并成一个大的有序数组暂存到 tmp 中 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]; } // 5.拷贝到原数组 for (int j begin; j end; j) { a[j] tmp[j]; } } void MergeSort(int* a, int n) { // 申请辅助空间 int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc); return; } // 调用递归子函数从整个数组区间 [0, n-1] 开始归并 _Merge(a, 0, n - 1, tmp); // 别忘了释放 free(tmp); tmp NULL; }5.2复杂度和稳定性时间复杂度O(nlogn),无论数组是否有序递归树高度永远是 log⁡n每层合并总耗时都是 O(n)。空间复杂度O(n),需要额外的临时数组 tmp 来存放合并结果。稳定性让前半区间的值先归并可以保证稳定性。(if (a[begin1]a[begin2]) //保证稳定性)6.计数排序6.1核心思想及代码实现计数排序利用数组下标来定位置而不是通过比较来决定顺序。使用前提数据跨度不能太大数据必须为整数思路需要用到3个数组原数组 a计数数组 count辅助数组 tmp统计遍历原始数组以“当前元素值减去最小值”作为索引在计数数组count的对应位置上进行自增操作记录每个不同元素值出现的总次数。累加从计数数组的第一个元素开始依次执行累加操作。此时count[ i ] 的含义不再代表频次而是代表原始数组中所有小于等于当前值的元素个数。反向填充逆序遍历原数组从最后一个元素开始向前遍历。采用逆序填放是为了保证当遇到重复元素时原数组中靠后的元素仍然放置在输出数组靠后的位置从而维持算法的稳定性。代码实现void CountSort(int* a, int n) { // 防止传入空指针或长度为0的数组避免后续访问越界 if (n 0) return; // 1.找出数据的极值确定范围 // 初始化 min 和 max 为第一个元素 int i 0; int min a[i], max a[i]; // 遍历整个数组找出实际的最小值和最大值 for (i 1; i n; i) { if (min a[i]) min a[i]; if (max a[i]) max a[i]; } // 2.开辟计数数组 // 计算数值跨度闭区间元素个数例如 [10, 19] 的 range 19-101 10 int range max - min 1; int* count (int*)calloc(range, sizeof(int));// calloc 会将所有元素初始化为 0 if (count NULL) { perror(calloc); return; } // 3.统计频率 for (i 0; i n; i) { count[a[i] - min]; // 该位置计数加1 } // 4.开辟辅助数组用于存放排序结果 int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc); free(count); return; } // 5.前缀和累加 // 累加后count[i] 代表 小于等于该值的元素总个数即右边界排位 for (i 1; i range; i) { count[i] count[i - 1]; } // 6。反向填充确保稳定性 for (i n - 1; i 0; i--) { // 1. 计算当前值对应的下标 idx a[i] - min // 2. 获取该值的排位 count[idx]减1后作为数组下标 // 3. 放置数据并将 count[idx] 自减1 tmp[count[a[i] - min] - 1] a[i]; count[a[i] - min]--; } // 7.拷贝回原数组 for (i 0; i n; i) { a[i] tmp[i]; } free(tmp); tmp NULL; free(count); count NULL; }6.2复杂度和稳定性时间复杂度假设n是数据个数range是数据范围则时间复杂度为O(nrange)若range接近于n,则时间复杂度为O(n)空间复杂度O(nrange)。稳定性稳定。因为反向遍历原数组