排序1.直接插入排序voidInserSort(int*arr,intn){for(inti0;in-1;i){intendi;inttmparr[end1];while(end0){if(tmparr[end]){arr[end1]arr[end];end--;}else{break;}}arr[end1]tmp;}}✅ 直接插入排序在数据量小、数组基本有序时性能极佳这也是实际工程里经常使用它的核心原因。在数组为降序的情形下达到最坏On^2那在数组为降序的时候如何优化直接插入排序呢2. 希尔排序又叫做缩小增量法。设置一个增量 gap把数组按照下标间隔 gap 分成若干组每组内部单独执行直接插入排序初始 gap 大分组多、每组元素数量少。✅ 此时整体数组无序但每组数据量小插入排序效率尚可不断缩小增量 gap重复分组插入排序直到 gap 1退化成完整数组的直接插入排序。✅ 经过前面多轮处理数组已经接近基本有序直接插入排序发挥最强性能。voidShellSort(int*arr,intn){intgapn;while(gap1){gapgap/31;for(inti0;in-gap;i){intendi;inttmparr[endgap];while(end0){if(tmparr[end]){arr[endgap]arr[end];end-gap;}else{break;}}arr[endgap]tmp;}}}希尔排序的本质通过 gap 让元素进行“大跨度移动”快速消除大量逆序。3.快速排序快速排序Quick Sort是一种经典的分治算法平均时间复杂度为 O(n log n)。快速排序│┌─────────┴─────────┐│ │选择 Pivot Partition│┌──────────────┼──────────────┐│ │ │挖坑法 Hoare法 Lomuto法它们不是三种完全不同的快速排序而是三种不同的“分区实现”。3.1 HoareHoare于1962年提出一种二叉树结构的交换排序方法其基本思想任取待排序元素序列中的某元素为基准值按照该排序码将集合分成两个子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后左右子序列重复该过程直到所有元素都排列有序为止。//hoareint_QuickSort1(int*arr,intleft,intright){intkeyileft;left;while(leftright){while(leftrightarr[right]arr[keyi]){right--;}while(leftrightarr[left]arr[keyi]){left;}if(leftright){swap(arr[left],arr[right--]);}}swap(arr[keyi],arr[right]);returnright;}为什么最后是 arr[right]因为循环结束的时候left right而在整个过程中right 最终停在 小于等于 key 的区域最后一个位置所以swap(arr[keyi], arr[right]);就可以把 key 放到正确位置。left right不一定意味着“完成了。”而可能意味着“还有最后一个元素没有检查。”left right才意味着“两个指针已经交叉所有元素都检查完了。”3.2挖坑法int_QuickSort2(int*arr,intleft,intright){intholeleft;intkeyarr[left];while(leftright){while(leftrightarr[right]key){right--;}arr[hole]arr[right];holeright;while(leftrightarr[left]key){left;}arr[hole]arr[left];holeleft;}arr[hole]key;returnhole;}left right的时候发生了什么假设[1 | 2 | □ | 5 | 6]↑L/R这意味着左右两边已经把所有能搬运的元素都处理完了。中间这个位置□就是最后的坑。所以left right意味着任务完成。外层 while回答“还有没有元素没有处理”内层 while回答“当前这个元素需不需要处理”这两个问题完全不同。3.3 lomuto前后指针//前后指针法int_QuickSort2(int*arr,intleft,intright){intpreleft;intpcurleft1;while(pcurright){if(arr[pcur]arr[left]){swap(arr[pre],arr[pcur]);}pcur;}swap(arr[pre],arr[left]);returnpre;}pre是这个算法最核心的地方。在任何时候[left1 … pre] key[pre1 … pcur-1] key[pcur … right] 尚未处理核心pre pcur↓ ↓[ key | key区域 | key区域 | 未处理区域 ]pre小于 key 区域的最后一个位置pcur 当前正在扫描的位置voidQuickSort(int*arr,intleft,intright){if(leftright){intkeyi_QuickSort2(arr,left,right);QuickSort(arr,left,keyi-1);QuickSort(arr,keyi1,right);}}4.归并排序void_MergeSort(int*arr,intleft,intright,int*temp){if(leftright){return;}intmid(leftright)/2;_MergeSort(arr,left,mid,temp);_MergeSort(arr,mid1,right,temp);//mergeintindexleft;intbegin1left,end1mid;intbegin2mid1,end2right;while(begin1end1begin2end2){if(arr[begin1]arr[begin2]){temp[index]arr[begin1];}else{temp[index]arr[begin2];}}while(begin1end1){temp[index]arr[begin1];}while(begin2end2){temp[index]arr[begin2];}for(intileft;iright;i){arr[i]temp[i];}}voidMergeSort(int*arr,intn){int*temp(int*)malloc(sizeof(int)*n);_MergeSort(arr,0,n-1,temp);free(temp);tempNULL;}5.计数排序结合鸽笼原理是对哈希直接定址法的变形应用。voidCountSort(int*arr,intn){intmaxarr[0];intminarr[0];for(inti1;in;i){if(arr[i]max){maxarr[i];}elseif(arr[i]min){minarr[i];}}intsizemax-min1;int*count(int*)malloc(sizeof(int)*size);for(inti0;isize;i){count[i]0;}for(inti0;in;i){count[arr[i]-min];}intindex0;for(inti0;isize;i){while(count[i]--){arr[index]imin;index;}}}当数据范围比较小并且数据量比较大时计数排序非常优秀排序核心思想平均复杂度最坏复杂度空间稳定性直接插入插入O(n²)O(n²)O(1)✅希尔分组插入依赖 gap依赖 gapO(1)❌快速排序分治 PartitionO(nlogn)O(n²)O(logn)~O(n)❌归并排序分治 MergeO(nlogn)O(nlogn)O(n)✅计数排序直接定址/计数O(n range)O(n range)O(range)可以做到 ✅