超详细八大经典排序算法完整解析（原理+代码+复杂度+场景）

排序算法是计算机算法的基石，是面试、算法刷题、工程开发的核心必备知识点。市面上主流的八大经典排序算法可分为两大类：比较排序和非比较排序。

本文将保姆级拆解所有排序算法，从零讲解原理、执行流程、手写代码、时间/空间复杂度、稳定性、优缺点及实战场景，零基础也能完全看懂。

一、前置核心概念（必看）

1.1 排序稳定性

稳定排序：相等元素的相对顺序在排序后保持不变。

不稳定排序：相等元素的相对顺序可能被打乱。

举例：数组 [2(1), 1, 2(2)]，稳定排序后一定是 [1, 2(1), 2(2)]；不稳定排序可能出现 [1, 2(2), 2(1)].这里的(1)(2)是指第一个出现的2，第二个出现的2

工程意义：多条件排序时，稳定排序可保留上一轮排序的有序结果，避免数据错乱。

1.2 时间复杂度

衡量算法执行速度，核心看数据规模n趋向于+∞时，运算次数的增长趋势：

• O(1)：常数级，与数据量无关

• O(n)：线性级，随数据量线性增长

• O(nlogn)：对数线性级，中大数据量最优主流复杂度

• O(n²)：平方级，大数据量效率极低

• O(n+k)：线性非比较排序专属，k为数据范围

1.3 空间复杂度

衡量算法额外占用的内存空间：

• 原地排序（O(1)）：仅使用常数额外空间，不新开数组/递归栈

• 非原地排序：需要额外开辟内存存储数据

1.4 算法分类

比较排序（基于元素两两对比）：冒泡、选择、插入、希尔、归并、快速、堆排序

非比较排序（基于数据特征，不两两对比）：计数等

二、七大比较排序算法（核心重点）

七大比较排序又分成4种类型的排序，分别为插入类排序，选择类排序，交换类排序，归并排序！

2.1插入排序

直接插入排序（Insertion Sort）

核心思想：模拟人手整理扑克牌，将数组分为有序前缀、无序后缀，逐个取出无序区元素，插入到有序区的正确位置。

执行流程：

1. 默认第一个元素为有序区

2. 依次取出后续元素作为待插入元素

3. 有序区元素向后移位，为待插入元素腾出位置

4. 插入元素，完成一轮排序

//直接插入排序----- ≈ O(N^2) void InsertSort(int* arr, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] > tmp) { arr[end+1] = arr[end]; end--; } else { break; } } arr[end + 1] = tmp; } }

复杂度与特性：

• 最优时间：O(n)（数组完全有序）

• 最坏/平均时间：O(n²)

• 空间复杂度：O(1)（原地排序）

• 稳定性：稳定

优缺点 & 场景：小规模数据、基本有序数据效率极高，是工程默认小额排序方案（快速排序、归并排序的底层辅助排序）。

希尔排序（Shell Sort）

核心思想：插入排序的优化版，也叫“缩小增量排序”。先将数组按固定增量分组，对每组做插入排序；逐步缩小增量，直至增量为1（全局插入排序），让数组提前趋于有序，大幅减少移位次数。

执行流程：

1. 初始化增量 gap = 数组长度 // 2

2. 按 gap 分组，组内执行插入排序

3. gap = gap // 2，重复分组排序

4. gap=1 时完成全局排序

//希尔排序 --- ≈ O(N^1.3) void ShallSort(int* arr, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end = end - gap; } else { break; } } arr[end + gap] = tmp; } } }

复杂度与特性：

• 平均时间：O(nlogn)，最坏 O(n²)

• 空间复杂度：O(1)（原地排序）

• 稳定性：不稳定（跨组交换打乱相等元素顺序）

优缺点 & 场景：优化了插入排序的低效问题，中等数据量表现较好，代码简单，常用于嵌入式、轻量化排序场景。

2.2选择排序

直接选择排序（Selection Sort）

核心思想：将数组分为有序区和无序区，每一轮遍历无序区，找到最小值，与无序区首位交换，逐步扩大有序区。

执行流程：

1. 初始有序区为空，无序区为整个数组

2. 遍历无序区，记录最小值下标

3. 最小值与无序区第一个元素交换，有序区长度+1

4. 重复直至全部有序

优化方法：

既然是直接找最小值那么可以也顺便找了最大值

最小值和array[left]交换，left++

最大值和array[right]交换，right--

这样就省下了很大的时间来提高了效率

以下的视图是只找一个最小值

//直接选择排序(优化版) void SelectSort(int* arr, int n) { for (int begin = 0, end = n - 1; begin < end; begin++, end--) { int mini = begin; int maxj = begin; for (int k = begin +1; k <= end; k++) { if (arr[k] < arr[mini]) mini = k; if (arr[k] > arr[maxj]) maxj = k; } if (arr[begin] == arr[maxj]) { maxj = mini; } Swap(&arr[begin], &arr[mini]); Swap(&arr[end], &arr[maxj]); } }

• 所有情况时间：O(n²)（核心误区纠正：优化后依然是平方级复杂度）

• 空间复杂度：O(1)（原地排序，无额外空间开销）

• 稳定性：不稳定（首尾交换操作极易打乱相等元素相对顺序）

• 所有情况时间：O(n²)（无论是否有序，都需遍历找最小值）

• 空间复杂度：O(1)（原地排序）

• 稳定性：不稳定（交换操作会打乱相等元素顺序）

堆排序（Heap Sort）

在学习堆排序之前，

我们还需要补充一个之前遗漏的知识点：

我们目前对堆的了解还停留在向上调整和向下调整，但待排序的数组是乱序的，而向上、向下调整只能处理有序的插入或删除。因此，这里引入一个新知识点——调整建堆。

向下调整 AdJustDown：

思想：针对某个节点，将其与左右孩子比较，把最大的元素换上来，再向下递归，保证以该节点为根的子树始终满足堆的性质。

• 使用场景：原地建堆（Heapify）
• 建堆做法：从最后一个非叶子节点开始，向前依次对每个节点执行向下调整。
• 时间复杂度：\(O(n)\)，真正线性时间，考试标准答案。
• 逻辑：先处理下层子树使其成为堆，再向上逐层合并。

for (int father = (n-1-1) / 2; father >= 0; father--) { AdJustDown(arr, father, n); }

重点：向下调整是父找孩子，往下沉。

向上调整 AdJustUp:

思想：某个叶子结点，不断跟自己的父节点对比，如果比父大就交换，一直往上，直到不违反堆性质。

• 使用场景：堆的插入（新元素插在数组末尾，然后向上调整）
• 如果用向上调整来 “建堆”：把元素一个一个依次插入堆，每插入一个就 shiftUp。
• 时间复杂度：\(O(n\log n)\)
• 逻辑：每新增一个叶子，向上冒泡

for(i = 1; i < n; i++) AdJustUp(arr, i);

到这里建堆的知识就这样完成了

接下来就可以看堆排序了；

核心思想：利用大顶堆（父节点大于子节点）特性，将数组构建为大顶堆，堆顶为最大值，将堆顶与末尾元素交换，末尾有序；再调整剩余堆结构，重复交换，最终实现整体有序，

这样可以构成升序序列（从小到大）。

利用小根堆可特性，将数组构建成小根堆，堆顶为最小值，将堆顶与末尾元素交换，末尾有序；调整剩余的堆结构，重复交换，最终整体有序，这样可以构成降序序列（从大到小）。

本文上述建堆方式就是小根堆，将向上，向下调整里面的大于，小于符号改变可以建成大顶堆。

执行流程：构建大顶堆 → 交换堆顶与末尾 → 调整堆结构 → 循环排序

构建小根堆 → 交换堆顶与末尾 → 调整堆结构 → 循环排序

无论向上调整建堆还是向下调整建堆，都是可以建成堆，堆顶和末尾元素交换后在向下调整，就可以得到一个有序的素组。

//向下调整算法 void AdJustDown(int* arr, int father,int n) { int child = father * 2 + 1; //从上到下对左右孩子与根节点比较 while (child < n) { //大根堆 < //小根堆 > if (child + 1 < n && arr[child] > arr[child + 1]) { child = child + 1; } //大根堆 < //小根堆 > if (arr[father] > arr[child]) { Swap(&arr[father], &arr[child]); father = child; child = father * 2 + 1; } else { break; } } } //向上调整算法 void AdJustUp(int* arr, int n) { //从下到上调整堆 int child = n - 1; int father = (child - 1) / 2; while (father >= 0) { //大根堆 < //小根堆 > if (arr[father] > arr[child]) { Swap(&arr[father], &arr[child]); child = father; father = (child - 1) / 2; } else { break; } } } //堆排序 void HeapSort(int* arr, int n) { //首先向下调整建堆-----O(N) for (int father = (n-1-1) / 2; father >= 0; father--) { AdJustDown(arr, father, n); } //向上调整建堆 ------O(NlongN) //for (int i =1; i < n; i++) //{ // //从两个元素开始建堆 // AdJustUp(arr, i+1); //} //进行向下调整 //最上面的元素拿到最下面，n-- while (n > 1) { Swap(&arr[0], &arr[n - 1]); n--; //只需要对堆顶做调整就好了 AdJustDown(arr, 0 , n); } }

堆排序的时间复杂度的分析

我们的堆排序是分为两种的：

一种是向上建堆排序：

1.首先看向上调整建堆的时间复杂度：

2.下面的循环要循环n次，要调整n次的堆

所以时间复杂度是O(nlogn)

总结：时间复杂度是O(n)+O(nlog) ~ O(nlogn)

一种是向下建堆排序：

1.先看向下调整建堆的时间复杂度：

2.下面的循环要循环n次，要调整n次的堆

所以时间复杂度是O(nlogn)

总结：时间复杂度是O(nlogn)+O(nlog) = O(2nlogn)

这里虽然也是 O(nlogn)但是向上调整建堆的复杂度是远远大与向下建堆的，这个o(nlongn)

比后者建堆多了logn的时间所以我们优先选择向下调整建堆

复杂度与特性：

• 所有情况时间：O(nlogn)

• 空间复杂度：O(1)（原地排序）

• 稳定性：不稳定

优缺点 & 场景：适合海量数据 TopK 问题（无需全量排序，仅维护堆结构），实时流式排序、大数据最值筛选首选。

2.3交换排序

冒泡排序（Bubble Sort）

核心思想：重复遍历数组，相邻元素两两对比，逆序则交换，每一轮遍历都会将当前最大元素“冒泡”到数组末尾，像气泡上浮。

执行流程：

1. 外层循环控制排序轮数，共需 n-1 轮

2. 内层循环对比相邻元素，大数后移

3. 每轮结束，末尾已有序，下一轮减少一次对比

4. 优化：设置标记，无交换则直接结束排序（数组已有序）

//冒泡排序 -----交换类 void BubbbleSort(int* arr, int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]); } } } }

复杂度与特性：

• 最优时间：O(n)（优化后，数组完全有序）

• 最坏/平均时间：O(n²)

• 空间复杂度：O(1)（原地排序）

• 稳定性：稳定

优缺点 & 场景：实现最简单、稳定性好，但效率极低，仅适用于小规模、基本有序的数据，工程几乎不用，仅教学入门。

快速排序（Selection Sort）【递归版本】

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法

核心思想：分治算法，任取待排序元素 序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左⼦序列中所有元素均小于基准值，右子序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为止。

执行流程

选取基准 pivot，右指针先走，左指针后走：

• right 从末尾向前，找小于 pivot的值停下来
• left 从开头向后，找大于 pivot的值停下来
• 两个指针不相遇就交换，重复操作
• left == right相遇，交换基准与相遇位置；该位置就是基准的最终有序位置
• 递归处理[begin,pos‑1]、[pos+1,end]

//快速排序(houre版) int hoare(int* arr, int left, int right) { int keyi = left; ++left; while (left <= right) { while (left <= right && arr[right] > arr[keyi]) { right--; } while (left <= right && arr[left] < arr[keyi]) { left++; } if (left <= right) { Swap(&arr[left++], &arr[right--]); } } Swap(&arr[right], &arr[keyi]); return right; } //快速排序---递归 void QuickSort(int* arr, int left, int right) { if (left > right) { return; } //需要参数来接受基准值 int mid = hoare(arr, left, right); //递归左右序列 QuickSort(arr, left, mid - 1); QuickSort(arr, mid + 1, right); }

hoare要思考一下几个问题：

1.如果数组中都是重复的数字呢，排序的效率呢？

2.如果重复数字多的话，排序效率如何呢？

3.可以优化吗？

首先这样的hoare版本并不可以的去优化它，一点也不智能，接下来我们来优化一下，引入hoare快排（三路划分）

//快速排序(三路快排) void ThreeSort(int* arr, int left, int right) { if (left >= right) return; // 递归终止条件 int begin = left; int end = right; //开始三路快排 int key = left; int cur =left + 1; //cur小于右才行 while (cur <= right) { if (arr[cur] < arr[key]) { Swap(&arr[cur], &arr[key]); ++key; ++left; } else if (arr[cur] > arr[key]) { Swap(&arr[cur], &arr[right]); --right; } else { ++cur; } } //递归左右序列 ThreeSort(arr, begin, left - 1); ThreeSort(arr, right + 1, end); }

1. 二路 Hoare 快排的痛点（重复元素多的时候会炸）

比如数组：[2,2,2,2,1,3]，大量重复的 2

• Hoare 二路分区：等于 key 的 2，会随机分到左区间或者右区间。
• 最坏情况：大量等值元素全部跑到一侧，递归树极度不平衡，时间复杂度退化到 \(O(n^2)\)。
• 重复元素并没有被 “一次性定位好”，后面递归还要继续拿这些 2 反复分区，做无用功。

2. 三路快排做了什么优化

三路划分后区间：[begin , left-1]：全部 < key[left , right]：全部 == key[right+1 , end]：全部 > key

中间[left, right]这一整段等于基准的元素，位置已经确定，后面递归完全不用管了！递归只处理：小于区[begin, left-1]、大于区[right+1, end]等于基准的这一大片直接 “抛弃出递归”，不再参与后续排序。

👉当数组存在大量重复数据时，性能提升巨大，避免二路快排的最坏\(O(n^2)\)退化

典型场景：考试分数排序、年龄排序，大量重复值，三路快排优势明显。

快速排序（lomuto版）

快速排序（lomuto版）于1986年Nico Lomuto提出的⽅法（前后指针法）

核心思想:

遍历数组，不断把小于等于基准的元素放到左边的小区间里，最后把基准放到小区间末尾。

执行流程：

选定一个基准值（一般选最右元素，也可以选最左），维护一个小于区的边界下标 small：

1. [left , small]：全部≤ key（基准）
2. [small+1 , i-1]：全部> key
3. i是遍历指针，从左向右扫描整个区间 遍历完成后，把基准元素交换到small+1的位置，这个位置就是基准的最终下标，返回它作为 mid； 然后递归处理左段[left, mid-1]和右段[mid+1, right]。

//快速排序(lomuto前后指针版) int Lomuto(int* arr, int left, int right) { int keyi = left; int prev = keyi, cur = prev + 1; while (cur <= right) { if (arr[cur] < arr[keyi]&& ++prev!=cur) { Swap(&arr[prev], &arr[cur]); } cur++; } Swap(&arr[prev], &arr[keyi]); return prev; } //快速排序---递归 void QuickSort(int* arr, int left, int right) { if (left > right) { return; } //需要参数来接受基准值 int mid = Lomuto(arr, left, right); //递归左右序列 QuickSort(arr, left, mid - 1); QuickSort(arr, mid + 1, right); }

快速排序【非递归版本】

递归的底层逻辑是栈，那么我们也可以用栈这个数据结结构来实现一下非递归版的；

这个栈和我们之前实现的栈是一样的；

可以把之前的栈的代码的.c文件和.h文件给拷贝到解决方案里面；

在编译器打开这两个文件，并且在该程序的顶部加上#include"stack.h"即可；

//快速排序(非递归版) void QuickSortNor(int* arr, int left, int right) { //定义一个栈 ST s; StackInit(&s); //先入栈两个区间 StackPush(&s, right); StackPush(&s, left); //对栈里面判空 while (!StackEmpty(&s)) { int begin = StackTop(&s); StackPop(&s); int end = StackTop(&s); StackPop(&s); //lomuto前后指针法 int keyi = begin; int prev = begin, cur = prev + 1; while (cur <= end) { if (arr[cur] < arr[keyi] ) { ++prev; Swap(&arr[prev], &arr[cur]); } cur++; } Swap(&arr[prev], &arr[keyi]); keyi = prev; //入栈 if (keyi + 1 < end) { StackPush(&s, end); StackPush(&s, keyi + 1); } if (begin < keyi - 1) { StackPush(&s, keyi - 1); StackPush(&s, begin); } } //销毁 StackDeTroy(&s); }

复杂度与特性：

• 平均/最优时间：O(nlogn)

• 最坏时间：O(n²)（有序数组未优化基准）

• 空间复杂度：O(logn)（递归栈空间，原地排序）

• 稳定性：不稳定

优缺点 & 场景：平均效率最高，Java、Python、C++ 标准库排序底层均基于快排优化（TimSort、pdqsort），适用于绝大多数通用排序场景。

2.4归并排序

归并排序（Merge Sort）

核心思想：分治算法经典实现，先分后合。将数组递归拆分为左右两个子数组，直至子数组长度为1（天然有序），再逐层合并两个有序数组，最终得到全局有序数组。

执行流程：拆分 → 递归排序子数组 → 合并有序数组

//方法 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 index = left; int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; //合并两个有序数组为一个数组 while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { tmp[index++] = arr[begin1++]; } if (arr[begin2] < arr[begin1]) { tmp[index++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { tmp[index++] = arr[begin2++]; } //将tmp的值返给到arr里面 for (int i = left; i <= right; i++) { arr[i] = tmp[i]; } } //归并排序 void MergeSort(int* arr, int n) { //开辟一个用来零时存放的数组 int* tmp = (int*)malloc(sizeof(int) * n); //排序 _MergeSort(arr, 0, n-1, tmp); free(tmp); }

复杂度与特性：

• 所有情况时间：O(nlogn)（稳定最优复杂度）

• 空间复杂度：O(n)（需要临时数组存储合并结果，非原地）

• 稳定性：稳定

优缺点 & 场景：时间复杂度绝对稳定，适合海量数据、外部排序（超内存数据），是多路归并、流式排序的核心算法；缺点是占用额外内存。

三、非排序算法

3.1计数排序

计数排序又称为鸽巢原理，是对哈希直接地址的变形应用

（1）统计相同元素出现的次数

（2）根据统计结果将序列回收到原来的序列中

核心思想：统计每个数值出现的次数，基于统计结果直接重构有序数组，适合整数、数值范围小的数据。

复杂度：时间 O(n+k)，空间 O(k)（k 为数据最大值），稳定排序。

场景：学生成绩排序、年龄排序、小规模整数数据。

//计数排序 void CountSort(int* arr, int n) { int max = arr[0]; int min = arr[0]; //找最大最小值拿到中间的区间 for (int i = 0; i < n; i++) { if (max < arr[i]) { max = arr[i]; } if (min > arr[i]) { min = arr[i]; } } //开辟一个计数的空间(也可以使用calloc) int index = 0; int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail!"); exit(1); } memset(count, 0, sizeof(int) * range); //统计数组出现的个数 for (int i = 0; i < n; i++) { count[arr[i] - min]++; } //将统计的结果返回给原数组 for (int i = 0; i < n; i++) { while (count[i] > 0) { arr[index++] = i+min; count[i]--; } } }

四、八大排序算法终极对比表

五、工程选型总结（面试+实战必背）

1. 通用场景首选快速排序：平均效率最高，标准库排序底层核心

2. 需要稳定排序、海量外部数据：选归并排序

3. 小规模、基本有序数据：插入排序最优

4. 大数据取TopK、最值：堆排序专属场景

5. 有明确数据范围的整数/固定位数数据：优先非比较排序（计数/基数）

6. 绝对避免：冒泡、选择排序（仅学习，不落地）

六、面试高频考点

• 最快的排序：平均快排、最坏归并

• 稳定排序：冒泡、插入、归并、所有非比较排序

• 原地排序：冒泡、选择、插入、希尔、堆排序

• 分治算法排序：快排、归并