C语言数据结构排序算法详解上从插入排序、希尔排序到选择排序、堆排序 星恒随风个人主页❄️ 个人专栏《指针合集》《C语言基础》《数据结构》《机器学习导论》《前端基础》✨ 数据即知识压缩即智能目录前言一、排序是什么二、为什么排序这么重要三、排序算法应该从哪些维度分析四、常见排序算法分类五、插入排序像整理扑克牌一样排序六、直接插入排序的代码实现七、直接插入排序的复杂度与稳定性八、希尔排序对插入排序的一次升级九、希尔排序的代码实现十、希尔排序的复杂度与稳定性十一、选择排序每一轮选出最小值十二、直接选择排序的代码实现十三、直接选择排序的复杂度与稳定性十四、堆排序用堆结构优化选择过程十五、堆排序为什么升序要建大堆十六、堆排序的代码实现十七、堆排序的复杂度与稳定性上篇总结前言排序是数据结构与算法里非常基础、也非常重要的一章。我们平时写代码时经常会遇到这类需求按成绩从高到低排列学生按价格从低到高展示商品按时间顺序显示消息按热度展示文章、视频或商品按字典序排列字符串在海量数据中找 Top K这些需求背后都离不开排序。所谓排序简单说就是把一组数据按照某个关键字的大小重新排列成递增或递减的顺序。比如原数组53816升序排序后13568降序排序后86531一、排序是什么排序就是让一组记录按照关键字有序排列。这里有两个关键词记录关键字比如学生信息姓名年龄成绩张三1892李四1985王五1892赵六2078每一行就是一条记录。如果按成绩排序那么“成绩”就是关键字。如果按年龄排序那么“年龄”就是关键字。所以排序不一定只是排整数数组它也可以排结构体、对象、字符串、文件记录等。二、为什么排序这么重要排序看起来只是把数据排一下但它的意义很大。1. 排序可以让数据更容易查找如果数组是无序的查找一个元素通常要从头扫到尾。但如果数组有序就可以使用二分查找。二分查找的时间复杂度是O(logN)这比顺序查找的 O(N) 快很多。2. 排序可以让数据更容易展示电商网站经常会提供排序功能综合排序销量排序价格升序价格降序好评优先上架时间排序这些本质上都是根据不同关键字进行排序。3. 排序经常是其他算法的前置步骤很多算法都会先排序再处理。比如去重双指针区间合并贪心算法Top K 问题中位数问题统计排名排序不是孤立存在的它经常是解决复杂问题的第一步。三、排序算法应该从哪些维度分析学习排序算法时不建议只背代码。更重要的是理解每种排序的特点。通常从下面几个维度分析。1. 时间复杂度时间复杂度关注数据规模变大以后算法执行次数如何增长。常见排序复杂度有复杂度代表算法O(N²)插入排序、选择排序、冒泡排序O(NlogN)堆排序、快速排序、归并排序O(N 范围)计数排序2. 空间复杂度空间复杂度关注算法执行过程中额外占用多少空间。比如插入排序O(1)选择排序O(1)堆排序O(1)快速排序平均 O(logN)归并排序O(N)计数排序O(范围)3. 稳定性稳定性是排序里一个非常容易被忽略但很重要的概念。假设有两条记录关键字相同。排序前顺序姓名分数1张三902李四90如果排序后张三仍然在李四前面那么这个排序过程对这两个相同关键字的记录保持了相对顺序。这种排序算法叫稳定排序如果排序后李四跑到张三前面了那么就是不稳定排序稳定性在结构体排序、多关键字排序中非常有用。比如先按姓名排序再按成绩排序如果第二次排序是稳定的就能在成绩相同的时候保留第一次排序的结果。4. 是否原地排序如果排序过程中只使用常数级额外空间一般称为原地排序。比如插入排序选择排序冒泡排序堆排序它们基本都属于原地排序。归并排序通常需要额外数组因此不是典型原地排序。5. 是否基于比较大多数排序算法都是通过比较两个元素大小来排序。比如插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序这些都属于比较排序。计数排序则不是单纯依靠比较而是通过统计元素出现次数完成排序。四、常见排序算法分类常见排序算法可以按思想分成几类。类型代表算法核心思想插入排序直接插入排序、希尔排序把数据插入到已有序区间选择排序直接选择排序、堆排序每轮选择最小值或最大值交换排序冒泡排序、快速排序通过交换把元素放到正确区域归并排序归并排序分治先分解再合并非比较排序计数排序统计次数再回收数据这篇上篇先讲插入类和选择类排序。五、插入排序像整理扑克牌一样排序直接插入排序是最容易理解的排序之一。它的思想很像我们整理扑克牌。假设你手里已经有几张排好序的牌。现在新摸到一张牌你要把它插入到合适位置。比如你手里已有35912新摸到7你会从右往左看发现 9 和 12 都比 7 大于是它们往后挪。最后把 7 插到 5 和 9 中间357912这就是插入排序的思想。直接插入排序的基本过程给定数组下标01234数据53816插入排序会默认第一个元素已经有序。然后从第二个元素开始依次插入前面的有序区间。第一轮把 3 插入[5]结果| 数据 | 3 | 5 | 8 | 1 | 6 |第二轮把 8 插入[3, 5]8 已经比 5 大不需要移动。结果| 数据 | 3 | 5 | 8 | 1 | 6 |第三轮把 1 插入[3, 5, 8]3、5、8 都比 1 大全部后移。结果| 数据 | 1 | 3 | 5 | 8 | 6 |第四轮把 6 插入[1, 3, 5, 8]8 后移6 插入 5 后面。结果| 数据 | 1 | 3 | 5 | 6 | 8 |六、直接插入排序的代码实现voidInsertSort(int*a,intn){for(inti0;in-1;i){intendi;inttmpa[end1];while(end0){if(a[end]tmp){a[end1]a[end];end--;}else{break;}}a[end1]tmp;}}代码解读外层循环中i表示当前有序区间的最后一个位置。也就是说[0, i]是已经排好序的区域i 1是即将插入的元素intendi;inttmpa[end1];tmp保存待插入元素。为什么要先保存因为后面元素后移时a[end 1]这个位置会被覆盖。while 循环在做什么while(end0){if(a[end]tmp){a[end1]a[end];end--;}else{break;}}这段逻辑表示如果前面的元素比tmp大就往后挪如果前面的元素不比tmp大说明找到插入位置了最后a[end1]tmp;把tmp放到正确位置。七、直接插入排序的复杂度与稳定性1. 时间复杂度直接插入排序的最坏情况是逆序。比如数据54321每插入一个元素都要把前面的元素整体后移。所以最坏时间复杂度是O(N²)最好情况是数组本来就有序。比如数据12345每次比较一次就结束时间复杂度接近O(N)平均时间复杂度通常看作O(N²)2. 空间复杂度直接插入排序只使用了少量临时变量O(1)3. 稳定性直接插入排序是稳定的。关键在于这句判断if(a[end]tmp)只有当前元素严格大于tmp才后移。如果两个元素相等不会移动前面的相等元素。因此相等元素的相对顺序不会改变。4. 直接插入排序适合什么场景它适合数据规模较小数据基本有序对稳定性有要求想要实现简单实际开发中很多高级排序在处理小区间时也会切换到插入排序因为小规模数据下插入排序常数小、实现简单、效果不错。八、希尔排序对插入排序的一次升级希尔排序也叫缩小增量排序。它是对直接插入排序的优化。直接插入排序有一个明显问题如果一个很小的数在数组最后面它只能一步一步往前挪效率很低。比如数据987654321如果用直接插入排序1 要从最后一路往前挪到最前面。希尔排序的想法是先让数据大致有序再进行最后一次直接插入排序。它通过 gap 分组来实现这个目标。什么是 gapgap 可以理解成间隔。比如数组下标012345678数据912574863如果 gap 3那么分组方式是组别下标第 1 组036第 2 组147第 3 组258每组内部做插入排序。然后 gap 缩小比如gap 3gap 1当 gap 1 时就是普通直接插入排序。但是此时数组已经比较接近有序插入排序会快很多。九、希尔排序的代码实现voidShellSort(int*a,intn){intgapn;while(gap1){gapgap/31;for(inti0;in-gap;i){intendi;inttmpa[endgap];while(end0){if(a[end]tmp){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;}}}代码解读gapgap/31;这句用于逐步缩小 gap。它保证最后一次 gap 一定会变成 1。当 gap 1 时是预排序。当 gap 1 时是直接插入排序。希尔排序和插入排序的关系如果把直接插入排序看作相邻元素之间进行插入调整那么希尔排序就是间隔为 gap 的元素之间进行插入调整当 gap 慢慢缩小到 1 时数据整体已经接近有序。所以最后一轮会很快。十、希尔排序的复杂度与稳定性1. 时间复杂度希尔排序的时间复杂度和 gap 的取法有关。不同增量序列会得到不同复杂度。在基础学习阶段可以记住希尔排序通常明显优于直接插入排序复杂度不容易精确统一常见教材中通常给出介于 O(N^1.3) 到 O(N²) 之间的分析实际性能通常比 O(N²) 排序好很多2. 空间复杂度希尔排序仍然只使用少量临时变量O(1)3. 稳定性希尔排序是不稳定的。原因是它会让相隔 gap 的元素进行交换或移动。相等元素可能被分到不同组里经过多轮 gap 调整后相对顺序可能发生变化。4. 希尔排序适合什么场景希尔排序适合希望在插入排序基础上提升性能数据规模中等不强制要求稳定性想写一个代码不复杂但比 O(N²) 排序快很多的算法十一、选择排序每一轮选出最小值选择排序的思想非常直接每一轮从未排序区间中选出最小值放到当前区间最前面。比如数组数据53816第一轮从所有元素中选出最小值 1放到第 0 个位置数据13856第二轮从下标 1 到末尾选出最小值 3放到第 1 个位置数据13856第三轮从下标 2 到末尾选出最小值 5放到第 2 个位置数据13586继续进行最终有序。十二、直接选择排序的代码实现普通写法是每轮只找最小值。这里给出一个稍微优化的写法每一轮同时找最小值和最大值把它们分别放到区间两端。这样每轮可以确定两个位置。voidSwap(int*p1,int*p2){inttmp*p1;*p1*p2;*p2tmp;}voidSelectSort(int*a,intn){intbegin0;intendn-1;while(beginend){intminibegin;intmaxibegin;for(intibegin1;iend;i){if(a[i]a[mini]){minii;}if(a[i]a[maxi]){maxii;}}Swap(a[begin],a[mini]);if(maxibegin){maximini;}Swap(a[end],a[maxi]);begin;end--;}}为什么要处理maxi begin这段代码很关键if(maxibegin){maximini;}因为第一步会把最小值交换到begin位置。如果最大值原本就在begin那么最大值会被换到mini的位置。所以后面交换最大值前需要修正maxi。否则会把错误位置的数据换到末尾。十三、直接选择排序的复杂度与稳定性1. 时间复杂度选择排序无论数组是否有序都要完整扫描未排序区间来找最小值。所以时间复杂度始终是O(N²)它不像插入排序那样在接近有序时变快。2. 空间复杂度只使用少量临时变量O(1)3. 稳定性直接选择排序是不稳定的。举个例子原始顺序5a5b3第一轮选择最小值 3与第一个位置 5a 交换排序后局部35b5a原来 5a 在 5b 前面现在 5a 跑到了 5b 后面。所以选择排序不稳定。4. 选择排序适合什么场景选择排序思路简单但效率不高。它适合教学理解数据规模很小不要求稳定性想理解“选择最值”的排序思想实际开发中很少直接使用选择排序。十四、堆排序用堆结构优化选择过程堆排序本质上也是选择排序的一种。直接选择排序每一轮都要线性扫描找最大值或最小值。堆排序则用堆结构来提高选数效率。堆是一种特殊的完全二叉树。它通常用数组存储。什么是大堆和小堆大堆每个父结点都大于等于它的孩子结点。因此堆顶是最大值。小堆每个父结点都小于等于它的孩子结点。因此堆顶是最小值。堆的数组下标关系如果某个结点下标是parent那么关系下标左孩子parent * 2 1右孩子parent * 2 2父结点(child - 1) / 2这组公式来自完全二叉树的顺序存储。十五、堆排序为什么升序要建大堆很多初学者会问我要排升序为什么不建小堆反而要建大堆原因在于堆排序通常是在原数组上进行排序。如果排升序我们希望最大值最终放到数组末尾。大堆的堆顶正好是最大值。操作流程建大堆让最大值在堆顶交换堆顶和数组最后一个元素最大值被放到最终位置对剩余元素继续向下调整重复这个过程所以升序建大堆。如果排降序就建小堆。堆排序过程示意假设我们有数组数据53816升序堆排序先建大堆堆顶是最大值 8将 8 交换到数组末尾剩余区间继续调整成大堆再把当前最大值放到倒数第二个位置重复直到有序它的核心是每次把当前未排序区间中的最大值放到最终位置。十六、堆排序的代码实现1. 向下调整向下调整的前提是左右子树已经是堆只有根结点可能不满足堆规则。voidAdjustDown(int*a,intn,intparent){intchildparent*21;while(childn){if(child1na[child1]a[child]){child;}if(a[child]a[parent]){Swap(a[child],a[parent]);parentchild;childparent*21;}else{break;}}}这里实现的是大堆向下调整。关键逻辑先找到左右孩子中较大的那个如果孩子大于父亲就交换交换后继续向下调整2. 堆排序完整实现voidHeapSort(int*a,intn){for(inti(n-2)/2;i0;i--){AdjustDown(a,n,i);}intendn-1;while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}}代码分两步第一步建堆。for(inti(n-2)/2;i0;i--){AdjustDown(a,n,i);}为什么从(n - 2) / 2开始因为它是最后一个非叶子结点。叶子结点本身就可以看成一个堆不需要调整。第二步排序。while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}每次把堆顶最大值交换到末尾。然后对剩余区间继续调整成大堆。十七、堆排序的复杂度与稳定性1. 时间复杂度堆排序主要分两步阶段时间复杂度建堆O(N)依次选出最大值O(NlogN)所以整体时间复杂度是O(NlogN)2. 空间复杂度堆排序可以在原数组上完成只使用少量变量O(1)3. 稳定性堆排序是不稳定的。因为堆排序过程中会频繁交换堆顶和末尾元素相等元素的相对顺序可能被打乱。4. 堆排序适合什么场景堆排序适合希望最坏时间复杂度仍然是 O(NlogN)希望空间复杂度是 O(1)不要求稳定性需要理解 Top K、优先级队列、堆结构不过实际工程中堆排序的常数因素和缓存局部性不一定优于快速排序因此很多场景中快排更常见。但堆排序在理论上非常稳因为它没有快排那种最坏 O(N²) 的退化问题。上篇总结上篇主要讲了四类排序中的两大类插入类排序选择类排序其中包括直接插入排序希尔排序直接选择排序堆排序1. 直接插入排序核心思想把待插入元素放入前面的有序区间。特点维度结论时间复杂度O(N²)最好可接近 O(N)空间复杂度O(1)稳定性稳定适合场景小数据、基本有序数据2. 希尔排序核心思想先按 gap 分组预排序再进行最终插入排序。特点维度结论时间复杂度与 gap 取法有关通常优于 O(N²) 排序空间复杂度O(1)稳定性不稳定适合场景中等规模数据、不要求稳定性3. 直接选择排序核心思想每一轮从未排序区间选择最小值或最大值。特点维度结论时间复杂度O(N²)空间复杂度O(1)稳定性不稳定适合场景教学理解、数据量很小4. 堆排序核心思想利用堆结构反复选择最大值或最小值。特点维度结论时间复杂度O(NlogN)空间复杂度O(1)稳定性不稳定适合场景需要稳定最坏复杂度、空间要求较低
C语言数据结构排序算法详解（上）：从插入排序、希尔排序到选择排序、堆排序
C语言数据结构排序算法详解上从插入排序、希尔排序到选择排序、堆排序 星恒随风个人主页❄️ 个人专栏《指针合集》《C语言基础》《数据结构》《机器学习导论》《前端基础》✨ 数据即知识压缩即智能目录前言一、排序是什么二、为什么排序这么重要三、排序算法应该从哪些维度分析四、常见排序算法分类五、插入排序像整理扑克牌一样排序六、直接插入排序的代码实现七、直接插入排序的复杂度与稳定性八、希尔排序对插入排序的一次升级九、希尔排序的代码实现十、希尔排序的复杂度与稳定性十一、选择排序每一轮选出最小值十二、直接选择排序的代码实现十三、直接选择排序的复杂度与稳定性十四、堆排序用堆结构优化选择过程十五、堆排序为什么升序要建大堆十六、堆排序的代码实现十七、堆排序的复杂度与稳定性上篇总结前言排序是数据结构与算法里非常基础、也非常重要的一章。我们平时写代码时经常会遇到这类需求按成绩从高到低排列学生按价格从低到高展示商品按时间顺序显示消息按热度展示文章、视频或商品按字典序排列字符串在海量数据中找 Top K这些需求背后都离不开排序。所谓排序简单说就是把一组数据按照某个关键字的大小重新排列成递增或递减的顺序。比如原数组53816升序排序后13568降序排序后86531一、排序是什么排序就是让一组记录按照关键字有序排列。这里有两个关键词记录关键字比如学生信息姓名年龄成绩张三1892李四1985王五1892赵六2078每一行就是一条记录。如果按成绩排序那么“成绩”就是关键字。如果按年龄排序那么“年龄”就是关键字。所以排序不一定只是排整数数组它也可以排结构体、对象、字符串、文件记录等。二、为什么排序这么重要排序看起来只是把数据排一下但它的意义很大。1. 排序可以让数据更容易查找如果数组是无序的查找一个元素通常要从头扫到尾。但如果数组有序就可以使用二分查找。二分查找的时间复杂度是O(logN)这比顺序查找的 O(N) 快很多。2. 排序可以让数据更容易展示电商网站经常会提供排序功能综合排序销量排序价格升序价格降序好评优先上架时间排序这些本质上都是根据不同关键字进行排序。3. 排序经常是其他算法的前置步骤很多算法都会先排序再处理。比如去重双指针区间合并贪心算法Top K 问题中位数问题统计排名排序不是孤立存在的它经常是解决复杂问题的第一步。三、排序算法应该从哪些维度分析学习排序算法时不建议只背代码。更重要的是理解每种排序的特点。通常从下面几个维度分析。1. 时间复杂度时间复杂度关注数据规模变大以后算法执行次数如何增长。常见排序复杂度有复杂度代表算法O(N²)插入排序、选择排序、冒泡排序O(NlogN)堆排序、快速排序、归并排序O(N 范围)计数排序2. 空间复杂度空间复杂度关注算法执行过程中额外占用多少空间。比如插入排序O(1)选择排序O(1)堆排序O(1)快速排序平均 O(logN)归并排序O(N)计数排序O(范围)3. 稳定性稳定性是排序里一个非常容易被忽略但很重要的概念。假设有两条记录关键字相同。排序前顺序姓名分数1张三902李四90如果排序后张三仍然在李四前面那么这个排序过程对这两个相同关键字的记录保持了相对顺序。这种排序算法叫稳定排序如果排序后李四跑到张三前面了那么就是不稳定排序稳定性在结构体排序、多关键字排序中非常有用。比如先按姓名排序再按成绩排序如果第二次排序是稳定的就能在成绩相同的时候保留第一次排序的结果。4. 是否原地排序如果排序过程中只使用常数级额外空间一般称为原地排序。比如插入排序选择排序冒泡排序堆排序它们基本都属于原地排序。归并排序通常需要额外数组因此不是典型原地排序。5. 是否基于比较大多数排序算法都是通过比较两个元素大小来排序。比如插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序这些都属于比较排序。计数排序则不是单纯依靠比较而是通过统计元素出现次数完成排序。四、常见排序算法分类常见排序算法可以按思想分成几类。类型代表算法核心思想插入排序直接插入排序、希尔排序把数据插入到已有序区间选择排序直接选择排序、堆排序每轮选择最小值或最大值交换排序冒泡排序、快速排序通过交换把元素放到正确区域归并排序归并排序分治先分解再合并非比较排序计数排序统计次数再回收数据这篇上篇先讲插入类和选择类排序。五、插入排序像整理扑克牌一样排序直接插入排序是最容易理解的排序之一。它的思想很像我们整理扑克牌。假设你手里已经有几张排好序的牌。现在新摸到一张牌你要把它插入到合适位置。比如你手里已有35912新摸到7你会从右往左看发现 9 和 12 都比 7 大于是它们往后挪。最后把 7 插到 5 和 9 中间357912这就是插入排序的思想。直接插入排序的基本过程给定数组下标01234数据53816插入排序会默认第一个元素已经有序。然后从第二个元素开始依次插入前面的有序区间。第一轮把 3 插入[5]结果| 数据 | 3 | 5 | 8 | 1 | 6 |第二轮把 8 插入[3, 5]8 已经比 5 大不需要移动。结果| 数据 | 3 | 5 | 8 | 1 | 6 |第三轮把 1 插入[3, 5, 8]3、5、8 都比 1 大全部后移。结果| 数据 | 1 | 3 | 5 | 8 | 6 |第四轮把 6 插入[1, 3, 5, 8]8 后移6 插入 5 后面。结果| 数据 | 1 | 3 | 5 | 6 | 8 |六、直接插入排序的代码实现voidInsertSort(int*a,intn){for(inti0;in-1;i){intendi;inttmpa[end1];while(end0){if(a[end]tmp){a[end1]a[end];end--;}else{break;}}a[end1]tmp;}}代码解读外层循环中i表示当前有序区间的最后一个位置。也就是说[0, i]是已经排好序的区域i 1是即将插入的元素intendi;inttmpa[end1];tmp保存待插入元素。为什么要先保存因为后面元素后移时a[end 1]这个位置会被覆盖。while 循环在做什么while(end0){if(a[end]tmp){a[end1]a[end];end--;}else{break;}}这段逻辑表示如果前面的元素比tmp大就往后挪如果前面的元素不比tmp大说明找到插入位置了最后a[end1]tmp;把tmp放到正确位置。七、直接插入排序的复杂度与稳定性1. 时间复杂度直接插入排序的最坏情况是逆序。比如数据54321每插入一个元素都要把前面的元素整体后移。所以最坏时间复杂度是O(N²)最好情况是数组本来就有序。比如数据12345每次比较一次就结束时间复杂度接近O(N)平均时间复杂度通常看作O(N²)2. 空间复杂度直接插入排序只使用了少量临时变量O(1)3. 稳定性直接插入排序是稳定的。关键在于这句判断if(a[end]tmp)只有当前元素严格大于tmp才后移。如果两个元素相等不会移动前面的相等元素。因此相等元素的相对顺序不会改变。4. 直接插入排序适合什么场景它适合数据规模较小数据基本有序对稳定性有要求想要实现简单实际开发中很多高级排序在处理小区间时也会切换到插入排序因为小规模数据下插入排序常数小、实现简单、效果不错。八、希尔排序对插入排序的一次升级希尔排序也叫缩小增量排序。它是对直接插入排序的优化。直接插入排序有一个明显问题如果一个很小的数在数组最后面它只能一步一步往前挪效率很低。比如数据987654321如果用直接插入排序1 要从最后一路往前挪到最前面。希尔排序的想法是先让数据大致有序再进行最后一次直接插入排序。它通过 gap 分组来实现这个目标。什么是 gapgap 可以理解成间隔。比如数组下标012345678数据912574863如果 gap 3那么分组方式是组别下标第 1 组036第 2 组147第 3 组258每组内部做插入排序。然后 gap 缩小比如gap 3gap 1当 gap 1 时就是普通直接插入排序。但是此时数组已经比较接近有序插入排序会快很多。九、希尔排序的代码实现voidShellSort(int*a,intn){intgapn;while(gap1){gapgap/31;for(inti0;in-gap;i){intendi;inttmpa[endgap];while(end0){if(a[end]tmp){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;}}}代码解读gapgap/31;这句用于逐步缩小 gap。它保证最后一次 gap 一定会变成 1。当 gap 1 时是预排序。当 gap 1 时是直接插入排序。希尔排序和插入排序的关系如果把直接插入排序看作相邻元素之间进行插入调整那么希尔排序就是间隔为 gap 的元素之间进行插入调整当 gap 慢慢缩小到 1 时数据整体已经接近有序。所以最后一轮会很快。十、希尔排序的复杂度与稳定性1. 时间复杂度希尔排序的时间复杂度和 gap 的取法有关。不同增量序列会得到不同复杂度。在基础学习阶段可以记住希尔排序通常明显优于直接插入排序复杂度不容易精确统一常见教材中通常给出介于 O(N^1.3) 到 O(N²) 之间的分析实际性能通常比 O(N²) 排序好很多2. 空间复杂度希尔排序仍然只使用少量临时变量O(1)3. 稳定性希尔排序是不稳定的。原因是它会让相隔 gap 的元素进行交换或移动。相等元素可能被分到不同组里经过多轮 gap 调整后相对顺序可能发生变化。4. 希尔排序适合什么场景希尔排序适合希望在插入排序基础上提升性能数据规模中等不强制要求稳定性想写一个代码不复杂但比 O(N²) 排序快很多的算法十一、选择排序每一轮选出最小值选择排序的思想非常直接每一轮从未排序区间中选出最小值放到当前区间最前面。比如数组数据53816第一轮从所有元素中选出最小值 1放到第 0 个位置数据13856第二轮从下标 1 到末尾选出最小值 3放到第 1 个位置数据13856第三轮从下标 2 到末尾选出最小值 5放到第 2 个位置数据13586继续进行最终有序。十二、直接选择排序的代码实现普通写法是每轮只找最小值。这里给出一个稍微优化的写法每一轮同时找最小值和最大值把它们分别放到区间两端。这样每轮可以确定两个位置。voidSwap(int*p1,int*p2){inttmp*p1;*p1*p2;*p2tmp;}voidSelectSort(int*a,intn){intbegin0;intendn-1;while(beginend){intminibegin;intmaxibegin;for(intibegin1;iend;i){if(a[i]a[mini]){minii;}if(a[i]a[maxi]){maxii;}}Swap(a[begin],a[mini]);if(maxibegin){maximini;}Swap(a[end],a[maxi]);begin;end--;}}为什么要处理maxi begin这段代码很关键if(maxibegin){maximini;}因为第一步会把最小值交换到begin位置。如果最大值原本就在begin那么最大值会被换到mini的位置。所以后面交换最大值前需要修正maxi。否则会把错误位置的数据换到末尾。十三、直接选择排序的复杂度与稳定性1. 时间复杂度选择排序无论数组是否有序都要完整扫描未排序区间来找最小值。所以时间复杂度始终是O(N²)它不像插入排序那样在接近有序时变快。2. 空间复杂度只使用少量临时变量O(1)3. 稳定性直接选择排序是不稳定的。举个例子原始顺序5a5b3第一轮选择最小值 3与第一个位置 5a 交换排序后局部35b5a原来 5a 在 5b 前面现在 5a 跑到了 5b 后面。所以选择排序不稳定。4. 选择排序适合什么场景选择排序思路简单但效率不高。它适合教学理解数据规模很小不要求稳定性想理解“选择最值”的排序思想实际开发中很少直接使用选择排序。十四、堆排序用堆结构优化选择过程堆排序本质上也是选择排序的一种。直接选择排序每一轮都要线性扫描找最大值或最小值。堆排序则用堆结构来提高选数效率。堆是一种特殊的完全二叉树。它通常用数组存储。什么是大堆和小堆大堆每个父结点都大于等于它的孩子结点。因此堆顶是最大值。小堆每个父结点都小于等于它的孩子结点。因此堆顶是最小值。堆的数组下标关系如果某个结点下标是parent那么关系下标左孩子parent * 2 1右孩子parent * 2 2父结点(child - 1) / 2这组公式来自完全二叉树的顺序存储。十五、堆排序为什么升序要建大堆很多初学者会问我要排升序为什么不建小堆反而要建大堆原因在于堆排序通常是在原数组上进行排序。如果排升序我们希望最大值最终放到数组末尾。大堆的堆顶正好是最大值。操作流程建大堆让最大值在堆顶交换堆顶和数组最后一个元素最大值被放到最终位置对剩余元素继续向下调整重复这个过程所以升序建大堆。如果排降序就建小堆。堆排序过程示意假设我们有数组数据53816升序堆排序先建大堆堆顶是最大值 8将 8 交换到数组末尾剩余区间继续调整成大堆再把当前最大值放到倒数第二个位置重复直到有序它的核心是每次把当前未排序区间中的最大值放到最终位置。十六、堆排序的代码实现1. 向下调整向下调整的前提是左右子树已经是堆只有根结点可能不满足堆规则。voidAdjustDown(int*a,intn,intparent){intchildparent*21;while(childn){if(child1na[child1]a[child]){child;}if(a[child]a[parent]){Swap(a[child],a[parent]);parentchild;childparent*21;}else{break;}}}这里实现的是大堆向下调整。关键逻辑先找到左右孩子中较大的那个如果孩子大于父亲就交换交换后继续向下调整2. 堆排序完整实现voidHeapSort(int*a,intn){for(inti(n-2)/2;i0;i--){AdjustDown(a,n,i);}intendn-1;while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}}代码分两步第一步建堆。for(inti(n-2)/2;i0;i--){AdjustDown(a,n,i);}为什么从(n - 2) / 2开始因为它是最后一个非叶子结点。叶子结点本身就可以看成一个堆不需要调整。第二步排序。while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}每次把堆顶最大值交换到末尾。然后对剩余区间继续调整成大堆。十七、堆排序的复杂度与稳定性1. 时间复杂度堆排序主要分两步阶段时间复杂度建堆O(N)依次选出最大值O(NlogN)所以整体时间复杂度是O(NlogN)2. 空间复杂度堆排序可以在原数组上完成只使用少量变量O(1)3. 稳定性堆排序是不稳定的。因为堆排序过程中会频繁交换堆顶和末尾元素相等元素的相对顺序可能被打乱。4. 堆排序适合什么场景堆排序适合希望最坏时间复杂度仍然是 O(NlogN)希望空间复杂度是 O(1)不要求稳定性需要理解 Top K、优先级队列、堆结构不过实际工程中堆排序的常数因素和缓存局部性不一定优于快速排序因此很多场景中快排更常见。但堆排序在理论上非常稳因为它没有快排那种最坏 O(N²) 的退化问题。上篇总结上篇主要讲了四类排序中的两大类插入类排序选择类排序其中包括直接插入排序希尔排序直接选择排序堆排序1. 直接插入排序核心思想把待插入元素放入前面的有序区间。特点维度结论时间复杂度O(N²)最好可接近 O(N)空间复杂度O(1)稳定性稳定适合场景小数据、基本有序数据2. 希尔排序核心思想先按 gap 分组预排序再进行最终插入排序。特点维度结论时间复杂度与 gap 取法有关通常优于 O(N²) 排序空间复杂度O(1)稳定性不稳定适合场景中等规模数据、不要求稳定性3. 直接选择排序核心思想每一轮从未排序区间选择最小值或最大值。特点维度结论时间复杂度O(N²)空间复杂度O(1)稳定性不稳定适合场景教学理解、数据量很小4. 堆排序核心思想利用堆结构反复选择最大值或最小值。特点维度结论时间复杂度O(NlogN)空间复杂度O(1)稳定性不稳定适合场景需要稳定最坏复杂度、空间要求较低
