C语言数据结构——排序算法详解

C语言数据结构——排序算法详解排序是数据结构中非常重要的一类操作核心目标是按照关键字将一组数据按照递增或递减顺序重新排列常见排序算法包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序不同算法在时间复杂度、空间复杂度、稳定性以及适用场景方面存在明显差异文章目录C语言数据结构——排序算法详解一、排序基础1、排序的概念1.1 排序的定义1.2 排序的稳定性1.3 内部排序1.4 外部排序二、插入排序1、直接插入排序1.1 基本思想1.2 排序过程1.3 基本代码框架1.4 复杂度与稳定性2、希尔排序2.1 基本思想2.2 gap 的作用2.3 希尔排序的过程2.4 代码框架2.5 复杂度与稳定性三、选择排序1、直接选择排序1.1 基本思想1.2 排序过程1.3 代码框架1.4 复杂度与稳定性四、堆排序1、基本思想2、升序与降序2.1 升序2.2 降序3、向下调整4、复杂度与稳定性五、交换排序1、基本思想六、冒泡排序1、基本思想2、代码框架3、复杂度与稳定性七、快速排序1、基本思想2、快速排序递归框架八、快速排序的三种常见划分方法1、Hoare版本2、挖坑法3、前后指针法九、快速排序优化1、三数取中法2、小区间使用插入排序十、快速排序非递归实现1、基本思想2、快速排序复杂度十一、归并排序1、基本思想2、归并操作3、归并排序的核心结构4、归并排序的复杂度5、归并排序与外部排序十二、计数排序1、基本思想2、基本步骤2.1 统计次数2.2 根据次数回收数据3、适用条件4、复杂度与稳定性十三、排序算法复杂度与稳定性1、常见排序算法对比2、稳定排序3、不稳定排序十四、排序算法的选择1、数据基本有序2、追求较好的综合性能3、要求额外空间较少4、要求稳定5、数据范围集中十五、常见排序接口十六、排序算法核心关系1、按照思想分类2、核心思想对比十七、排序中的关键复杂度1、O(N²) 排序2、O(N logN) 排序3、非比较排序十八、排序算法实际选择思路十九、总结一、排序基础1、排序的概念1.1 排序的定义排序就是根据记录中某个或某些关键字的大小将一组记录按照递增或递减顺序重新排列例如原序列 5 2 8 1 6 升序 1 2 5 6 8 降序 8 6 5 2 1其中用于比较大小的数据称为关键字1.2 排序的稳定性假设待排序序列中存在多个关键字相同的记录如果排序完成后这些关键字相同的记录之间的相对次序保持不变则称该排序算法是稳定的例如排序前 A(20) B(10) C(20) D(30)按照关键字从小到大排序B(10) A(20) C(20) D(30)其中A和C的关键字相同排序前A在C前面排序后仍然保持A在C前面因此这种排序是稳定的如果排序后变成B(10) C(20) A(20) D(30)那么A和C的相对位置发生改变此时排序算法是不稳定的稳定性只关注关键字相同元素之间的相对顺序1.3 内部排序内部排序是指排序过程中所有数据元素都能够同时存放在内存中完成排序常见的插入排序、选择排序、堆排序、快速排序、归并排序等都可以进行内部排序1.4 外部排序外部排序用于数据量过大的情况当数据无法一次性全部放入内存时需要根据排序过程不断在内存和外部存储之间移动数据归并排序尤其适合解决外部排序相关问题二、插入排序1、直接插入排序1.1 基本思想直接插入排序的核心思想是将待排序元素逐个插入到前面已经有序的序列中类似于打扑克牌时整理手中的牌例如原序列 5 3 4 1 2开始时可以认为第一个元素5已经有序5 | 3 4 1 2将3插入到5前面3 5 | 4 1 2再将4插入3 4 5 | 1 2继续处理1 3 4 5 | 2最终1 2 3 4 51.2 排序过程当处理第i个元素时a[0] ~ a[i-1]已经处于有序状态此时将a[i]与前面的元素从后往前进行比较如果前面的元素大于当前元素就将前面的元素向后移动直到找到合适的位置再将当前元素插入1.3 基本代码框架voidInsertSort(int*a,intn){for(inti1;in;i){intendi-1;inttmpa[i];while(end0a[end]tmp){a[end1]a[end];--end;}a[end1]tmp;}}1.4 复杂度与稳定性项目结果最好时间复杂度O(N)最坏时间复杂度O(N²)空间复杂度O(1)稳定性稳定直接插入排序具有一个非常明显的特点数据越接近有序排序效率越高因此当数据基本有序时直接插入排序的性能非常好2、希尔排序2.1 基本思想希尔排序又称为缩小增量排序希尔排序可以看作是对直接插入排序的优化直接插入排序一次只能处理相邻元素而希尔排序通过设置gap让距离较远的元素先进行比较和调整2.2gap的作用例如gap 3可以按照下标间隔3将元素分组a[0] a[3] a[6] a[9] a[1] a[4] a[7] a[10] a[2] a[5] a[8] a[11]分别对这些分组进行插入排序完成后缩小gap最终gap 1此时对整个数组进行一次直接插入排序2.3 希尔排序的过程希尔排序可以分为两个阶段gap 1 ↓ 预排序 ↓ 数组逐渐接近有序 ↓ gap 1 ↓ 直接插入排序当gap 1时主要目的是让数组快速接近有序当gap 1时数组已经比较接近有序此时直接插入排序效率较高2.4 代码框架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;}}}2.5 复杂度与稳定性希尔排序的时间复杂度与gap的取值方式有关不同增量序列会产生不同的复杂度因此不能简单地用一个固定的时间复杂度表示所有希尔排序实现其特点为是直接插入排序的优化gap 1时进行预排序gap 1时进行最终插入排序空间复杂度为O(1)不稳定三、选择排序1、直接选择排序1.1 基本思想直接选择排序的核心思想是每次从待排序区间中选择一个最小或最大的元素将其放到对应位置例如升序排序5 3 8 1 6第一轮寻找最小值1将1放到最前面1 3 8 5 6第二轮从剩余部分寻找最小值3继续进行直到所有元素有序1.2 排序过程假设当前处理区间为a[i] ~ a[n-1]在该区间中寻找最小元素如果最小元素不是a[i]就将它与a[i]交换然后继续处理a[i1] ~ a[n-1]直到只剩下一个元素1.3 代码框架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;}}1.4 复杂度与稳定性项目结果时间复杂度O(N²)空间复杂度O(1)稳定性不稳定直接选择排序的思想简单但是效率较低因此实际使用场景相对有限四、堆排序1、基本思想堆排序利用堆这种数据结构进行排序堆排序本质上属于选择排序核心思想是建立堆 ↓ 选择堆顶元素 ↓ 将堆顶元素放到最终位置 ↓ 调整剩余元素 ↓ 重复上述过程2、升序与降序堆排序中有一个非常重要的对应关系升序排序建立大堆降序排序建立小堆原因在于2.1 升序建立大堆后堆顶 最大值将最大值放到数组末尾不断重复后即可得到升序序列1 2 3 4 52.2 降序建立小堆后堆顶 最小值将最小值放到数组末尾不断重复后即可得到降序序列3、向下调整堆排序的核心操作之一是向下调整voidAdjustDown(int*a,intn,introot){intparentroot;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;}}}对于大堆父节点 子节点对于小堆父节点 子节点4、复杂度与稳定性项目结果时间复杂度O(N logN)空间复杂度O(1)稳定性不稳定相比直接选择排序堆排序通过堆结构提高了选择元素的效率五、交换排序1、基本思想交换排序根据两个记录关键字的比较结果决定是否交换两个记录的位置总体思想可以概括为较大的元素逐渐向后移动 较小的元素逐渐向前移动常见的交换排序包括冒泡排序快速排序六、冒泡排序1、基本思想冒泡排序通过不断比较相邻元素并在顺序错误时进行交换使较大的元素逐渐向后移动例如5 3 4 1 2第一轮3 4 1 2 5最大值5被移动到了末尾第二轮3 1 2 4 5继续进行最终得到1 2 3 4 52、代码框架voidBubbleSort(int*a,intn){for(intendn-1;end0;--end){intexchange0;for(inti0;iend;i){if(a[i]a[i1]){Swap(a[i],a[i1]);exchange1;}}if(exchange0)break;}}其中exchange用来判断当前一轮是否发生交换如果一轮排序中完全没有发生交换说明整个序列已经有序可以提前结束3、复杂度与稳定性项目结果最好时间复杂度O(N)最坏时间复杂度O(N²)空间复杂度O(1)稳定性稳定冒泡排序非常容易理解但整体效率较低七、快速排序1、基本思想快速排序采用分治思想首先从待排序区间中选择一个元素作为基准值key然后通过一次划分将序列分成两部分左区间 基准值 右区间使得左区间中的元素 基准值 右区间中的元素 基准值然后分别对左右两个区间继续进行快速排序最终整个序列有序2、快速排序递归框架快速排序的整体结构可以概括为排序整个区间 ↓ 选择基准值 ↓ 进行区间划分 ↓ 得到左右两个子区间 ↓ 递归排序左区间 ↓ 递归排序右区间代码框架voidQuickSort(int*a,intleft,intright){if(right-left1)return;intdivPartSort(a,left,right);QuickSort(a,left,div);QuickSort(a,div1,right);}八、快速排序的三种常见划分方法1、Hoare版本Hoare 法通过左右指针不断向中间移动根据基准值寻找需要交换的元素基本过程选取基准值 ↓ left 从左向右寻找 right 从右向左寻找 ↓ 交换不符合要求的元素 ↓ 两个指针相遇 ↓ 完成一次划分2、挖坑法挖坑法的核心思想是先保存基准值 ↓ 形成一个坑 ↓ 从右侧寻找符合条件的元素填入坑中 ↓ 右侧形成新的坑 ↓ 再从左侧寻找元素填入 ↓ 不断重复这种方法本质上仍然是在围绕基准值完成一次区间划分3、前后指针法前后指针法通常设置两个指针prev cur通过两个指针之间的配合将小于基准值的元素逐渐移动到前面最终完成区间划分九、快速排序优化1、三数取中法快速排序性能与基准值key的选择密切相关如果每次都选择一个极端元素作为基准值最小值或者最大值就可能导致区间划分严重不均衡例如1 2 3 4 5 6 7 8如果每次都选择最小值作为基准1 | 2 3 4 5 6 7 8 ↓ 2 | 3 4 5 6 7 8 ↓ 3 | 4 5 6 7 8此时递归结构非常不平衡快速排序会发生严重退化因此可以使用三数取中法选择更加合理的基准值2、小区间使用插入排序当快速排序递归到较小区间时可以考虑停止继续递归改用直接插入排序原因是小区间递归开销相对明显插入排序在小规模数据上的效率较好可以减少递归次数因此可以采用大区间 ↓ 快速排序 ↓ 小区间 ↓ 直接插入排序十、快速排序非递归实现1、基本思想递归快速排序本质上利用的是函数调用栈因此可以使用自己实现的栈来模拟递归过程基本过程将左右边界入栈 ↓ 取出一个区间 ↓ 完成一次划分 ↓ 得到左右两个子区间 ↓ 将子区间边界入栈 ↓ 继续处理代码框架voidQuickSortNonR(int*a,intleft,intright){Stack st;StackInit(st);StackPush(st,left);StackPush(st,right);while(!StackEmpty(st)){rightStackTop(st);StackPop(st);leftStackTop(st);StackPop(st);if(right-left1)continue;intdivPartSort(a,left,right);StackPush(st,div1);StackPush(st,right);StackPush(st,left);StackPush(st,div);}StackDestroy(st);}2、快速排序复杂度项目结果平均时间复杂度O(N logN)空间复杂度O(logN)稳定性不稳定快速排序整体综合性能较好因此在实际排序场景中具有较高的使用价值十一、归并排序1、基本思想归并排序同样采用分治思想核心思路是先让子序列有序再将多个有序子序列合并成一个完整的有序序列例如8 4 5 7 1 3 6 2不断划分8 4 5 7 1 3 6 2继续划分8 4 5 7 1 3 6 2最终划分到单个元素8 | 4 | 5 | 7 | 1 | 3 | 6 | 2然后不断进行有序合并4 8 5 7 1 3 2 6继续合并4 5 7 8 1 2 3 6最终1 2 3 4 5 6 7 82、归并操作两个已经有序的序列A1 4 7 B2 3 8分别使用两个指针A - 1 B - 2比较两个指针指向的元素将较小元素放入临时数组最终1 2 3 4 7 83、归并排序的核心结构分解 ↓ 将数组拆成左右两个部分 ↓ 递归排序左半部分 ↓ 递归排序右半部分 ↓ 合并两个有序区间归并排序的核心就在于合并两个有序区间4、归并排序的复杂度项目结果时间复杂度O(N logN)空间复杂度O(N)稳定性稳定归并排序最大的特点之一就是需要额外的O(N)辅助空间5、归并排序与外部排序归并排序非常适合处理数据量较大的排序问题当数据无法一次全部装入内存时可以将数据划分为多个有序部分再逐步进行归并因此归并排序在外部排序场景中具有重要作用十二、计数排序1、基本思想计数排序属于非比较排序其核心思想不是通过元素之间不断比较大小来完成排序而是统计每个数据出现的次数例如原数组 1 3 2 1 3 3 2统计1 → 2次 2 → 2次 3 → 3次然后根据统计结果重新生成有序序列1 1 2 2 3 3 32、基本步骤计数排序主要分为两个步骤2.1 统计次数统计每一个关键字出现的次数数据值 出现次数 1 2 2 2 3 32.2 根据次数回收数据按照关键字从小到大的顺序根据统计次数重新放回原数组1 1 2 2 3 3 33、适用条件计数排序在数据范围比较集中时效率较高例如10 11 12 12 13 14 15数据范围较小适合使用计数排序如果数据范围非常大1 100000000即使只有两个数据也可能需要处理一个非常大的范围此时计数排序的空间消耗会明显增加因此计数排序的适用范围存在一定限制4、复杂度与稳定性项目结果时间复杂度O(MAX(N, 范围))空间复杂度O(范围)稳定性稳定十三、排序算法复杂度与稳定性1、常见排序算法对比排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(N)O(N²)O(N²)O(1)稳定希尔排序与增量有关与增量有关与增量有关O(1)不稳定直接选择排序O(N²)O(N²)O(N²)O(1)不稳定堆排序O(N logN)O(N logN)O(N logN)O(1)不稳定冒泡排序O(N)O(N²)O(N²)O(1)稳定快速排序O(N logN)O(N logN)会发生退化O(logN)不稳定归并排序O(N logN)O(N logN)O(N logN)O(N)稳定计数排序O(MAX(N,范围))O(MAX(N,范围))O(MAX(N,范围))O(范围)稳定2、稳定排序常见稳定排序包括直接插入排序冒泡排序归并排序计数排序稳定排序的关键在于关键字相同 ↓ 排序前后的相对顺序不发生改变3、不稳定排序常见不稳定排序包括希尔排序直接选择排序堆排序快速排序判断稳定性时不能只看最终结果而要考虑关键字相同元素在排序过程中是否可能发生相对位置变化十四、排序算法的选择1、数据基本有序当数据已经比较接近有序时直接插入排序通常具有较好的效率冒泡排序也可以利用提前结束进行一定程度的优化2、追求较好的综合性能快速排序通常具有较好的综合性能可以通过三数取中 小区间使用插入排序进一步优化3、要求额外空间较少可以考虑堆排序其空间复杂度为O(1)4、要求稳定可以选择直接插入排序 冒泡排序 归并排序 计数排序具体还需要结合数据规模和数据特征进行选择5、数据范围集中当数据范围较小并且比较集中时可以考虑计数排序其时间复杂度与数据规模以及数据范围有关而不是单纯依赖元素之间的比较次数十五、常见排序接口常见排序函数接口可以统一设计为// 插入排序voidInsertSort(int*a,intn);// 希尔排序voidShellSort(int*a,intn);// 选择排序voidSelectSort(int*a,intn);// 堆排序voidHeapSort(int*a,intn);// 冒泡排序voidBubbleSort(int*a,intn);// 快速排序voidQuickSort(int*a,intleft,intright);// 快速排序非递归实现voidQuickSortNonR(int*a,intleft,intright);// 归并排序voidMergeSort(int*a,intn);// 归并排序非递归实现voidMergeSortNonR(int*a,intn);// 计数排序voidCountSort(int*a,intn);其中快速排序的区间通常需要额外传入left right因为快速排序本质上是在不断处理不同的子区间十六、排序算法核心关系1、按照思想分类排序 ├── 插入排序 │ ├── 直接插入排序 │ └── 希尔排序 │ ├── 选择排序 │ ├── 直接选择排序 │ └── 堆排序 │ ├── 交换排序 │ ├── 冒泡排序 │ └── 快速排序 │ ├── 归并排序 │ └── 非比较排序 └── 计数排序2、核心思想对比算法核心思想直接插入排序将元素插入前面的有序区间希尔排序通过gap进行预排序直接选择排序每次选择最小或最大元素堆排序利用堆高效选择元素冒泡排序不断交换相邻元素快速排序基准值划分 分治归并排序分治 有序区间合并计数排序统计元素出现次数十七、排序中的关键复杂度1、O(N²)排序常见的有直接插入排序 直接选择排序 冒泡排序其中直接插入排序和冒泡排序在数据基本有序时可以获得较好的实际表现2、O(N logN)排序常见的有堆排序 快速排序 归并排序其中堆排序空间复杂度较低快速排序综合性能较好但存在退化情况归并排序时间复杂度稳定但需要额外的O(N)空间3、非比较排序计数排序不依赖元素之间逐个比较大小而是利用数据范围进行统计因此在适合的场景下可以获得较高效率但对数据范围存在要求十八、排序算法实际选择思路可以按照下面的思路进行选择数据是否基本有序 │ ├── 是 → 直接插入排序 │ └── 否 │ ├── 数据范围集中 → 计数排序 │ ├── 要求稳定 → 归并排序 │ ├── 追求综合性能 → 快速排序 │ └── 要求较低额外空间 → 堆排序实际使用时还需要结合数据规模数据分布是否要求稳定是否允许额外空间最坏情况要求实现复杂度进行综合选择十九、总结排序的核心是按照关键字重新排列数据常见排序算法可以从思想上分为插入 选择 交换 归并 非比较其中需要重点掌握直接插入排序简单数据基本有序时效率较高希尔排序通过gap对插入排序进行优化直接选择排序思想简单但时间复杂度较高堆排序O(N logN)空间复杂度O(1)冒泡排序实现简单且稳定快速排序分治思想综合性能较好归并排序O(N logN)且稳定但需要O(N)额外空间计数排序适合数据范围集中的场景理解各种排序算法时重点关注排序思想、区间变化、时间复杂度、空间复杂度以及稳定性