教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本文以 6 Sort/README.md 为骨架系统梳理排序稳定性的定义、比较排序与线性排序两大阵营的复杂度边界并对冒泡、选择、插入、希尔、快排、归并、堆排序七种经典算法逐一拆解原理、步骤与代码实现同时结合仓库源码 insert_sort.c 中六种排序的完整 C 实现、8.c 的双层循环示例以及 堆.md 的堆结构细节给出可直接运行、可对照验证的实战素材。读完本文你将能准确说出每种排序的稳定性、时间复杂度与适用场景并能对照源码理解快排挖坑填数、归并后序合并、堆排序建堆-交换-调整等关键机制的底层实现。一、排序的稳定性一句话判定的核心概念排序的稳定性是指对于相等的元素排序之后依然保持这两个元素原来的相对位置没有变就是稳定排序反之如果相等元素的相对次序在排序过程中可能发生改变就是不稳定排序。稳定性是工程选型中常被忽略、但实际很重要的属性——例如在对对象数组按多个关键字先后排序时先按主键排再按次键排只有稳定排序才能保证次键排序不会打乱主键已有的相对顺序。后续各节我们会在讲解每个算法时依据其元素移动机制判断稳定性凡是只在相邻位置交换、且相等时不交换的算法冒泡、插入、归并通常稳定凡是会跨越一段距离交换元素的算法选择、快排、希尔、堆排序通常不稳定。二、排序算法总览与复杂度边界按交换与移动策略的不同经典排序大致可分为两类交换排序算法冒泡排序、选择排序、快速排序、归并排序、插入排序、希尔排序、堆排序线性排序算法桶排序不基于元素两两比较。一个关键的复杂度结论常见的排序算法都是比较排序比较排序的时间复杂度通常为 O(n²) 或 O(nlogn)。而排序算法的总复杂度由比较的次数和交换的次数一起决定——这也是为什么同样 O(n²) 量级的算法实际耗时可能相差数倍见文末源码实测基准。另外如果待排序的数字具有一些特殊性例如取值范围有限、分布均匀我们可以据此设计出更优化的非比较排序突破 O(nlogn) 的比较排序下限桶排序就是典型代表。三、交换排序之冒泡排序Bubble Sort核心思想每轮确定一个最大的数排到末尾。相邻的 2 个元素比较大的向后移经过一轮比较最大的元素排在最后第二轮第二大的元素排到倒数第二个位置直到全部排好。这样即使是已经排好序的数组用冒泡排序来排比较次数依然不变比较的时间复杂度仍为 O(n²)。仓库 insert_sort.c 中的实现如下void bubble_sort(int *a, int length){ int tmp ; for (int i 0; i length-1; i) // 第i轮排序 { for (int j 0; j length-i; j) { if (a[j] a[j1]) { tmp a[j]; a[j] a[j1]; a[j1] tmp; } } } }从源码结构看内层循环条件写成j length-i当i 0时会访问到a[length]这一越界位置实际使用时建议将内层条件收紧为j length-i-1这也是经典冒泡写法的常见边界细节。由于冒泡只交换相邻且严格大于的元素相等元素不会互换位置因此冒泡排序是稳定的。四、交换排序之快速排序Quick Sort4.1 原理与复杂度快速排序是对冒泡排序的改进本质是一种划分交换排序。其时间复杂度平均为O(nlogn)最坏为O(n²)例如每次划分都极端不平衡时。快速排序的思维可以浓缩为一句话递归一次pivot 左边都比它小右边都比它大这是递归、分治的思想。它天然对应二叉树的前序遍历思路——先处理根划分出 pivot 的位置再递归处理左右子树左右子区间。4.2 分治三步曲对数组 A[p...r] 而言选择基准选择最后一个元素作为 pivot基准分解划分出 A[p..q-1] 与 A[q1..r]使得 A[p...q-1] A[q] A[q1..r]解决递归调用快排对子数组 A[p..q-1]、A[q1..r] 分别排序合并因为子问题相互独立无需额外合并操作直接分治即可。具体步骤为先从数列中选择一个元素作为基准 pivot通常取分区的最后一个→ 重排数列比 pivot 小的排左边比 pivot 大的排右边相等的放哪边都可以一句话概括就是挖坑填数→ 递归地用相同方式重排左右两边的子序列。4.3 C 语言实现递归框架 挖坑填数扫描过程分为两种挖坑排序两头向中间扫描先从后向前找再从前向后找与单向扫描。仓库文档与 insert_sort.c 中采用的是前者void quicksort(int *a, int left, int right){ if (leftright) // 递归结束条件否则会死循环造成堆栈溢出 { int i partion(a,left,right); // 使得局部有序i作为分隔 quicksort(a,left,i-1); quicksort(a,i1,right); } } // 挖坑填数2边向中间扫描 int partion(int *a, int start,int end){ int istart,jend; int tmp a[i]; // 这里要做越界检查 while(ij){ // 从后向前扫描找到第一个小于tmp的值来填a[i] while(ij a[j]tmp){ j--; } if (ij) // 找到了这时候a[j]为坑 { a[i] a[j]; } // 从左向右扫描找一个大于 tmp 的 数 去填坑a[j] while(ij a[i]tmp){ i; } if (ij) { a[j]a[i]; } } // 扫描完成后ij a[i]tmp; return i; }关键点在于基准值tmp先被挖出来形成坑然后右侧小于它的元素填到左侧坑位左侧大于它的元素填到右侧坑位来回往复直到i j最后把tmp填回这个位置——该位置即 pivot 的最终下标同时天然把区间一分为二。4.4 Java 实现左右指针技巧当 pivot 选择尾部节点时代码写起来更简单、移动元素更方便。仓库文档给出了另一种用左右指针完成的partition// pivot 选择 尾部节点 代码写起来更加简单 移动元素更方便 // 左右指针技巧 static int partition(int[] nums, int left, int right){ int pivot nums[right];//选尾部节点作为 pivot int end right; right--; while (left right) { if (nums[left] pivot) { left ; //左边指针 窗口变小 continue; } //元素比 pivot 大右边指针 窗口变小 //swap left right swap(nums, left, right); right--; } // 跟 pivot 元素置换 int i 0; if (nums[left] pivot) { //swap left1 pivot i left 1; } else {//swap left pivot i left ; } swap(nums, i, end); return i; }这种写法把比 pivot 小的留在左边比 pivot 大的与右边指针交换作为不变式维护最终只需一次置换即可把 pivot 放到正确位置。快速排序动图来自 qsort.gif直观展示了挖坑填数 分治递归的完整过程由于快排的元素交换是跨越式的挖坑/交换会跨越中间位置相等元素的相对顺序无法保证因此快速排序是不稳定排序。五、交换排序之归并排序Merge Sort5.1 原理分治算法必然用到递归归并排序是典型的分治算法divide-and-conquer必然用到递归。它的核心洞察是2 个有序数组的合并操作是 O(n) 的复杂度。因此我们可以把无序数组分成 2 个子数组分别排序然后再 merge依次类推。归并排序的步骤分解将一个数组分成 n/2 个子数组每个序列 2 个元素2 路归并解决将各个子数组都排好序然后 merge 2 个有序数组合并。从遍历顺序看归并排序套用的是二叉树的后序遍历思路——先递归排左右后序位置之前再在后序遍历位置执行合并void sort(int[] nums, int low, int high) { int mid (low high) / 2; sort(nums, low, mid); sort(nums, mid 1, high); /****** 后序遍历位置 ******/ // 合并两个排好序的子数组 merge(nums, low, mid, high); /************************/ } //合并两个有序数组 从前往后merge public void merge(int[] arr,int low,int mid,int high,int[] tmp){ int i 0; int j low,k mid1; //左边序列和右边序列起始索引 while(j mid k high){ if(arr[j] arr[k]){ tmp[i] arr[j]; }else{ tmp[i] arr[k]; } } //若左边序列还有剩余则将其全部拷贝进tmp[]中 while(j mid){ tmp[i] arr[j]; } while(k high){ tmp[i] arr[k]; } for(int t0;ti;t){ arr[lowt] tmp[t]; } }5.2 仓库 C 实现临时数组版 mergeinsert_sort.c 中的 C 版本思路一致合并时分配临时空间装载结果最后拷贝回原数组并释放临时空间// 合并2个有序数组,分配一个临时空间装ab的结果最后将合并结果拷贝到数组A释放临时空间 void merge_array(int *a,int size_a,int *b, int size_b){ int *tmp malloc( (size_asize_b)*sizeof(int) ); int i,j,k; ijk0; while(isize_a jsize_b){ tmp[k] (a[i]b[j])?b[j]:a[i]; } while(isize_a){ tmp[k]a[i]; } while(jsize_b){ tmp[k]b[j]; } for (int p 0; p k; p) { a[p] tmp[p]; } free(tmp); } void merge_sort(int *a, int length){ if (length1) { merge_sort(a,length/2); merge_sort(alength/2,length-length/2); merge_array(a,length/2,alength/2,length-length/2); } }注意merge_array中三目表达式(a[i]b[j])?b[j]:a[i]的含义谁小取谁取完即推进对应指针剩下的两个while负责把某一侧剩余的尾巴一次性拷贝完——这正是合并两个有序数组 O(n)的全部逻辑。由于合并时相等元素取左侧子数组的元素归并排序是稳定的。归并排序动图mergesort.gif清晰展示了不断二分到底再逐层合并有序子数组的过程六、直接选择排序Selection Sort直接选择排序的思路非常简单从未排序的序列中选择最小的元素与放在第一个位置的元素交换依次类推直到全部排序完成。更形式化的表述是在a[i..n]中找到最小的元素与a[i]交换位置。其空间复杂度 O(1)时间复杂度 O(n²)。insert_sort.c 中的实现void select_sort(int *a,int length){ int min_index,tmp; int j; for (int i 0; i length; i) { for (j i1 ,min_indexi; j length; j) { if (a[min_index]a[j]) { min_indexj; } } //min_index是最小的元素的index if (min_index!i) { tmpa[i]; a[i]a[min_index]; a[min_index]tmp; } } }这里每次内层循环只做比较、记录min_index找到后再做一次交换把比较与交换分离。与之对应的双层循环骨架可以参见 8.c内层循环从i1开始遍历恰好刻画了选择排序每轮从剩余元素中找最小的扫描范围——比较次数为 n(n-1)/2这正是 O(n²) 的来源。动画演示见 selectsort.gif。由于最小元素是与a[i]跨越式交换相等元素的相对顺序可能被打乱因此选择排序是不稳定排序。七、插入排序Insertion Sort插入排序像整理扑克牌一样逐个将元素插入已排序区第一个元素算作已经排好取下一个元素从已经排好的序列中从后向前扫描如果排好序的元素大于新元素排好序的元素移到下一个位置重复第 3 步直到找到插入位置重复第 2 步。它的复杂度有两个极端最坏情况待排序的是逆序排放的数组每一轮都要移动元素复杂度为 O(n²)最好情况待排序的已是顺序排放的数字只需要做一轮比较就够了复杂度为 O(n)空间复杂度 O(1)。因此可以看到对大部分数据已经有序的数组排序使用插入排序非常有优势。这是它在工程中例如作为 TimSort 等混合排序的基础块依然重要的原因。insert_sort.c 中的实现void insert_sort(int *a,int length){ int tmp ; int i,j; for (i 1; i length; i) { for ( tmpa[i],ji-1 ; j0 a[j] tmp ; j--) { a[j1]a[j]; } // j1是插入的位置 a[j1]tmp; } }源码把取出待插入值tmp与从后向前移动大元素合并进内层循环条件只要前面的元素a[j] tmp就后移一位循环结束后j1就是tmp的最终落点。由于相等时a[j] tmp不会触发移动相对顺序得以保持插入排序是稳定的。八、希尔排序Shell Sort希尔排序是递减增量排序算法本质是对插入排序的改进也叫分组插入排序 / 缩小增量排序。它的奥秘在于前面插入排序的结论数据元素越有序使用插入排序效率越高。步骤先将待排数列分割成若干子序列增量为 m对每个子序列使用插入排序减小增量再排序最后对全体元素做一次插入排序。通过先宏观有序再微观有序希尔排序把插入排序的 O(n²) 最坏代价摊薄到接近 O(n^1.3) 量级具体取决于增量序列的选择动画演示见 shellsort.gif。由于分组跳跃式交换跨越了较远距离希尔排序是不稳定排序。九、堆排序Heap Sort9.1 堆结构前置知识堆排序是利用堆这种数据结构设计的一种排序算法。堆也叫优先队列、二叉堆的特性可参见 堆.md堆总是一颗完全二叉树使用数组作为存储结构因此也叫二叉堆任一节点小于或大于其所有的孩子节点根节点大于所有孩子节点的是大根堆根为最大值根节点小于所有孩子节点的是小根堆根为最小值因为是完全二叉树用数组存储时节点i的父节点索引为(i-1)/2左右子节点下标为2i1、2i2。堆的核心操作包括建堆、插入插到数组最后再调整、删除总是删除根节点 A[0]。9.2 堆排序步骤将待排序数列看作一颗完全二叉树的存储结构堆化数组结束后根 a[0] 变成最大值大根堆或最小值小根堆取走 a[0]然后对堆做删除操作堆会重新堆化数组a[0] 又成为下一个最大/最小。删除操作通常是先把数组最后的元素提到 a[0] 位置然后从根节点开始进行一次从上向下的调整调整时先从左右孩子中找最大/最小的交换如果父节点比每个孩子都大/小就不用调整。因此堆排序可以直接让 a[0] 与数组最后一个元素互换但要先保存好 a[0] 或 a[n-1]这也解释了为什么递增排序使用大根堆递减排序使用小根堆循环第 3 步即可按顺序取出所有元素。堆排序的主要时间花在建堆和堆化数组阶段找出数列中最大数只需要 O(1) 的时间复杂度。9.3 代码框架与仓库源码文档给出的堆排序框架如下void heap_sort(int *a, int length){ // 建立堆 大根堆递增排序 heap_build(a,length); for (int i length-1; i 0; --i) { //交换 heap_swop(a[0],a[i]); //调整 heap_adjust(a,i); } }insert_sort.c 中给出了完整的底层三件套核心是自顶向下调整//自顶向下调整 void heap_public_adjust(int *a,int parent,int length){ // 三个数里取最大的一个 a[i],a[2i1],a[2i2],跟a[i]交换然后是 a[(i-1)/2],a[i],a[i1] .. 一直到a[0] int max parent * 2 1; while(max length){ //三个数里取最大的一个 a[tmp],a[2tmp1],a[2tmp2] if (max 1 length a[max] a[max 1])// left right { max; } // 和最大孩子比 if (a[parent] a[max])// parent max(left, right) { break; } else { heap_swop(a[parent],a[max]); parent max; //继续向下, 比对, 交换, 保证所有树 父节点 子节点 max 2 * parent 1; } } } // 从第一个非叶子节点a[(length-2)/2]开始做调整... void heap_build(int *a,int length){ for (int i (length-2)/2; i 0 ; --i) { heap_public_adjust(a,i,length); } } void heap_adjust(int *a,int length){ heap_public_adjust(a,0,length); //对0号调整 }关键实现细节heap_build从第一个非叶子节点(length-2)/2开始逐个向上调整每次交换后把parent下移保证整条路径上父节点不小于孩子节点交换时仓库采用无临时变量的加减法技巧heap_swop。由于堆排序在交换 a[0] 与 a[i]以及堆化过程中会跨越式移动元素堆排序是不稳定排序。堆排序动画演示见 heapsort.gif可见建堆 → 交换堆顶 → 缩小堆再调整的循环另外堆排序还可以用来求 top-K 大小的问题具体思路固定容量为 k 的小根堆、遍历剩余元素动态替换参见 Top-K 问题.md。十、线性排序桶排序Bucket Sort上面的算法都是基于比较的排序时间复杂度最好也就是 O(nlogn)。而非基于比较的排序可以突破 O(nlogn) 的时间下限。当然非比较排序也需要有一些限定条件例如元素取值范围有限、分布已知。桶排序的思想用一个例子就能说明给全校学生做分数排序最大分 100 分。我们使用一个 100 个空间的辅助数组以 key 为分数、value 为命中的次数通过O(n) 复杂度就可以完成排序任务——这种排序方式就是桶排序。具体做法分配一个hash[100]的空间并初始化为 0遍历一遍数据出现的数字就hash[k]这样再次遍历一次 hash 数组就可以得到 n 个数的顺序了。它把比较大小换成了数值范围映射 计数代价是空间换时间且要求数值范围可枚举、不会太大。当数据分布呈现明显局部性比如分桶后桶内再用其他排序时桶排序还能进一步扩展出更精细的分桶策略。十一、排序动画演示对照仓库 6 Sort 目录下收录了一组排序动画可以先观察动画猜测算法再对照验证动画文件对应算法qsort.gif快速排序mergesort.gif归并排序heapsort.gif堆排序selectsort.gif选择排序bubblesort.gif冒泡排序shellsort.gif希尔排序十二、源码实测5000 个随机数的性能基准insert_sort.c 的main()中内置了一个可运行的自测基准生成 5000 个随机数rand() % 5000用clock()计时并依次注释切换各排序算法。作者在源码注释中记录了一次实测耗时不同机器与编译环境下结果会不同仅供参考算法实测耗时5000 个随机数归并排序merge_sort0.002s快速排序quicksort0.01s堆排序heap_sort未记录与快排同属 O(nlogn) 量级插入排序insert_sort3.85s选择排序select_sort5.3s冒泡排序bubble_sort12.5s同一份数据、同一个进程O(nlogn) 的算法与 O(n²) 的算法拉开了 34 个数量级的差距——这就是比较次数 交换次数共同决定排序成本的最直观证据。十三、小结一张表收束全局综合全文各算法的核心属性汇总如下稳定性依据实现机制推断相邻比较不跨越交换的为稳定算法平均/最好时间复杂度最坏时间复杂度空间复杂度稳定性关键特征冒泡排序O(n²)O(n²)O(1)稳定相邻交换每轮确定末尾最大数选择排序O(n²)O(n²)O(1)不稳定每轮选最小放前面插入排序O(n)近似有序时O(n²)O(1)稳定近似有序数据极具优势希尔排序约 O(n^1.3) 量级O(n²) 量级O(1)不稳定分组插入、缩小增量快速排序O(nlogn)O(n²)O(logn) 递归栈不稳定挖坑填数、前序分治归并排序O(nlogn)O(nlogn)O(n)稳定合并有序数组、后序分治堆排序O(nlogn)O(nlogn)O(1)不稳定建堆交换调整可解 top-K桶排序O(n)有前提—O(范围大小)—非比较排序突破 nlogn 下限核心结论可以概括为三条比较排序的复杂度下界是 O(nlogn)数据近似有序时优先插入排序数据取值范围有限时可考虑桶排序突破复杂度下界。希望这张表与源码的对应关系能帮助你在面试与工程实践中快速完成排序算法的选型与实现。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐排序算法稳定性应用Learn-Algorithms中的实际案例排序算法稳定性应用Learn Algorithms中的实际案例 排序算法稳定性Stability是指当待排序序列中存在相等元素时排序后这些元素的相对位置教程排序算法内存占用Learn-Algorithms中的空间复杂度排序算法内存占用Learn Algorithms中的空间复杂度 在处理大规模数据时排序算法的内存占用往往比时间效率更令人头疼。想象一下当你在嵌入式设备或内教程Hello 算法排序章小结七种经典排序算法的原理、优化与选型全解析Hello 算法排序章小结七种经典排序算法的原理、优化与选型全解析 本文基于《Hello 算法》排序章的小结文档 docs/chapter_sorting/教程文档示例工程教育上一篇如何在30分钟内用Dify工作流解决你的图片显示问题从新手到专家的完整指南下一篇gl-matrix移动端优化在移动设备上实现高性能计算创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考