欢迎阅读本篇学习笔记。本篇作为个人计算机专业的学习记录这里将系统梳理关于各类排序的相关知识点从基础概念到代码实现逐步展开已便于后续的复习巩固。如有不足欢迎大家在评论区交流指正感谢大家的阅读与支持一、什么是排序排序说白了就是给一群乱糟糟的数据选手安排名次。 就像班级考试排成绩、游戏天梯算段位给定一个规则升序或者降序让无序序列变得井然有序。别小看这个操作它几乎是所有数据处理里最常用的操作。数据库查询、排行榜、电商商品筛选背后都藏着排序算法在默默打工。1.1 排序的稳定性稳定性算是期末、考研选择题的常驻考点也是很多人容易记混的地方。大白话解释如果两个元素关键字的值相等排序之后它们原本的先后顺序不变这个算法就是稳定排序。反之就是不稳定。举个生活化例子帮助理解 现在有两个同分的考生甲排在乙前面。 稳定排序排完名次甲依旧在乙前面不会随便调换两人位置。 不稳定排序哪怕分数相同算法也有可能把乙换到甲前面打乱原本的相对顺序。✨小提醒稳定性不是代表算法更好只是它的一个特性不同场景有不同需求。1.2 内部排序 和 外部排序这一对概念区分起来很简单核心看数据能不能全部塞进内存。内部排序所有待排序的数据全部加载进内存所有比较、交换操作都在内存完成。我们待会学习的八大排序全部属于内部排序。内存读写速度飞快处理起来酣畅淋漓。外部排序当数据量过于庞大内存放不下全部数据数据主体保存在硬盘。排序时需要不断在外存和内存之间来回搬运数据。 海量日志、超大文件排序就会用到它代价就是速度会慢不少。1.3常见的排序算法这张思维导图一次性亮出了本次排位赛里所有算法选手。 排序算法分为四大门派插入、选择、交换、归并。门下每位选手各有独门心法行事风格迥然不同有的循序渐进、稳妥内敛有的大刀阔斧、效率惊人。 我们将围绕着几个排序展开。二、插入排序插入排序是四大门派里最朴实的一支理解起来就像我们打牌理牌的过程。门下共有两位选手直接插入排序与希尔排序。2.1直接插入排序2.1.1基本思想直接插入排序的思路十分贴近生活逐个取出待排序元素将它插入前方已经排好的有序序列中反复操作直到全部元素插入完成整个序列也就有序。最经典的类比就是摸扑克牌手里保留已经理好的牌每拿到一张新牌就找到合适位置插入。2.1.2执行逻辑假设数组前 i 个元素已经构成有序区间。取出第 i1 个元素从后往前依次和有序区间元素对比。如果有序区间的元素更大就将元素向后挪动腾出空位不断向前查找直到找到插入位置把元素放入。循环往复完成全部排序。2.1.3特性总结数组越接近有序直接插入排序效率越高近乎有序是它的优势场景。时间复杂度O(N^2)空间复杂度O(1)原地排序额外空间开销极小。稳定性稳定排序相同关键字元素不会打乱原有相对次序。小评代码简洁好实现在数据基本有序时表现亮眼。但面对高度无序数组大量元素移动会严重拖慢效率。// 直接插入排序 C语言实现 void InsertSort(int* arr, int n) { for (int i 1; i n; i) { int tmp arr[i]; int j i - 1; while (j 0 arr[j] tmp) { arr[j 1] arr[j]; j--; } arr[j 1] tmp; } }好比arr[0 ~i-1]是已经理好的有序手牌arr[i]是新摸来的牌。 我们拿新牌tmp从手牌末尾往前挨个比较把所有比新牌大的牌往后挪直到找到位置把新牌插进去。2.2 希尔排序缩小增量排序希尔排序是直接插入排序的改良进阶版解决了原版插入排序在乱序数组中大量移动元素的短板。2.2.1基本思想希尔排序不再一次性对整个数组做插入排序。它先选定间隔gap将下标相差gap的元素划为一组在组内执行插入排序随后不断缩小gap重复分组排序。当gap最终缩减至 1 时等价于一次全局直接插入排序。经过前面多轮预排序数组已经趋近有序最后一轮排序的开销会大幅降低。2.2.2执行逻辑例如初始gap 5间隔为 5 的元素分为一组组内做插入排序再缩小gap 2继续分组排序直到gap 1完成最后的插入排序数组整体有序。2.2.3特性总结核心思路通过多轮分组预排序让数组逐步接近有序优化直接插入排序的效率。时间复杂度不固定和增量序列强相关Knuth 增量序列下约 O(n^1.25。空间复杂度O(1)稳定性不稳定排序。小提醒希尔排序的时间复杂度分析是一大难点其性能高度依赖增量序列gap的选取至今没有通用的严谨数学推导属于数据结构里尚未完全解决的数学问题。gap存在多种经典取法Shell 最初提出每次取gap ⌊n/2⌋不断折半直到gap1Knuth 则推荐gap ⌊gap/3⌋ 1。不同方案各有支持者但没有哪一种能够被严格证明为最优。采用 Knuth 增量序列时大量实验统计表明当数据规模n很大关键字平均比较与移动次数约在 n^1.25 ~ 1.6n^1.25 区间我们一般记时间复杂度为O(n^1.25)。// 希尔排序 C语言实现Knuth增量序列 void ShellSort(int* arr, int n) { int gap n; while(gap 1) { gap gap / 3 1; for(int i gap; i n; i) { int tmp arr[i]; int j i - gap; while(j 0 arr[j] tmp) { arr[j gap] arr[j]; j - gap; } arr[j gap] tmp; } } }代码简析 外层循环不断更新增量 gap从下标 gap 开始遍历数组取出待插入元素tmp。向前跨 gap 距离比较更大的元素向后挪动最后将元素插入对应位置。门派小结 直接插入排序是根基简单稳妥偏爱有序数组希尔排序借助分组预排序提速代价是丢失了稳定性。插入门派两位选手到此介绍完毕。三、交换排序交换排序的核心在于通过元素之间的两两比较与交换逐步把序列调整为有序。它和插入、选择的思路不同插入排序强调 “找到位置插入”选择排序强调 “选出最值放到指定位置”而交换排序更像是让元素在不断比较中 “碰撞换位”一路交换到自己该在的地方。交换排序门下最典型的两位选手分别是冒泡排序与快速排序。3.1 冒泡排序3.3.1基本思想冒泡排序是交换排序中最直观的一种。它重复遍历待排序序列依次比较相邻两个元素。如果前面的元素比后面的元素更大就交换二者位置。这样一来每一轮遍历结束后当前未排序区间中的最大值就会像气泡一样 “浮” 到序列末尾。这个过程不断重复直到某一轮遍历中没有发生任何交换说明序列已经有序可以提前结束。3.3.2执行逻辑以升序排序为例从下标 0 开始依次比较相邻元素arr[j]和arr[j 1]。若arr[j] arr[j 1]交换两者。每一轮结束后当前未排序部分的最大值会被推到末尾。下一轮只需在前n - 1个元素中继续比较。若某一轮没有发生交换说明数组已有序直接退出。代码实现void BubbleSort(int* arr, int n) { for (int i 0; i n - 1; i) { int flag 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; flag 1; } } if (flag 0) break; } }代码简析i表示已经完成排序的轮数。每一轮中j从前往后比较相邻元素。n - 1 - i表示后面i个元素已经有序无需再比较。flag用于标记本轮是否发生交换若没有交换说明数组已有序提前结束。3.3.3特性总结每一轮都会把当前未排序区间的最大值放到末尾。加入flag提前判断后最好情况为O(N)。最坏时间复杂度O(N^2)。平均时间复杂度O(N^2)。空间复杂度O(1)。稳定性稳定排序。小提醒冒泡排序最好情况是数组已有序此时只需扫描一轮即可结束但如果没有提前判断即使数组有序也会执行完整的O(N^2)。3.2快速排序门派小引交换门派的王牌选手来了和冒泡那种一点点挪元素的笨办法不同快排靠着分治大法一次划分就能让基准元素直接坐到它最终的正确位置也是工程代码里出场率最高的排序算法。3.2.1 基本思想快速排序由 Hoare 在 1962 年提出是基于分治思想的交换排序。核心逻辑在待排序区间选取一个基准值pivot划分区间让基准左边所有元素 ≤ pivot基准右边所有元素 ≥ pivot基准元素归位后再递归对左右两个子区间重复划分直到子区间元素个数≤1整体有序。3.2.2 执行逻辑递归主框架// 对array数组[left, right]区间升序排序 void QuickSort(int array[], int left, int right) { if(right - left 1) return; // 划分得到分割点div int div partion(array, left, right); // 递归排左区间 [left, div] QuickSort(array, left, div); // 递归排右区间 [div1, right] QuickSort(array, div1, right); }代码简析递归框架和二叉树前序遍历高度相似。先做划分根节点处理再递归处理左子区间、右子区间。快速排序的难点不在递归框架而在partion划分函数。三种经典划分方式Hoare 版本原始左右双指针法思路左指针 L 从区间最左向右走找大于基准的元素右指针 R 从区间最右向左走找小于基准的元素。两个指针停下后交换元素持续直到两指针相遇相遇位置就是基准的落脚点。基准一般取区间最左端R 先移动L 后移动相遇点的值一定 ≤ pivot交换基准与相遇位置完成划分2.2.挖坑法将区间第一个元素存入临时变量key原位置变成坑位。 右指针 R 向左查找找到小于key的元素填入坑内该元素原来位置变成新坑。 左指针 L 向右查找找到大于key的元素填入当前坑更新坑位。 循环往复直到 L、R 相遇最后将key填入最后的坑中基准归位。直观理解不断移动坑的位置把不符合大小规则的元素填进坑里最终基准落在坑点。3.前后指针版本prev/curprev指向小于 pivot 区域的末尾cur作为探索指针从头向后遍历。cur找到比 pivot 小的元素时prev交换prev和cur位置元素。cur持续向前扫描遍历结束后交换prev与基准元素基准就位。优点代码逻辑简单适合链表实现快速排序。快速排序优化方案原生快排如果每次选到极差基准有序数组取端点时间复杂度退化到O(N^2)工程上常用下面两种优化三数取中法选基准取区间左端、右端、中间位置三个数选三者的中位数作为 pivot。避免选到最大 / 最小值防止划分极度不均衡。小区间改用直接插入排序递归拆分到子区间长度很小的时候递归调用的开销大于排序开销。当区间长度小于阈值一般取 7直接使用插入排序代替快排。#define MAX_LENGTH_INSERT_SORT 7 // 数组长度阈值 void QSort(SqList L, int low, int high) { int pivot; if ((high-low) MAX_LENGTH_INSERT_SORT) { pivotPartition(L,low,high); QSort(L, low, pivot-1); QSort(L, pivot1, high); } else InsertSort(L); //小区间插入排序 }快速排序 非递归版本递归会使用函数调用栈数据量极大时有栈溢出风险。可以手动用栈模拟递归保存待排序区间[left,right]循环取出区间进行划分再把划分后的子区间入栈。void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(st); StackPush(st, left); StackPush(st, right); while (StackEmpty(st) ! 0) { right StackTop(st); StackPop(st); left StackTop(st); StackPop(st); if(right - left 1) continue; int div PartSort1(a, left, right); //右区间入栈 StackPush(st, div1); StackPush(st, right); //左区间入栈 StackPush(st, left); StackPush(st, div); } StackDestroy(st); }代码简析栈用来存储待处理区间边界。每次弹出一组左右边界执行划分再把划分得到的左右子区间继续压栈循环直到栈空完成排序。3.2.3 特性总结核心思想分治选取基准划分区间基准元素直接落到最终位置递归处理左右子区间。最好时间复杂度O(Nlog N)平均时间复杂度O(Nlog N)最坏时间复杂度O(N^2)空间复杂度O(log N)来自递归调用栈非递归版本同样需要栈保存区间边界。稳定性不稳定排序。小提醒快速排序虽然平均效率很高但如果每次划分都极不均衡例如数组已有序且固定取端点作为 pivot时间复杂度会退化到 O(N^2)。门派小结 冒泡排序是交换排序里的基础选手依靠相邻元素两两交换像气泡一样把大数逐步推到尾部而快速排序是交换门派的王牌依靠分治划分一次划分就能让基准一步到位归位平均性能远高于冒泡。交换排序两位选手就介绍到这里。四、归并排序门派小引如果说快排是分治门派的激进派那归并排序就是分治门派的稳健派。它不搞基准划分的 “一步归位”而是走先拆后合的路线用最稳妥的方式完成排序也是外排序场景的首选选手。4.1 基本思想归并排序MERGE-SORT是建立在归并操作上的排序算法是分治法Divide and Conquer的典型应用。 核心逻辑先让每个子序列各自有序再将两个有序子序列合并成一个完整的有序序列这个两两合并的操作称为二路归并。整个过程分为两大核心步骤先分解、后合并。4.2执行逻辑整个归并过程分为「分解」和「合并」两个阶段分解阶段从原始数组开始不断从中间位置对半切分拆分为左右两个子区间递归执行拆分直到每个子区间内只剩 1 个元素单个元素天然就是有序的。合并阶段从最小的有序单元开始将两个有序小数组合并成一个更长的有序数组逐层向上重复合并操作最终合并为完整的有序数组。我们就用图里的例子[10, 6, 7, 1, 3, 9, 4, 2]完整走一遍流程。第一步分解从上往下拆从原始数组开始每次从中间切开一分为二第 1 层[10,6,7,1,3,9,4,2]→ 拆成[10,6,7,1]和[3,9,4,2]第 2 层继续拆 →[10,6]、[7,1]、[3,9]、[4,2]第 3 层再拆 →[10]、[6]、[7]、[1]、[3]、[9]、[4]、[2]拆到每个数组只剩 1 个元素分解阶段结束。左指针指 1右指针指 2 → 取 1左指针后移左指针指 6右指针指 2 → 取 2右指针后移左指针指 6右指针指 3 → 取 3右指针后移左指针指 6右指针指 4 → 取 4右指针后移左指针指 6右指针指 9 → 取 6左指针后移依次取 7、9、10 最终合并结果[1, 2, 3, 4, 6, 7, 9, 10]最底层[10][6]→ 合并成[6,10][7][1]→[1,7][3][9]→[3,9][4][2]→[2,4]上一层[6,10][1,7]→ 合并成[1,6,7,10][3,9][2,4]→[2,3,4,9]最顶层[1,6,7,10]和[2,3,4,9]合并 → 最终[1,2,3,4,6,7,9,10]// 归并排序递归实现 void MergeSort(int* arr, int left, int right, int* tmp) { if(left right) return; int mid (left right) / 2; // 递归拆分排序左右区间 MergeSort(arr, left, mid, tmp); MergeSort(arr, mid 1, right, tmp); // 二路归并合并两个有序区间 int begin1 left, end1 mid; int begin2 mid 1, end2 right; int idx left; while(begin1 end1 begin2 end2) { if(arr[begin1] arr[begin2]) tmp[idx] arr[begin1]; else tmp[idx] arr[begin2]; } // 拷贝剩余元素 while(begin1 end1) tmp[idx] arr[begin1]; while(begin2 end2) tmp[idx] arr[begin2]; // 有序数据拷贝回原数组 for(int i left; i right; i) arr[i] tmp[i]; }代码简析递归先完成左右子区间的排序再借助临时数组完成二路归并。每次比较两个子数组的头部元素更小的优先放入临时空间最后把剩余元素依次补齐再写回原数组。4.3 特性总结时间复杂度O(Nlog N)无论最好、最坏、平均情况复杂度一致性能不受原始数据有序程度影响。空间复杂度O(N)需要额外开辟临时数组存储归并数据这是它最主要的缺点。稳定性稳定排序相等元素的相对顺序在归并过程中不会被打乱。适用场景尤其适合磁盘外排序当数据量过大无法全部载入内存时归并排序是主流方案。 门派小结 归并排序和快速排序同属分治家族但路线截然不同。快排先划分再递归平均速度更快但最坏情况会退化归并先拆分再合并时间复杂度始终稳定还能保证排序稳定代价是需要额外的内存空间。五、选择排序门派小引选择排序门派的行事风格非常直接 —— 不搞插入挪动也不搞两两交换冒泡每一轮只干一件事从剩余元素里挑出最值直接送到它该去的位置。门下两位选手一位是简单直白的直接选择排序一位是借助堆结构升级的堆排序。5.1 直接选择排序5.1.1 基本思想直接选择排序是选择排序最朴素的实现。每一轮遍历未排序区间找到关键字最小的元素将它与未排序区间的第一个元素交换位置有序区间从左向右逐步扩大直到覆盖整个数组。5.1.2 执行逻辑初始状态有序区间长度为 0未排序区间为整个数组[0, n-1]。第i轮排序i 从 0 开始在未排序区间[i, n-1]中遍历找到最小值的下标。将最小值元素与未排序区间的首元素arr[i]交换此时arr[i]加入有序区间。重复上述步骤直到未排序区间只剩 1 个元素排序完成。// 直接选择排序 C语言实现 void SelectSort(int* arr, int n) { for(int i 0; i n - 1; i) { int min_idx i; // 记录最小值下标 for(int j i 1; j n; j) { if(arr[j] arr[min_idx]) min_idx j; } // 交换最小值和未排序区第一个元素 int tmp arr[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } }5.1.3 特性总结思路非常直观好理解但整体效率不高实际工程中很少使用。时间复杂度O(N^2)无论数组是否有序都需要完整遍历找最小值。空间复杂度O(1)原地排序额外空间开销极小。稳定性不稳定排序跨位置的交换操作可能打乱相同关键字元素的相对顺序。5.2 堆排序门派小注堆排序本质还是选择排序。直接选择排序是每次遍历整个数组找最大值堆排序用「大顶堆」快速锁定最大值省去一遍遍全数组扫描想要看懂堆排序流程首先得认识这个核心工具 —— 大顶堆。这里很多人会产生疑问我们最终目标是升序为啥不用小顶堆直接拿最小值看完堆的定义我们再来解答这个经典疑问。5.2.1什么是大顶堆大顶堆是一棵完全二叉树父节点的值 ≥ 左右孩子节点。 堆顶树根永远是整个堆里面最大的数字。 数组可以直接映射成完全二叉树不需要额外开辟空间这也是堆排序原地排序的关键。 对应的还有小顶堆父节点 ≤ 子节点堆顶是堆里最小元素。❓灵魂拷问升序排序为什么选用大顶堆而不是小顶堆堆排序有个关键特点选出最值之后把最值放到数组末尾固定有序区域从后往前逐步扩大。大顶堆堆顶是最大值 每次交换把最大值放到数组最后的位置这个位置就固定不再参与后续排序。 大数不断往数组尾部安家最后前面剩下的自然就是从小到大的升序序列和我们流程图的操作完全匹配。小顶堆堆顶是最小值 如果用小顶堆每次拿到的是最小值交换后最小值会被放到数组末尾。 所有小数都堆在数组尾部最终得到的数组反而是降序。补充扩展理论上小顶堆也能实现升序但每次取出最小值放到数组前面会破坏前面已经排好的有序区域调整堆时代价更高工程上不会这么写。大顶堆是一棵完全二叉树父节点的值 ≥ 左右孩子节点。 堆顶树根永远是整个堆里面最大的数字。 数组可以直接映射成完全二叉树不需要额外开辟空间这也是堆排序原地排序的关键。结合这张流程图一步一步拆解初始堆[20,17,4,16,5,3]画成二叉树根节点是20全局最大值第一步交换堆顶和堆末尾元素堆顶是最大值20把20和堆最后一个元素3交换。 此时20就位固定在数组最后的位置不再参与后续排序图里蓝色标记代表已经排好的数。 现在待排序的堆范围缩小不再包含 20。第二步向下调整重新变回大顶堆现在堆顶变成了3不满足大顶堆规则我们执行向下调整拿根节点3和左右孩子对比把大的孩子换上来一直换到满足大顶堆为止。 调整完成新堆顶是17也就是剩下元素里的最大值。循环重复上面两步交换堆顶17和当前堆末尾元素17固定就位向下调整选出剩余元素最大值16交换、调整…… 依次把16、5、4全部放到末尾每一轮取堆顶最大值 → 放到数组尾部 → 调整堆选出下一个最大值不断缩小待排序堆的区间直到堆只剩 1 个元素排序全部完成。5.2.2温馨提醒升序排序建大顶堆很多人容易记反不是小顶堆。小顶堆适合降序。堆排序不稳定相同大小元素相对顺序会被交换打乱。时间复杂度 O(Nlog N)建堆是O(N)每一次向下调整是(log N)一共 N 次。原地排序空间复杂度O(1)不需要额外数组。代码简要解析// 向下调整parent位置元素往下滑维护大顶堆 void AdjustDown(int* arr, int n, int parent) { int child 2 * parent 1; while(child n) { // 选出左右孩子里面更大的那个 if(child1 n arr[child1] arr[child]) child; if(arr[child] arr[parent]) { swap(arr[child], arr[parent]); parent child; child 2*parent 1; } else break; // 满足大顶堆停止 } } void HeapSort(int* arr, int n) { // 1、建大顶堆从最后一个非叶子节点向前调整 for(int i (n-2)/2; i 0; i--) AdjustDown(arr,n,i); // 2、不断取出堆顶最大值放到数组末尾 int end n-1; while(end0) { swap(arr[0], arr[end]); AdjustDown(arr, end, 0); // 注意end堆范围缩小不碰已经排好的尾部 end--; } }5.2.3特性总结 门派小结 直接选择排序是选择门派的基础款逻辑简单但效率平平仅适合小数据场景堆排序是它的进阶优化版用堆结构把选最值的效率从O(N)降到O(log N)时间复杂度跻身(Nlog N)级别还保持了原地排序的优势缺点是排序不稳定。六、非比较排序门派小引前面咱们介绍的插入、选择、交换排序全都属于比较排序依靠元素两两比较来决定先后。而本门派的成员不走比较这条路直接利用元素本身的值通过映射完成排序因此称为非比较排序。代表选手就是计数排序。6.1 计数排序6.1.1基本思想计数排序也叫鸽巢原理是哈希直接定址法的变形应用。核心思想不去比较元素大小先统计每个数字出现多少次再根据统计结果把数字放回有序数组。只适合数值范围集中的数据。操作步骤结合图中例子待排序数组 A[2, 5, 3, 0, 2, 3, 0, 3]统计频次创建计数数组 CC [i] 记录数字i在 A 中出现多少次。 图中 C 数组值为 0 有 2 个值为 1 有 0 个值为 2 有 2 个值为 3 有 3 个值为 4 有 0 个值为 5 有 1 个。前缀和处理把 C [i] 修改成小于等于 i 的元素总个数。 这个操作的作用直接算出数字i在结果数组 B 里的最后存放位置。从后向前遍历原数组 A 取出 A 里的元素查看 C 数组找到它在 B 数组的下标放到 B 里对应 C 数组计数减 1。 ✨重点必须从后往前遍历这一步是保证计数排序稳定的关键全部复制完成后B 数组就是有序结果。C 语言简易实现void CountSort(int* arr, int n) { // 找最大值确定计数数组的范围 int max arr[0]; for(int i 1; i n; i) { if(arr[i] max) max arr[i]; } // 开辟计数数组初始化为0 int* countArr (int*)calloc(max 1, sizeof(int)); // 1.统计元素出现次数 for(int i 0; i n; i) { countArr[arr[i]]; } // 2.计算前缀和C[i]变为i的元素总数 for(int i 1; i max; i) { countArr[i] countArr[i-1]; } // 临时数组存放排序结果 int* tmp (int*)malloc(sizeof(int)*n); // 3.从后向前遍历保证排序稳定 for(int i n-1; i 0; i--) { tmp[ countArr[arr[i]] - 1 ] arr[i]; countArr[arr[i]]--; } // 拷贝回原数组 for(int i 0; i n; i) { arr[i] tmp[i]; } free(tmp); free(countArr); }6.1.2特性总结优势数据范围集中时效率极高它没有元素之间的比较操作缺点适用场景受限。如果数字跨度极大如[1, 100000]会开辟超大数组浪费大量空间。稳定性稳定排序前提从后向前遍历原数组 门派小考点 很多同学写计数排序习惯从前向后遍历虽然排序结果数字是对的但是排序就会变成不稳定考研 / 笔试很爱考这个坑点。 门派小结非比较排序门派 前面的几大门派都需要拿元素两两 PK 比较大小而本门派直接摆烂不做比较利用数字本身的值做映射统计典型代表就是计数排序。 计数排序是典型的 “空间换时间” 选手在整数密集的场景下能跑出碾压级的效率但短板也十分明显一旦数据跨度很大就要开辟巨大的辅助数组空间开销直接爆炸。 它是为数不多稳定的线性时间排序算法记住关键点想要保住稳定性遍历原始数组时必须从后往前。七、排序算法复杂度及稳定性分析门派总览插入、选择、交换、归并四大门派悉数登场七位核心算法全部讲解完毕。这里用一张性能总表把时间复杂度、空间开销、稳定性等核心指标一网打尽方便横向对比也适合考前速记复盘。7.1核心性能对比表排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n2)O(n)O(n2)O(1)稳定简单选择排序O(n2)O(n2)O(n2)O(1)不稳定直接插入排序O(n2)O(n)O(n2)O(1)稳定希尔排序O(nlogn)∼O(n2)O(n1.3)O(n2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n2)O(logn)∼O(n)不稳定八、 选择题练习参考答案1.A 2.C 3.D 4.B 5.D 6.A 7.A好啦那这篇内容就先整理到这里这次把相关排序算法的相关知识整理了一下为了方便自己日后复习回顾也希望能给正在学习的小伙伴一些参考。如果文中有理解不到位或是书写有误的地方欢迎大家在评论区指出一起交流共同进步。谢谢大家