C语言：排序（二）

目录1. 快速排序1.1 动态演示1.2 代码实现1.2.1 经典快排1.2.2 优化快排三数选中小区间优化1.2.3 双指针快排1.2.4 非递归快排栈实现2. 归并排序2.1 动态演示2.2 代码实现2.2.1 经典归并递归2.2.2 非递归归并循环实现3. 计数排序3.1 代码实现4. 总结1. 快速排序时间复杂度O( NlogN )空间复杂度O( logN )思想找一个基准值把比它小的放左边比它大的放右边然后左右两边递归重复这个过程。空间复杂度之所以不是O( 1 )是因为一般的快排都是通过递归实现的而递归就要不断建立和销毁函数栈帧因此也会消耗空间。常见问题和解答Q为什么快排需要先移动右指针A先移动right可以保证两个指针相遇时所指向的值是小于key的。最后一次移动分为两种情况一种是right找到了小于等于key的值left没有找到大于等于key的值不断移动直至与right相遇另一种是right没有找到小于等于key的值一直移动直至与left相遇但此时left位置的值已经在上次移动时交换了变为了比key小的值因此相遇点的值还是小于key的。Q为什么判断左右指针和key的大小时都要带等号A是为了让等于key的值均匀分布在数组中使递归更平衡。如果去掉等号所有等于key的值会堆积在数组一侧当数组元素相等时时间复杂度会退化至O(N^2)。举个例子如果一个数组全是1在左右指针都没有等号的情况下left和right都不会移动会导致死循环如果只有一侧有等号带等号的指针会一直移动直至与另一侧指针相遇这样会导致递归树极不平衡。因此加上等号可以显著改善这样的情况。1.1 动态演示快速排序1.2 代码实现1.2.1 经典快排思路选取指定区间最左侧元素为key设置两个指针从两端向中间会合保证相遇点左侧全部元素小于key右侧全部元素大于key然后交换key和相遇点元素以key为分割点对左右区间再次快排递归。//快速排序递归 void QuickSort1(int* a, int begin, int end) { //终止条件 if(begin end) return; //begin和end用于标记区间范围 //begin和end是在区间内移动的指针 int keyi begin; int left begin; int right end; while(left right) { //先移动右指针小于keyi就停下 while(left right a[right] a[keyi]) { right--; } //再移动左指针大于keyi就停下 while(left right a[left] a[keyi]) { left; } //交换两个指针的值 Swap(a[left], a[right]); } //当两指针重合时交换keyi和重合点更新keyi Swap(a[keyi], a[left]); keyi left; //继续递归 QuickSort1(a, begin, keyi - 1); QuickSort1(a, keyi 1, end); } //基础快排三数选中小区间优化递归 int GetMidi(int* a, int begin, int end) { int midi (begin end) / 2; if(a[begin] a[midi]) { if(a[end] a[midi]) { if(a[begin] a[end]) { return end; } else { return begin; } } else { return midi; } } else // a[begin] a[midi] { if(a[end] a[begin]) { if(a[end] a[midi]) { return midi; } else { return end; } } else { return begin; } } }1.2.2 优化快排三数选中小区间优化三数选中原因由于经典快排中每次选取区间最左侧元素作为key会导致递归不平衡可能会出现递归区间极小和极大的情况。因此通过三数选中可以尽量令key的大小落在区间的中心从而平衡递归区间。具体方案选取区间首尾和中间位置的元素并返回大小居中元素的对应下标。小区间优化原因当区间中的元素个数屈指可数时反复递归会增加函数调用次数减少效率。具体方案在区间元素个数在10个以内时直接用插入排序解决。插入排序的原理实现详细介绍可以看上一篇C语言排序一-CSDN博客//快速排序三数选中小区间优化递归 int GetMidi(int* a, int begin, int end) { int midi (begin end) / 2; if(a[begin] a[midi]) { if(a[end] a[midi]) { if(a[begin] a[end]) { return end; } else { return begin; } } else { return midi; } } else // a[begin] a[midi] { if(a[end] a[begin]) { if(a[end] a[midi]) { return midi; } else { return end; } } else { return begin; } } } void QuickSort2(int* a, int begin, int end) { //小区间优化插入排序 if((end - begin) 1 10) { InsertSort(abegin, end-begin1); return; } //三数取中 int midi GetMidi(a, begin, end); Swap(a[midi], a[begin]); //begin和end用于标记区间范围 //begin和end是在区间内移动的指针 int keyi begin; int left begin; int right end; while(left right) { //先移动右指针小于keyi就停下 while(left right a[right] a[keyi]) { right--; } //再移动左指针大于keyi就停下 while(left right a[left] a[keyi]) { left; } //再次比较减少一次自交换 if(left right) { Swap(a[left], a[right]); } } //当两指针重合时交换keyi和重合点更新keyi Swap(a[keyi], a[left]); keyi left; //继续递归 QuickSort2(a, begin, keyi - 1); QuickSort2(a, keyi 1, end); }1.2.3 双指针快排类似移动零等常见力扣双指针题。283. 移动零 - 力扣LeetCode思路设置key和快慢两个指针同时从区间左端出发fast指针遇到小于key的则和slow进行交换大于key则继续走直至到区间末尾。此时slow指针所在位置即为分界点交换slow和key的值和位置即可达到和经典快排一样的效果。随后再次对key左右两区间进行快排递归。仅仅优化了代码量在性能上还是和普通快排相似。//快速排序双指针 int PartSort(int* a, int left, int right) { int keyi left; int prev left; int cur prev 1; while(cur right) { if(a[cur] a[keyi]) { prev; Swap(a[prev], a[cur]); } cur; } Swap(a[keyi], a[prev]); return prev; } void QuickSort3(int* a, int begin, int end) { int left begin; int right end; if(right - left 1 10) { InsertSort(a begin, end - begin 1); //特别注意不是从0位置开始插入排序不要传错了 } else { //双指针排序 int keyi PartSort(a, left, right); QuickSort3(a, begin, keyi - 1); QuickSort3(a, keyi 1, end); } }1.2.4 非递归快排栈实现利用快速排序属于前序排序的特点可以利用栈的先入先出特性实现快速排序//快速排序非递归栈 void QuickSortNonR(int* a, int begin, int end) { //数组首尾下标入栈 ST st; STInit(st); STPush(st, begin); STPush(st, end); //循环出入 while(!STEmpty(st)) { //先入后出 int right STTop(st); STPop(st); int left STTop(st); STPop(st); //排序 int keyi PartSort(a, left, right); //入栈(要判断边界是否有效) // [left, keyi - 1] keyi [keyi 1, right] if(left keyi - 1) { STPush(st, left); STPush(st, keyi - 1); } if(keyi 1 right) { STPush(st, keyi 1); STPush(st, right); } } STDestroy(st); }关于栈的具体实现可以看这篇文章栈C语言-CSDN博客2. 归并排序时间复杂度O( NlogN )空间复杂度O( N )思想把数组不断分成两半分别排好序再把两个有序数组合并成一个继续归并直至整个数组有序。由于需要另开一个等大的数组存储数据因此空间复杂度也不是O( 1 )。2.1 动态演示归并排序2.2 代码实现2.2.1 经典归并递归//归并排序递归 void _MergeSort(int* a, int* tmp, int begin, int end) { if(begin end) return; int mid (begin end) / 2; _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid 1, end); int begin1 begin, begin2 mid 1; int end1 mid, end2 end; int i begin; while(begin1 end1 begin2 end2) { if(a[begin1] a[begin2]) //取等时则排序稳定 { tmp[i] a[begin1]; } else { tmp[i] a[begin2]; } } //处理剩余数据 while(begin1 end1) { tmp[i] a[begin1]; } while(begin2 end2) { tmp[i] a[begin2]; } //拷贝(不能用begin1因为已经被更改) memcpy(abegin, tmpbegin, (end - begin 1) * sizeof(int)); }2.2.2 非递归归并循环实现利用归并排序是后序排序的特点即不断拆分至最小单位再进行排序我们可以使用循环设置gap为每组的元素个数通过增加gap来不断增加排序数量从而对数组实现归并排序。//归并排序非递归循环 void MergeSortNonR(int* a, int n) { int* tmp (int*)malloc(n*sizeof(int)); if(tmp NULL) { perror(malloc fail); exit(1); } //gap为每组归并的数据个数 int gap 1; while(gap n) { for(int i0; in; i 2*gap) { //选出两组归并 int begin1 i, end1 i gap - 1; int begin2 i gap, end2 i gap * 2 - 1; //判断是否符合归并条件 if(begin2 n) //第二组全部越界则第一组已经有序不必继续归并 { break; } if(end2 n) //第二组end2越界 { end2 n - 1; } int j i; //两组归并起点 while(begin1 end1 begin2 end2) { if(a[begin1] a[begin2]) { tmp[j] a[begin1]; } else { tmp[j] a[begin2]; } } //放入剩余数据 while(begin2 end2) { tmp[j] a[begin2]; } while(begin1 end1) { tmp[j] a[begin1]; } //拷贝 memcpy(a i, tmp i, sizeof(int) * (end2 - i 1)); } //gap每次乘2扩大归并范围 gap * 2; } free(tmp); tmp NULL; }3. 计数排序时间复杂度O( N range )空间复杂度O( range )思路统计每个值出现的次数根据次数把数放回数组中覆盖原有元素。本质利用count数组中的自然序号排序问题数据相差特别大时开辟的空间浪费也会很大优化- 按照范围开这里的range为数据范围max - minQ负数的情况还能排序吗A可以因为存在a[i] - minmin为负数减去相当于增加-min偏移量还是在范围内的不用担心下标会越界。3.1 代码实现Step1遍历一遍找出最大最小值确定范围rangeStep2开辟一块range范围的空间初始化为0callocStep3统计数据次数Step4在原数组中写入数据//计数排序 void CountSort(int* a, int n) { //step1:找出最大最小值确定范围 int max a[0]; int min a[0]; for(int i0; in; i) { if(a[i] min) { min a[i]; } if(a[i] max) { max a[i]; } } int range max - min 1; //step2:开辟空间 int* tmp (int*)calloc(range, sizeof(int)); //Allocates a block of memory for an array of num elements, //each of them size bytes long, //and initializes all its bits to zero. if(!tmp) { perror(malloc fail); exit(1); } //step3:统计次数 for(int i0; in; i) { tmp[a[i] - min]; } //step4:排序 int j 0; for(int i0; irange; i) { while(tmp[i]--) { a[j] i min; } } }4. 总结在了解众多经典排序后我们可以根据他们各自的特点总结出一份对比表格稳定性指的是在遇到相等元素时元素在数组中的相对位置是否会发生改变。若不会改变则说明这个排序是稳定的否则不稳定排序时间复杂度空间复杂度稳定性直接插入排序O(N^2)O(1)稳定可以选择在等于时不移动直接插入希尔排序O(N^1.3)O(1)不稳定相同的数据预排序时会分到不同的组无法控制选择排序O(N^2)升序每次遍历选出最小的共遍历N次O(1)不稳定Eg6的位置被交换了堆排序O(NlogN)O(1)不稳定Eg全是2交换时顺序全乱冒泡排序O(N^2)O(1)稳定相等时可以不交换快速排序O(NlogN)O(logN)递归建立函数栈帧不稳定相等时相交会改变顺序归并排序O(NlogN)O(N)需要新建数组稳定在比较begin1和begin2时加上等号确保begin1先放入tmp中结论只要涉及交换大概率不稳定//感谢阅读看完顺手点个赞吧︶↗