1.插入排序1.1 核心思想把数组分成有序区间无需区间两个部分假设位置[0end]的值都是按升序排列的把end1位置的值保存到变量tmp里end位置的值大于tmp就往后挪一位end也走到end-1一直比较直到成功插入该数然后进行下一轮比较。先写单趟排序的过程再写整体。1.2 代码1.3 复杂度·时间复杂度O(N^2)逆序的情况下最坏O(N^2)顺序的情况下最好O(N)·空间复杂度O(1)原地排序只开临时变量不额外开辟数组2.冒泡排序2.1 核心思想重复遍历数组相邻两个元素逆序则交换每一轮外层循环会把当前无序区间里最大的数“冒泡”到区间末尾。优化点设置flag标记如果一整轮遍历没有发生任何交换代表数组已经完全有序直接提前跳出循环不用继续遍历。2.2 代码2.3 复杂度·时间复杂度O(N^2)·空间复杂度O(1)3.希尔排序3.1 核心思想希尔排序是插入排序的优化版本分为两个阶段1.预排序设置间隔gap将数组分为gap组每组内部做插入排序让数组接近有序。2.插入排序间隔缩小为1时等价于标准插入排序示例先只排红色这一组核心疑问i 的范围为什么在0到n-gap之间如上图数组下标最大为n-1若 i n-gapi gap na[igap]就越界了。接下来把绿色与紫色组的考虑进去写法一分组依次遍历写法二多组依次遍历gap缩小公式说明gap gap/3 11. 除以3快速缩小间隔2. 1兜底防止gap变为03.2 代码3.3 复杂度·时间复杂度O(N^1.3)4.双向选择排序4.1 核心思想双向选择排序每一趟同时找出区间[begin, end]的最小值、最大值分别交换到区间左右两端1. 遍历区间记录最小值下标mini、最大值下标maxi2. 最小值交换到begin位置最大值交换到end位置3. begin、end--缩小区间循环直到begin end写出代码如下但是经过测试我们发现并没有按照我们预想的成功排好序。出错场景最大值刚好在begin下标第一轮begin0区间最小值下标mini1最大值下标maxi01.执行Swap(a[0]a[1])后下标为0的最大值9被换到了mini1的位置但maxi仍然为0。2.再执行Swap(a[end]a[maxi])把1交换到了末尾而最大值9遗留在中间排序出现错乱。4.2 正确代码如下4.3 复杂度·时间复杂度O(N^2)5.快排5.1 核心思想分治二分快速排序是经典分治类排序算法核心逻辑1. 在区间内选定一个key一趟遍历将数组分割为两部分左侧全部 ≤ key右侧全部 ≥ key2. 递归处理左子区间[left, keyi-1]、右子区间[keyi1, right]3. 当区间长度≤1时天然有序递归终止。5.2 Hoare分区法基础原生快排5.2.1 分区原理我们默认把区间最左元素设为key左指针L从左向右找大于key的数右指针R从右向左找小于key的数• 行走规则R先动L后动两指针相遇时停下• 相遇位置性质保证相遇处的值一定 ≤ key1. 场景1R主动停下——R找到小于key的值L全程未找到大数直接和R相遇R停留值天然小于key2. 场景2R走完整个区间无小数直接与L碰头——上一轮交换已经把小于key的元素换到L侧。• 收尾操作两指针相遇后交换key与相遇位置的值完成区间分割。补充将key设为最右侧需要改为L先走R后走相遇位置的值会恒大于key代码如下易错点内层循环必须重复添加beginend判断外层循环的初始检查替代不了循环中持续变化的变量校验如果漏写begin与end可能会一直走造成越界。接下来只需要让key的左区间与右区间有序即可。我们可以用递归调用来实现具体过程如下图5.2.2 代码时间复杂度O(N)N*logN5.3 原生快排的缺陷与优化5.3.1 两大风险1.当数组本身有序时递归深度极大有可能会出现栈溢出的情况。2.当数组有序时这个算法就会退化成O(N^2)的算法如下图5.3.2 优化1三数取中所以为了避免有序情况下造成的效率退化我们可以用到以下两种方法1.随机取key2.三数取中重点讲解三数取中即在一组数最左边最右边以及中间的数中取一个不大不小的中间值作key。代码如下使用方法分区函数开头获取中位数下标交换至left位置再执行Hoare逻辑5.3.3 优化2小区间插入排序由于递归调用本身存在不小的性能损耗我们可以对长度较短的小区间放弃递归改用插入排序提升整体效率。原理假设快排每次分割都是二分整个递归过程可以等效为满二叉树二叉树最后一层的递归调用次数占总次数50%倒数第二层占25%。直接去掉底层小规模区间的递归能明显降低开销。小区间阈值通常取长度10代码示例5.4前后指针分区法5.4.1 原理设定最左侧为key初始状态下prev与cur指向同一起点cur向后遍历找到小于key的值时prev就然后交换prev处与cur处的值循环这个过程直到cur遍历到最后交换prev处与key的值。5.4.2 代码5.5 整合优化版递归快排代码void QuickSort(int* a,int left,int right) { if (left right) return; int keyiPartSort2(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); } int PartSort1(int* a, int left, int right) { //小区间优化 if (right - left 1 10) { InsertSort(a left, right - left 1); } else { //三数取中 int mid GetMidi(a, left, right); Swap(mid, a[left]); int begin left, end right; int keyi left; while (begin end) { while (begin end a[begin] a[keyi]) { begin; } while (begin end a[end] a[keyi]) { --end; } Swap(a[begin], a[end]); } Swap(a[begin], a[keyi]); return begin; } } int PartSort2(int* a, int left, int right) { //三数取中 int mid GetMidi(a, left, right); Swap(mid, a[left]); int prev left; int cur left1; int keyi left; while (cur right) { if (a[cur] a[keyi]) { prev; Swap(a[cur], a[prev]); } cur; } Swap(a[keyi], a[prev]); return prev; }5.6 非递归快排栈模拟递归解决栈溢出5.6.1 实现思路递归快排依赖程序调用栈有序大数据易栈溢出使用自定义栈数据结构存储待排序区间下标手动模拟递归二分流程。优势自定义栈在堆区申请内存空间上限远大于程序栈不会栈溢出。如上图右左子区间入栈每次取栈顶区间单趟排序。循环一次相当于一次递归。5.6.2 代码如下6.归并排序6.1 核心思想分治思想整体分为两个阶段1.分递归拆分不断将数组区间对半切割直到每个子区间仅仅存在单个元素单个元素天然有序2.治有序归并将两段已经排好序的子数组借助临时数组tmp按从小到大的顺序合并为一段完整有序区间最后拷贝回原数组。如上图不断对比a[begin1]和a[begin2]把更小的值存入临时数组tmp对应下标向后移动直至其中一段全部遍历完毕。若某一段提前遍历完成直接把另一段剩余元素全部追加至tmp尾部最后将tmp内当前区间有序数据覆盖写回原数组。6.2 代码void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin end) return; int mid (begin end) / 2; //[begin,mid][mid1,end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid1, end); //归并 int begin1 begin, end1 mid; int begin2 mid 1, end2 end; int i begin; while (begin1 end1 begin2 end) { 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]; } memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc); return; } _MergeSort(a, tmp, 0, n-1); free(tmp); tmp NULL; }易错点1.memcpy容易漏掉begin2.为什么分割区间不这样分割[beginmid-1][midend]根据上图分析可得这样分割区间会造成区间重复递归死循环6.3 复杂度·时间复杂度O(N*logN)·空间复杂度O(N)6.4 非递归实现归并排序递归版归并排序需要借助函数调用栈完成区间拆分与回溯栈操作逻辑抽象、不易理解因此我们改用循环迭代的方式实现归并排序思路直观清晰。gap代表每组归并区间的数据个数• 初始 gap 1单个元素天然有序执行11归并• 每轮循环结束执行 gap * 2子区间长度翻倍• 循环条件gap n当子区间长度超过数组总长度时整体数组完成有序合并。分组遍历逻辑for(int i0;in;i2*gap)i 代表每组归并区间的起始位置每组包含两段长度为gap的有序空间总长度2*gap。区间划分公式基础代码框架如下void MergeNonRSort(int* a,int n) { int* tmp malloc(sizeof(int) * n); if (tmp NULL) { perror(malloc); return; } int gap 1; while (gap n) { for (int i 0; i n; i 2 * gap) { int begin1 i, end1 i gap - 1; int begin2 i gap, end2 i 2 * gap - 1; int j i; while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[j] a[begin1]; } else { tmp[j] a[begin2]; } } while (begin1 end1) { tmp[j] a[begin1]; } while (begin2 end2) { tmp[j] a[begin2]; } memcpy(a i, tmp i, sizeof(int) * (end2 - i 1)); } gap * 2; } free(tmp); tmp NULL; }缺陷上述代码在数组长度不能被2*gap整除时会产生下标越界访问的问题。我们添加打印语句输出每一组区间的下标直观观察越界场景测试数组{6,1,2,7,9,3,4,5,10,8}数组长度n10下标范围0-9输出结果如下红色标注的区间即为越界下标一共分为两类异常场景针对两种越界场景我们在计算完区间下标后立刻添加两段边界校验7. 计数排序7.1 核心思想开辟一块统计数组count下标对应数组元素count[数值]存储该数字出现次数最后遍历count数组按下标顺序还原有序序列。示例演算基础版缺陷若数组数值跨度极大最小值远大于0会造成大量内存浪费。例优化偏移映射1.遍历数组找到最小值最大值2.实际开辟长度rangemax-min1的count数组3.count[a[i]-min]把原始数字减去最小值映射从0开始的连续下标4.读取还原a[j]imincount下标i加上偏移量min还原原始数值7.2 代码void CountSort(int* a, int n) { int min a[0], max a[0]; for (int i 0; i n; i) { if (a[i] min) min a[i]; if (a[i] max) max a[i]; } int range max - min 1; int* count calloc(range, sizeof(int)); if (count NULL) { perror(calloc); return; } for (int i 0; i n; i) { count[a[i] - min]; } int j 0; for (int i 0; i range; i) { while (count[i]--) { a[j] i min; } } free(count); }7.3 复杂度·时间复杂度O(Nrange)·空间复杂度O(range)适用限制1.仅支持整数数组浮点、字符串无法使用2.仅适合数值分布集中数值跨度小的数组