八大排序算法详解与性能对比分析

详细讲解了八大排序算法（直接插入、希尔、简单选择、堆、冒泡、快速、归并、计数）的原理与 C 语言实现。通过实际测试对比了各算法在不同数据规模下的运行时间，分析了时间复杂度、空间复杂度及稳定性。结论表明快速排序在平均情况下性能最优，计数排序适用于小范围整数，而堆排序和归并排序则适合对稳定性或最坏情况有要求的场景。

FrontendX发布于 2026/3/27更新于 2026/4/161 浏览

引言

本文详细讲解了八大排序算法（直接插入、希尔、简单选择、堆、冒泡、快速、归并、计数）的原理与 C 语言实现。通过实际测试对比了各算法在不同数据规模下的运行时间，分析了时间复杂度、空间复杂度及稳定性。

算法性能实测

测试背景

在理论分析之外，通过程序实际运行来精确测试这些排序算法的速度，以验证理论值在实际应用场景中的表现。

头文件

Sort.h

#pragma once
//任务 1：包含要使用头文件
#include <stdio.h>
#include <time.h>
#include <string.h>
#include "Stack.h"

//任务 2：声明排序要使用的一些辅助的函数
//0.数组中元素的打印
//1.数组中两个元素的交换
//2.堆排序的向下调整算法
//3.三数取中
void PrintArray(int* a, int n);
void Swap(int* a, int* b);
void AdjustDown(int* a, int parent, int n);
int GetMid(int* a, int left, int right);

//任务 3：声明要实现的排序算法函数
/*------------------------------------------比较排序------------------------------------------*/
/*---------------------插入排序---------------------*/
//1.直接插入排序

 ;
 ;




 ;
 ;





 ;
 ;
 ;




 ;
 ;



 ;

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include "Sort.h" /****************************************************** 实现：辅助函数 ******************************************************/ /*==============================================='数组中元素的打印'===============================================*/ //1.实现：'数组中元素的打印'辅助函数 void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /*==============================================='数组中的两个元素的交换'===============================================*/ //2.实现：'数组中的两个元素的交换'辅助函数 void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } /*==============================================='堆的向下调整'===============================================*/ //3.实现：'堆的向下调整'辅助函数 /** * @brief 堆的向下调整算法（大顶堆） * @param a 堆数组 * @param parent 需要调整的父节点索引 * @param n 堆的大小 * * 算法功能： * 1. 确保以 parent 为根的子树满足大顶堆性质 * 2. 若父节点小于子节点，则交换并继续向下调整 * * 执行过程： * 1. 从父节点出发，找到较大的子节点 * 2. 比较父子节点值，若父节点较小则交换 * 3. 循环执行直到满足堆性质或到达叶子节点 * * 时间复杂度：O(logN)（树的高度） */ void AdjustDown(int* a, int parent, int n) { //思路：向下调整的本质：是判断父节点的值和左右孩子的值的大小关系，并将父子关系不满足大根堆条件（孩子大于父亲）的情况进行交换调整 //所以我任务是 //任务 1：找到父节点孩子中值最大的那个孩子 //任务 2：判断父节点和孩子节点的大小关系，并进行调整 //1.先假设父节点的左孩子是值最大的孩子 int maxChild = (parent << 1) + 1; //注意 1：这里还用 +1，因为这里是 maxChild 和 parent 都是数组的下标 //注意 2：位运算符的优先级比算数运算符的优先级小 ---> 一般情况下：如果位运算符我们不写在表达式的最后的话，都要添加 () 来提高优先级 //2.循环进行交换调整 while (maxChild < n) //当孩子的索引值 >= n 的时候，说明进行调整到不能在调整了 { //3.确定父节点的值最大的孩子节点 if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) { maxChild = maxChild + 1; } //4.判断父节点和孩子节点的大小关系 if (a[parent] >= a[maxChild]) return; else { //4.1: 交换 Swap(&a[parent], &a[maxChild]); //4.2：更新 parent = maxChild; //4.3：寻找 parent = maxChild; maxChild = (parent << 1) + 1; } } } //4.实现：'三数取中'辅助函数 /** * @brief 三数取中法选择基准值 * @param a 数组指针 * @param left 左边界索引 * @param right 右边界索引 * @return 返回左、中、右三数中的中间值索引 * @note 用于快速排序优化，避免最坏情况时间复杂度退化 */ int GetMid(int* a, int left, int right) { //1.计算中间值 int mid = (left + right) >> 1; //2.处理情况 1：a[left] < a[mid] if (a[left] < a[mid]) { if (a[right] < a[left]) { return left; } else if (a[right] > a[mid]) { return mid; } else return right; } //3.处理情况 2：a[left] > a[mid] else { if (a[right] > a[left]) { return left; } else if (a[right] < a[mid]) { return mid; } else return right; } } /****************************************************** 实现：排序函数 ******************************************************/ /*--------------------------------------------------------------------插入排序--------------------------------------------------------------------*/ /*==============================================='直接插入排序'===============================================*/ //1.实现：'直接插入排序' /** * @brief 直接插入排序 * @param a 待排序数组 * @param n 数组长度 * @note 时间复杂度: * 最坏 O(N^2) - 逆序情况 * 最好 O(N) - 已有序情况 */ void InsertSort(int* a, int n) { //1.外层的循环控制 ---> 记录当前数组中区间到那里已经是有序的了（解释：循环变量 i=n-2 意味着'当前数组中区间为 [0,n-1] 范围中的元素现在已经是有序的了'） for (int i = 0; i <= n - 2; i++) //注：i 虽然只能到 n-2 的但是当 i=n-2 的时候，我们正在处理的是下标为 n-1 位置的元素，也就是数组中的最后哦一个元素 { //2.记录当前数组中已经有序区间的右下标 int end = i; //3.取出我们要进行插入排序的元素 int tmp = a[end + 1]; //4.内层的循环控制 ---> 寻找我们要插入的位置 while (end >= 0) { //核心：前面元素的值大进行后移 if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { break; } } //注意：因为 end 的值变为 -1 而退出的 while 循环的情况：意味着当前处理的这个元素的值比数组中区间为 [0,end] 的已经有序元素的任意一个元素的值都要小 a[end + 1] = tmp; } } /*==============================================='希尔排序'===============================================*/ //2.实现：'希尔排序' /** * @brief 希尔排序 * @param a 待排序数组 * @param n 数组长度 * @note 时间复杂度：O(N^1.3) * 基于插入排序的改进，通过分组预排序提高效率 */ /*希尔排序原理： * 1. 是插入排序的改进版本，通过分组预排序提高效率 * 2. 使用动态缩小的间隔序列 (gap) 对数据进行分组 * 3. 对每个分组进行插入排序 * 4. 最终当 gap = 1 时，就是标准的插入排序，此时数组已基本有序 */ void ShellSort(int* a, int n) { //1.初始化间隔为数组的长度 int gap = n; //2.第一层循环 ---> 动态的调整间隔的序列 while (gap > 1) { // 计算新的间隔，使用 Knuth 提出的序列：h = h/3 + 1（这个序列在实践中表现较好） gap = gap / 3 + 1; //注：接下来的实现主要有两种实现的方式：分别是： //1.严格分组法 //2.交叉分组法 //注：这两种方法性能上没有什么明显的区别，只是交叉分组法更加简洁，大多数的人都使用交叉分组法 /*--------------------------展示：严格分组法--------------------------* //第二层循环 ---> 控制我们处理组 for (int group = 0; group < gap; group++) { //第三层循环 ---> 控制已排序区间的右边界 for (int i = group; i <= n - gap - 1; i++) { int end = i; int tmp = a[end + gap]; //第三层循环 ---> 寻找我们要插入的位置 while (end >= 0) { //核心：前面的元素的值大时进行后移 if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } *//*--------------------------展示：交叉分组法--------------------------*/ //第二层循环 ---> 控制已排序区间的右边界 for (int i = 0; i <= n - gap - 1; i++) { int end = i; int tmp = a[end + gap]; //第三层循环 ---> 寻找我们要插入的位置 while (end >= 0) { //核心：当前面的元素的值大进行后移 if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } /*--------------------------------------------------------------------选择排序--------------------------------------------------------------------*/ /*==============================================='简单选择排序'===============================================*/ //1.实现：'简单选择排序' /** * @brief 简单选择排序 * @param a 待排序数组 * @param n 数组长度 * @note 时间复杂度：O(N^2) * 每次选择最小和最大元素放到首尾位置 */ void SelectSort(int* a, int n) { //1.记录选择排序的区间边界（解释：在区间之外的元素已经有序） //注：这里进行了优化，原始的直接选择排序进行一个次排序只会找到未排序区间中的最小的元素，这里优化为一次可以找到：最大的元素和最小的元素 int begin = 0, end = n - 1; //2.记录区间内值最大和最小的元素的下标 int minn, maxx; //3.外层循环 ---> 控制已排序区间的左右边界（解释：beigin=3,end=n-4 代表：数组中下标为 [3,n-4] 这个区间的中的元素还没有进行排序） while (begin < end) { //4.初始化当前数组未排序区间中元素的最大值和最小值元素的下标为 begin minn = begin, maxx = begin; //5.内层循环 ---> 寻找未排序区间中实际的最小/最大值索引 for (int i = begin + 1; i <= end; i++) { //5.1：更新最小值的索引 if (a[i] < a[minn]) { minn = i; } //5.2：更新最大值的索引 if (a[i] > a[maxx]) { maxx = i; } } //6.进行元素位置的交换 //6.1：将最小值交换到区间的头部 Swap(&a[minn], &a[begin]); //6.2：修正最大值在数组中的下表中的位置 /* 关键修正：处理最大值正好在 begin 位置的特殊情况 * 因为先交换了 begin 和 minn，可能导致 maxx 指向的值被移动 * 例子：[5, 3, 1, 4, 2] 中： * - 第一轮 begin=0, maxx=0, minn=2 * - 交换 begin 和 minn 后变为 [1, 3, 5, 4, 2] * - 此时原 maxx=0 的值已被移动到 minn=2 的位置 */ if (maxx == begin) { maxx = minn; } //6.3：将最大值交换到区间的尾部 Swap(&a[maxx], &a[end]); //7.缩小未排序区间 begin++; end--; } } /*==============================================='堆排序'===============================================*/ //2.实现：'堆排序' /** * @brief 堆排序算法实现 * @param a 待排序数组 * @param n 数组长度 * * 算法特性： * 1. 时间复杂度： * - 建堆过程：O(N) * - 排序过程：O(N*logN) * - 总体：O(N*logN) * * *核心思想： * - 将数组视为完全二叉树，建立大顶堆 * - 反复取出堆顶元素（最大值）放到数组末尾 * - 重新调整剩余元素维持堆结构 */ void HeapSort(int* a, int n) { /*------------------第一阶段：建堆------------------*/ //建堆的方法有两种： //1.向上调整建堆 //2.向下调整建堆 //注：这两种方法有明显的性能差别，向下调整建堆算法的时间复杂度更小，使用的人也更多 //建堆本质：从堆中最后一个非叶子节点到堆顶节点逐个使用：向下调整算法 for (int i = (n - 1 - 1) >> 1; i >= 0; i--) { AdjustDown(a, i, n); } /*------------------第二阶段：将堆顶元素与末尾的元素进行交换 + 向下调整堆------------------*/ //1.定义一个变量记录当前堆中最后一个元素的在数组中的索引 int end = n - 1; //2.循环进行第二阶段直到堆对应的数组中只剩下标为 0 的元素的值还没用进行交换的时候 while (end > 0) { //2.1：将堆顶元素与末尾的元素进行交换 Swap(&a[0], &a[end]); //2.2：更新堆对应数组的容量 ---> （逻辑上：删除了堆顶元素） end--; //2.3：重新向下调整堆 AdjustDown(a, 0, end + 1); } } /*--------------------------------------------------------------------交换排序--------------------------------------------------------------------*/ /*==============================================='冒泡排序'===============================================*/ //1.实现：'冒泡排序' /** * @brief 冒泡排序 * @param a 待排序数组 * @param n 数组长度 * @note 时间复杂度: * 最坏 O(N^2) - 逆序情况 * 最好 O(N) - 已有序情况 */ void BubbleSort(int* a, int n) { //1.外层的循环控制 ---> 记录需要进行交换的数字的个数 ['也可理解为冒泡的总的趟数']（解释：n 个数字只需要对 n-1 个数字进行排序即可实现 n 个数字的有序） for (int i = 1; i <= n - 1; i++) { //2.内层的循环控制 ---> 记录对每个数字进行排序需要交换的次数 ['也可以理解为每趟冒泡需要交换的次数']（注意：每趟冒泡需要交换的次数是不同的） //每趟冒泡需要交换的次数会逐渐的减少，次数类似于一个等差数列，例如：n 个元素的一个数组 //第一趟的冒泡需要比较的次数：n-1 //第二趟的冒泡需要比较的次数：n-2 //第三趟的冒泡需要比较的次数：n-3（总结：每趟冒泡需要交换的次数为 = 元素的总个数 n - 这是冒泡的第几趟 i） //……………………………… //第 n-2 趟的冒泡需要比较的次数：2 //第 n-1 趟的冒泡需要比较的次数：1 //对冒泡排序进行优化： int flag = 1; for (int j = 1; j <= n - i; j++) { //核心：前面的元素的值大进行交换 if (a[j - 1] > a[j]) { Swap(&a[j - 1], &a[j]); flag = 0; } } if (flag) break; //如果某一趟的冒没有进行交换，说明当前数组中的元素已经有序了，则直接退出 } } /*==============================================='快速排序'===============================================*/ //2.实现：'快速排序' /** * @brief 快速排序 * @param a 待排序数组 * @param left 左边界 * @param right 右边界 * @note 时间复杂度: * 平均 O(NlogN) * 最坏 O(N^2) - 已排序情况 * 空间复杂度：O(logN) - 递归栈空间 */ //说明：快速排序无疑是所有的排序算法中的明星，其版本也是有很多种 //1.hoare 法（原版） //2.lomuto 快慢指针法 //3.挖坑法 //同时由于快速排序：是一个分治算法，它将数组分成两个子数组，然后递归地对子数组进行排序 //也就是说快速排序的实现牵扯到了递归，然而递归的深度越深就越有可能导致栈溢出，所以为了降低这种风险，博主还会带大家实现 //4.快速排序的非递归版本 /* //1.这里先给大家写一个比较常使用的模板，步骤详细以供参考，后面的快排方法博主会封装为两个函数去实现以避免不必要的重复 //----------------------快速排序的模板：hoare 法的实现（经过两处优化）---------------------- void QucikSort(int* a, int left, int right) { //1.处理特殊的情况：'区间中没有元素 + 区间中只有一个元素'（同是也是递归终止条件） if (left >= right) return; //---------优化 1：'小区间优化：当子数组元素少于 10 时，使用插入排序提高效率'--------- if ((right - left + 1) < 10) { InsertSort(a + left, right - left + 1); } else { //---------优化 2：'三数取中优化：选择左、中、右三个元素的中间值作为基准'--------- int mid = GetMid(a, left, right); //4.将基准值放到左边界 Swap(&a[left], &a[mid]); //5.定义一个变量记录基准值的索引 int key = left; //6.定义两个临时变量用来左右扫描区间 int begin = left, end = right; //7.使用双边循环法分区 while (begin < end) { //7.1:从右向左找第一个小于基准的值 //注意细节：这里要先进行从右向左找第一个小于基准的值 ---> 这样可以确保最终两个指针停下来的位置的值一定小于基准 while (begin < end && a[end] >= a[key]) //注意：这里还要判断 begin<end，防止 end 越界，下面的 while 循环也是如此 { end--; } //7.2:从左向右找第一个大于基准的值 while (begin < end && a[begin] <= a[key]) { begin++; } //7.3:交换这两个不符合条件的元素 Swap(&a[begin], &a[end]); } //8.将基准值放到正确的位置（此时 begin == end） Swap(&a[key], &a[begin]); //9.更新基准值的位置 key = begin; //10.递归排序左右子分区：[left, key-1] key [key+1, right] QuickSort(a, left, key - 1); QuickSort(a, key + 1, right); } } *//*----------------------hoare 法的实现（未进行优化版本）----------------------*/ //看到上面的标题，我想大多数的人会直接会跳过这实现，而转去学习其他的经过优化的实现方法，你说我说的对吗？ //没有进行优化的快排难道就没有学习的必要吗？当然不是这样的，博主认为学习的价值有以下几点 //1.可以让我们抓住快排的核心 //2.可让我们学习快排过程更加的平滑 //3.在面试的时候时间紧，可以选择手撕未优化的快排以提高容错率，再简明扼要的说明可以进行优化的地方以彰显水平 /*----------------------hoare 分区算法（未进行优化）----------------------*/ int PartSort1(int* a, int left, int right) { //1.直接选择左边界的元素作为基准值 int key = left; //2.定义两个临时变量从区间的两端向中间进行扫描 ---> 高效地将数组分为两部分 //使得一部分元素小于等于基准值，另一部分元素大于等于基准值，进而将基准值放置到其最终排序位置上 int begin = left, end = right; //3.使用双边循环法分区 while (begin < end) { //3.1：从右向左寻找第一个小于基准的值 while (begin < end && a[end] >= a[key]) { end--; } //3.2：从左向右寻找第一个大于基准的值 while (begin < end && a[begin] <= a[key]) { begin++; } //3.4：交换这两个不符合条件的元素 Swap(&a[begin], &a[end]); } //4.将基准值放到正确的位置（此时 begin == end） Swap(&a[key], &a[begin]); //5.返回当前基准值的下标 return begin; } /*----------------------lomuto 快慢指针分区算法----------------------*/ /** * @brief 前后指针法实现快速排序分区 * @param a 数组指针 * @param left 左边界索引 * @param right 右边界索引 * @return 返回基准值的最终位置 */ int PartSort2(int* a, int left, int right) { //1.进行三数取中优化：基准值的选取 int mid = GetMid(a, left, right); //2.将找到的基准值放在左边界 Swap(&a[left], &a[mid]); //3.定义一个变量记录基准值的索引 int key = left; //4.定义一个慢指针：用于指向最后一个小于基准值的元素 int slow = left; //5.定义一个快指针：用于扫描整个分区 int fast = slow + 1; //6.进行分区 while (fast <= right) { if (a[fast] < a[key] && ++slow != fast) { Swap(&a[fast], &a[slow]); } fast++; } //7.将基准值交换到最终的位置（此时 slow 指向最后一个小于基准的元素） Swap(&a[key], &a[slow]); //8.返回当前基准值的下标 return slow; } /*----------------------挖坑分区算法----------------------*/ /** * @brief 挖坑法实现快速排序分区 * @param a 待排序数组 * @param left 左边界索引 * @param right 右边界索引 * @return 基准值的最终位置 * @note 时间复杂度：O(N) * 空间复杂度：O(1) */ int PartSort3(int* a, int left, int right) { //1.进行三数取中优化：基准值的选取 int mid = GetMid(a, left, right); //2.将找到的基准值放在左边界 Swap(&a[left], &a[mid]); //3.定义一个变量记录基准值 (注意这里保存值而不是索引) int key = a[left]; //特别注意：这的 key 存储的不再是基准值的下标，而是直接存储的基准值，这是为什么呢？（下面的注释博主有详细的解释，请继续往下看……） //4.定义一个变量记录坑位 int hole = left; //5.定义两个临时变量从区间的两端向中间进行扫描 ---> 高效地将数组分为两部分 int begin = left, end = right; //6.进行分区 while (begin < end) { //6.1：从右向左寻找第一个小于基准的值 while (begin < end && a[end] >= key) { end--; } //6.2：找到后填左坑，end 成为新坑 a[hole]= a[end]; //特别注意：这里 while 循环结束后并不是紧接又是一个 while 循环，而是做填坑、挖坑的操作，也恰恰是这个填坑、挖坑的操作使得基准值的下标已经发生了改变 hole = end; //所以说：我们下面就不可以使用 a[key]（假设：key 存储的还是基准值的下标）的方式来得到基准值了， //6.3：从左向右寻找第一个大于基准的值 while (begin < end && a[begin] <= key) { begin++; } //6.4：找到后填右坑，left 成为新坑 a[hole]= a[begin]; hole = begin; } //7.最后将基准值填入最后的坑位 a[hole] = key; //8.返回当前基准值的下标 return hole; } /*----------------------快排主函数（递归实现）----------------------*/ /** * @brief 快速排序（非递归实现） * @param a 待排序数组 * @param left 左边界索引 * @param right 右边界索引 * @note 使用栈模拟递归过程 */ void QuickSort(int* a, int left, int right) { //1.递归终止条件 if (left >= right) return; //2.可以根据需要选择性的在这里添加小区间优化（比如：之前已经实现过了插入排序就可以在这里进行小区间优化了） //3.定义一个变量接收基准值的位置 int key = PartSort3(a, left, right); //4.递归排序左右子区间 QuickSort(a, left, key - 1); QuickSort(a, key + 1, right); } /*----------------------快排排序（非递归实现）----------------------*/ /** * @brief 快速排序（非递归实现） * @param a 待排序数组 * @param left 排序区间左边界 * @param right 排序区间右边界 * @note 时间复杂度：O(NlogN) * 空间复杂度：O(logN)（栈空间） * 算法步骤： * 1. 使用栈保存待处理的区间 * 2. 循环处理栈中的区间直到栈空 * 3. 对每个区间进行分区操作 * 4. 将新生成的子区间压入栈中 */ void QuickSortNonR(int* a, int left, int right) { /*---------------第一阶段：准备数据阶段---------------*/ //1.创建栈 + 初始化栈 STK stk; STKInit(&stk); //2.先将整个数组区间压栈（注意顺序：先右后左） STKPush(&stk, right); STKPush(&stk, left); /*---------------第二阶段：循环处理阶段---------------*/ //3.循环处理栈的中的元素直至栈为空 while (!STKEmpty(&stk)) { //4.弹出当前处理区间的左右边界 int begin = STKTop(&stk); STKPop(&stk); int end = STKTop(&stk); STKPop(&stk); //5.选择任意的分区算法对当前的区间进行分区 int key = PartSort3(a, begin, end); //6.将存在的区间压入栈中 //6.1：先将右子区间 [key+1, end] 入栈（如果存在的话） if (key + 1 < end) { STKPush(&stk, end); STKPush(&stk, key + 1); } //6.2:再将左子区间 [left,key-1] 入栈（如果存在的话） if (begin < key - 1) { STKPush(&stk, key - 1); STKPush(&stk, begin); } } /*---------------第三阶段：释放资源阶段---------------*/ STKDestroy(&stk); } /*--------------------------------------------------------------------归并排序--------------------------------------------------------------------*/ /*==============================================='归并排序'===============================================*/ //1.实现：'归并排序' /** * @brief 归并排序的核心递归函数 * @param a 待排序的原始数组（排序后结果也存放在此） * @param tmp 临时工作数组，大小应与原数组相同 * @param begin 当前处理区间的起始下标（包含） * @param end 当前处理区间的结束下标（包含） * * @details * 1. 递归地将数组分成两半直到最小单元（单个元素） * 2. 然后自底向上地合并两个已排序的子数组 * 3. 合并过程使用双指针技术，保证稳定性 */ //和快速排序一样，博主这里也是通过封装两个函数来实现的归并排序的，目的都是为了避免编写重复的代码，提高代码复用性（其实是为了方便我使用递归） //主函数：MergeSort() 函数是入口，函数内部是一些可重复的代码 //子函数：_MergeSort() 函数是归并排序的核心 void _MergeSort(int* a, int* tmp, int begin, int end) { //1.处理特殊的情况：'区间中没有元素 + 区间中只有一个元素'（递归结束条件） if (begin >= end) return; //2.计算区间的中间点：（防溢出写法：begin + (end - begin)/2） int mid = begin + end >> 1; //装逼写法（不建议使用，请勿装逼） //3.递归处理左右子区间 //3.1：递归处理左子区间 _MergeSort(a, tmp, begin, mid); //3.2：递归处理右子区间 _MergeSort(a, tmp, mid + 1, end); //4.定义左右子数组的边界 + 临时数组的写入位置 int begin1 = begin, end1 = mid; //左子数组的边界 int begin2 = mid + 1, end2 = end; //右子数组的边界 int pos = begin; //5.双指针法合并：选择较小的元素优先放入 while (begin1 <= end1 && begin2 <= end2) //只要有一个子数组归并完毕循环就结束 ---> 两个数组都未完成归并 while 循环继续进行 { if (a[begin1] <= a[begin2]) //稳定排序的关键：相等时取前一个元素 { tmp[pos++] = a[begin1++]; } else tmp[pos++] = a[begin2++]; } //6.处理左右子数组剩余的元素 //6.1：处理左数组中的剩余的元素（如果有的话） while (begin1 <= end1) { tmp[pos++] = a[begin1++]; } //6.2：处理右数组中的剩余的元素（如果有的话） while (begin2 <= end2) { tmp[pos++] = a[begin2++]; } //7.将合并结果从 tmp 数组拷贝回原数组的对应的区间 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); //注意：只拷贝当前处理的范围 [begin, end] } /*----------------------归并主函数（递归实现）----------------------*/ void MergeSort(int* a, int n) { /*-----------------第一阶段：动态创建临时数组-----------------*/ int* tmp = (int*)malloc(n * sizeof(int)); if (tmp == NULL) { perror("malloc fail"); return; } /*-----------------第二阶段：调用核心排序函数-----------------*/ _MergeSort(a, tmp, 0, n - 1); //处理整个数组 [0, n-1] /*-----------------第三阶段：释放临时数组内存-----------------*/ free(tmp); tmp = NULL; } /*----------------------归并排序（非递归实现）----------------------*/ /** * @brief 归并排序（非递归实现） * @param a 待排序数组 * @param n 数组长度 * @note 时间复杂度：O(NlogN) - 每次归并 O(N)，共 logN 次 * 空间复杂度：O(N) - 需要额外 N 大小的临时空间 * 稳定性：稳定排序（相等元素的相对顺序不变） * * @details * 实现原理： * 1. 自底向上归并，先归并相邻的小区间，再逐步扩大归并区间 * 2. 使用 gap 控制当前归并的区间大小，从 1 开始每次翻倍 * 3. 对每个 gap，遍历整个数组进行两两归并 * 4. 处理边界情况，保证最后不足 gap 的部分也能正确归并 * * 优点： * - 避免了递归调用的栈空间开销 * - 更适合处理超大规模数据（不会栈溢出） */ //递归虽好，但是存在栈溢出的风险，所以我们还是有必要学习一下归并排序的非递归实现的 //说明：之前我们为实现快速排序的非递归使用的栈，但是归并的非递归不能简单的借助栈就能实现 //原因：快排的非递归类似二叉树的前序遍历，而递归类似于后序遍历，在递归过程中要先保存结果，在回溯阶段再进行归并 void MergeSortNonR(int* a, int n) { //1.动态创建临时数组 int* tmp = (int*)malloc(n * sizeof(int)); if (tmp == NULL) { perror("malloc fail"); return; } //2.定义一个变量记录归并子数组的大小 int gap = 1; //从 1 开始，单个元素视为已排序 //3.使用 while 循环进行循环归并 while (gap < n) //当子数组的大小 >= 原数组的长度时归并结束 ---> 反面即是 while 循环的条件 { //4.遍历整个区间，每次处理两个相邻的 gap 大小的区间 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; /*--------------------第二步：修正边界防止数组越界--------------------*/ //1）情况 1：第二个区间完全越界（无需归并） if (begin2 >= n) { break; } //2）情况 2：第二个区间部分越界（修正 end2） if (end2 >= n) { end2 = n - 1; } /*--------------------第三步：归并两个有序区间--------------------*/ //1.定义临时数组的写入位置 int pos = i; //2.双指针法合并两个区间 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) //稳定排序的关键：相等时取前一个元素 { tmp[pos++] = a[begin1++]; } else { tmp[pos++] = a[begin2++]; } } //3.处理左右子数组剩余的元素 //3.1：处理左数组中的剩余的元素（如果有的话） while (begin1 <= end1) { tmp[pos++] = a[begin1++]; } //3.2：处理右数组中的剩余的元素（如果有的话） while (begin2 <= end2) { tmp[pos++] = a[begin2++]; } //4.将归并结果拷贝回原数组（仅拷贝当前处理的范围） memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int)); } //5.扩大归并区间的大小 gap *= 2; } //6.释放资源 free(tmp); tmp = NULL; } /*--------------------------------------------------------------------计数排序--------------------------------------------------------------------*/ /*==============================================='计数排序'===============================================*/ //1.实现：'计数排序' /** * @brief 计数排序（非比较排序） * @param a 待排序数组 * @param n 数组元素个数 * * @note 特性： * - 时间复杂度：O(N+range)，range 为数据范围（max-min+1） * - 空间复杂度：O(range) * - 稳定性：稳定排序（但当前实现是非稳定版本） * - 限制：仅适用于整数且数据范围较小的场景 */ void CountSort(int* a, int n) { /*---------------第一阶段：确定数据的范围---------------*/ //1.使用假设法：先定义两个变量记作是数据中的最小/最大值 int minn = a[0], maxx = a[0]; //2.遍历数组寻找数组中的最大值和最小值 for (int i = 0; i < n; i++) { //2.1：修正最小值 if (a[i] < minn) { minn = a[i]; } //2.2：修正最大值 if (a[i] > maxx) { maxx = a[i]; } } //3.计算实际数据的范围 int range = maxx - minn + 1; /*---------------第二阶段：创建计数的数组---------------*/ int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { perror("calloc fail"); return; } /*---------------第三阶段：统计元素出现次数---------------*/ for (int i = 0; i < n; i++) //遍历原数组 [0,n] 的区间中的元素 { count[a[i] - minn]++; //将数据映射到 count 数组 [0,range-1] 区间中 } /*---------------第四阶段：重构待排序数组---------------*/ //1.定义元素数组的写入位置 int pos = 0; //2.使用 for 循环遍历 count 数组 for (int i = 0; i < range; i++) { //2.1：将 count 数组中元素转化为：元素的数量 while (count[i]--) { //2.2：将 count 数组的索引转化回：原始的值 a[pos++] = i + minn; } } /*---------------第五阶段：释放资源---------------*/ free(count); count = NULL; }

#include "Stack.h" //1.实现：'栈的初始化'的函数 void STKInit(STK* pstk) { assert(pstk); //确保指针非空 pstk->top = 0; pstk->capacity = 0; pstk->a = NULL; } //2.实现：'栈的销毁'的函数 void STKDestroy(STK* pstk) { assert(pstk); pstk->top = 0; pstk->capacity = 0; free(pstk->a); pstk->a = NULL; } //3.实现：'栈的入栈操作'的函数 void STKPush(STK* pstk, STKDateType x) { //第一部分：确保指针非空 assert(pstk); //第二部分：检查是否需要进行扩容 if (pstk->top == pstk->capacity) { //1.需要进行扩容 ---> 新容量是多少？ int newCapacity = pstk->capacity == 0 ? 4 : pstk->capacity * 2; //2.开始进行扩容 STKDateType* tmp = (STKDateType*)realloc(pstk->a, newCapacity * sizeof(STKDateType)); //3.检查扩容是否成功 if (tmp == NULL) { perror("realloc false"); return; } //4.更新指向动态数组的指针 pstk->a = tmp; //5.更新栈的容量 pstk->capacity = newCapacity; } //第三部分：实现入栈操作 pstk->a[pstk->top] = x; pstk->top++; } //4.实现：'栈的出栈操作'的函数 void STKPop(STK* pstk) { assert(pstk); //确保指针不为空 assert(pstk->top > 0); //确保栈不为空 pstk->top--; } //5.实现：'栈的取栈顶元素的操作'的函数 STKDateType STKTop(STK* pstk) { assert(pstk); assert(pstk->top > 0); return pstk->a[pstk->top - 1]; //注意：千万别写成这个样子 pstk->a[pstk->top--]；这样会先会修改 top 值 } //6.实现：'栈的判空操作'的函数 bool STKEmpty(STK* pstk) { assert(pstk); //if (pstk->top = 0) return true;//else return false //1.栈为空 --> 返回 true //2.栈不为空 ---> 返回 false return pstk->top == 0; } //7.实现：'栈的求栈中元素数量的操作'的函数 int STKSize(STK* pstk) { assert(pstk); return pstk->top; }

排名	排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度
🥇	快速排序	O(n log n)	O(n log n)	O(n²)
🥈	归并排序	O(n log n)	O(n log n)	O(n log n)
🥉	堆排序	O(n log n)	O(n log n)	O(n log n)
4	希尔排序	O(n^1.3)	O(n log n)	O(n²)
5	直接插入排序	O(n²)	O(n)	O(n²)
6	冒泡排序	O(n²)	O(n)	O(n²)
7	简单选择排序	O(n²)	O(n²)	O(n²)
8	计数排序	O(n × k)	O(n × k)	O(n × k)

八大排序算法详解与性能对比分析

引言

算法性能实测

测试背景

头文件

Sort.h

更多推荐文章

相关免费在线工具

Stack.h

实现文件

Sort.c

Stack.c

测试结果

算法性能分析

一、直接插入排序

二、简单选择排序

三、冒泡排序

四、希尔排序

五、堆排序

六、快速排序

七、归并排序

八、计数排序

八大排序算法详解与性能对比分析

引言

算法性能实测

测试背景

头文件

Sort.h

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

Stack.h

实现文件

Sort.c

Stack.c

测试结果

算法性能分析

一、直接插入排序

二、简单选择排序

三、冒泡排序

四、希尔排序

五、堆排序

六、快速排序

七、归并排序

八、计数排序