七大排序算法深度解析：从原理到代码实现-海口c网

1.排序

排序算法是计算机科学中最基础的技能之一，无论你是编程新手还是经验丰富的开发者，理解这些算法都能显著提升代码效率。本文将用最简单的方式，带你快速掌握七大经典排序算法的核心原理与实现。

1.1排序概念及其运用

排序是指将一组数据按照特定规则（如升序或降序）重新排列的过程。排序是计算机科学中最基础且重要的操作之一，广泛用于优化数据检索、提高算法效率以及简化复杂问题的处理。

排序的主要应用场景

数据库查询：加速数据检索（如索引排序）。
搜索算法：二分查找要求数据有序。
数据分析：统计、去重、Top-K问题（如排行榜）。
任务调度：按优先级处理任务。
文件系统：按文件名、日期排序文件。

1.2常见排序算法

常见排序算法
本次将系统介绍7种经典排序算法，重点从时间复杂度、空间复杂度、稳定性三个维度展开分析，时间复杂度和空间复杂度的概念在之前博客中有所讲解，现在来说明一下排序算法稳定性的概念。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

2.插入排序

插入排序的基本思想是：把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插入完为止，得到⼀个新的有序序列。

2.1直接插入排序

直接插入排序的思想是：当插入第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时用array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进进行较，找到插入位置将 array[i] 插⼊，原来位置上的元素顺序后移。
动图：
在这里插入图片描述

实现代码：

//直接插入排序
/** 直接插入排序算法实现* 参数说明：*   arr - 待排序数组首地址*   n   - 数组元素个数* 特性：*   - 时间复杂度：O(n²)（最优O(n)）*   - 空间复杂度：O(1)*   - 稳定排序*/
void InsertSort(int* arr, int n)
{// 外层循环：遍历未排序元素（从第二个元素开始）for (int i = 0; i < n - 1; i++)  // 共需进行n-1次插入操作{// 初始化已排序区末尾指针（指向当前有序序列最后一个元素）int end = i;          // 缓存待插入元素（未排序区首元素）int temp = arr[end + 1];  // 反向扫描定位插入位置（从后向前比较）while (end >= 0)  // 防止越界访问{// 发现前驱元素更大时需要后移if (arr[end] > temp)  {arr[end + 1] = arr[end];  // 元素后移操作end--;                    // 指针前移继续比较}else{// 找到首个不大于temp的元素，停止扫描break;  }}// 插入目标元素（处理两种情况）：// 1. 找到合适位置：插入到首个小等于temp的元素后// 2. 所有元素都比temp大：插入到数组头部（end=-1时，end+1=0）arr[end + 1] = temp;  }
}

2.2希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插入排序，当gap=1时，就相当于直接插入排序。
它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，在进行直接插入排序会大大减少循环次数，使得效率提升。

动图：
在这里插入图片描述
代码实现：

/** 希尔排序（Shell Sort）* 参数：*   arr - 待排序数组首地址*   n   - 数组元素个数* 特性：*   - 时间复杂度：O(n^(3/2)) 取决于gap序列*   - 空间复杂度：O(1)*   - 不稳定排序* 算法思想：*   通过动态缩小的间隔分组进行插入排序，逐步逼近有序*/
void ShellSort(int* arr, int n)
{// 初始化间隔值（Knuth增量序列）int gap = n;  // 动态缩小间隔直至1（最终执行标准插入排序）while (gap > 1)  {// 计算新间隔（+1确保gap最终能收缩到1）gap = gap / 3 + 1;  // 经典Knuth序列公式// 遍历所有分组（共gap个分组交替处理）for (int i = 0; i < n - gap; i++)  // 注意循环终止条件优化{// 当前元素在分组内的位置指针int end = i;          // 缓存分组内下一个待插入元素int temp = arr[end + gap];  // 分组内插入排序（反向扫描）while (end >= 0)  // 防止越界{// 发现前驱元素更大时进行跨间隔后移if (arr[end] > temp)  {// 元素按间隔步长后移arr[end + gap] = arr[end];  // 移动到前一个分组元素位置end -= gap;  }else{// 找到首个不大于temp的元素，结束扫描break;  }}// 插入元素到正确位置（两种情况处理）：// 1. 找到合适位置：插入到分组内首个小等于temp的元素后// 2. 越界情况：插入到当前分组头部（当end < 0时）arr[end + gap] = temp;  }}
}

3.选择排序

选择排序的基本思想：
每⼀次从待排序的数据元素中选出最小（或最大）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

3.1直接选择排序

在元素集合 array[i]–array[n-1] 中选择关键码最⼤(⼩)的数据元素
若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换
在剩余的 array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到数组剩余 1 个元素

动图：
在这里插入图片描述
实现代码（直接选择排序优化版）：

void Swap(int* x, int* y)
{int temp = *x;*x = *y;*y = temp;
}/** 双极值选择排序优化版* 参数：*   arr - 待排序数组首地址*   n   - 数组元素个数* 特性：*   - 时间复杂度：O(n²)（比较次数比基础版减少约50%）*   - 空间复杂度：O(1)（原地排序）*   - 不稳定排序（极值交换可能改变相等元素顺序）* 优化策略：*   1. 每轮同时确定最小值和最大值*   2. 区间双向收缩减少迭代轮次* 注意：*   修正了经典实现中的极值位置冲突问题*/
void SelectSort(int* arr, int n)
{// 初始化排序区间边界（未排序区间为 [begin, end]）int begin = 0;      // 左边界指针（有序区左边界）int end = n - 1;    // 右边界指针（有序区右边界）// 主循环：当未排序区间长度 > 1时继续处理while (begin < end) {// 初始化极值索引（指向区间起始位置）int mini = begin;  // 当前区间最小值索引int maxi = begin;  // 当前区间最大值索引/* 极值定位阶段：遍历未排序区间[begin, end]* 时间复杂度：O(end-begin+1) → 每轮减少2个元素*/for (int i = begin; i <= end; i++) {// 更新最大值索引（严格大于时更新）if (arr[i] > arr[maxi]) {maxi = i;}// 更新最小值索引（严格小于时更新）if (arr[i] < arr[mini]) {mini = i;}}/* === 关键操作顺序 === */// 步骤1：先将最小值交换到起始位置Swap(&arr[mini], &arr[begin]); /* 冲突修正逻辑（核心处理）* 场景：当最大值位于begin位置时* 问题：步骤1的交换已将原begin位置元素移到mini处* 处理：将maxi重定位到mini所在位置*/if (begin == maxi) {maxi = mini;  // 修正最大值索引}// 步骤2：将最大值交换到末尾位置Swap(&arr[maxi], &arr[end]); /* 区间收缩操作* 效果：未排序区间两端各减少一个元素*/begin++;  // 左边界右移（最小值已归位）end--;    // 右边界左移（最大值已归位）}
}

3.2堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
堆排序在上一篇博客深入理解二叉树中的实现顺序结构二叉树章节已经讲解，这里不再赘述。

4.交换排序

交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

4.1冒泡排序

冒泡排序大家应该都不陌生，它是大部分人所学到的第一个排序算法，它比较简单易懂，但效率低下，适合教学使用。
动图：
在这里插入图片描述
实现代码：

/** 冒泡排序算法（优化版）* 参数：*   arr - 待排序数组首地址*   n   - 数组元素个数* 特性：*   - 时间复杂度：O(n²)（最坏/平均），O(n)（最好-已有序）*   - 空间复杂度：O(1)（原地排序）*   - 稳定排序* 优化点：*   添加提前终止标志，避免无效比较*/
void BubbleSort(int* arr, int n)
{// 外层循环控制排序轮次（最多n-1轮）for (int i = 0; i < n-1; i++){// 有序标志位（1表示已有序，0表示发生交换）int flag = 1;  // 每轮初始设为有序状态/* 内层循环处理未排序区间* 遍历范围：[0, n-i-2]（第i轮时末尾i个元素已有序）* 物理意义：将最大值"冒泡"到未排序区末尾*/for (int j = 0; j < n - i - 1; j++){// 相邻元素比较（保证稳定性，使用>而非>=）if (arr[j] > arr[j + 1]) {// 标记需要继续排序flag = 0;  // 执行元素交换，简单的交换函数Swap(&arr[j], &arr[j + 1]);  }}/* 提前终止条件检测* 若整轮无交换，说明数组已完全有序* 时间复杂度从O(n²)优化至O(n)*/if (flag == 1)break;  }
}

4.2快速排序

作为20世纪十大经典算法之一，快速排序以其优雅的分治策略和接近线性的时间复杂度，成为工业级排序的首选方案。本文将深入解析其核心思想，并通过五大经典变体揭示其强大的泛用能力。

快速排序是Hoare于1962年提出的⼀种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右⼦序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

该算法的基准值非常重要，很多时候会直接影响算法的速率，比如一个数组为1，2，3，4，5，6，7，8，9，10，如果我们取1为基准值，一次递归之后将只有右子树，效率将大大减少，为此，在这里介绍一个取第一个基准值的方法----三数取中方法，顾名思义，三数取中就是将数组开头，结尾及其中间数进行比较，取三个数的中位数，我们这里来实现一下：

int MedianOfThree(int* arr, int left, int right) {int mid = left + (right - left) / 2;if (arr[left] > arr[mid]) {if (arr[mid] > arr[right]) return mid;else if (arr[left] > arr[right]) return right;else return left;}else {if (arr[left] > arr[right])return left;else if (arr[mid] > arr[right])return right;elsereturn mid;}
}

快速排序主函数：

void QuickSort(int* arr, int left, int right)
{if (left >= right)//等于表示子树只有一个元素，不再需要排序，直接退出即可{return;}int mid = _QuickSort(arr, left, right);//_QuickSort函数是寻找第二次及其之后基准值的函数QuickSort(arr, left, mid - 1);QuickSort(arr, mid + 1, right);
}

实现_QuickSort函数的不同方法：

4.2.1 Hoare版本

算法思路：
1）创建左右指针，确定基准值
2）从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环

int _QuickSort(int* arr, int left, int right)
{int medianIndex = MedianOfThree(arr, left, right);Swap(&arr[left], &arr[medianIndex]);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--]);}}//最后交换right与keyi位置的值，是因为循环之后实现了right前的数包括right所代表的值都要小于keyi所代表的值Swap(&arr[right], &arr[keyi]);return right;
}

在这里我们为什么要在left<right时把等号也加上呢？
这是为了防备一些特殊情况，假使数组为6，6，6，8，6，6，看图：
在这里插入图片描述
如果left==right相等时不进入循环，那么8将会与6交换位置，数组将变成8，6，6，6，6，6，基准值将会变成第三个数字6，这与我们快速排序的思想不合，快排要求基准值前都是小于或等于基准值的数，这里8要大于6，所以我们这里加上等于是为了防止此类情况。（虽然会增加一轮次数）。

4.2.2挖坑法

思路：
创建左右指针。⾸先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）

动图：
在这里插入图片描述

int _QuickSort(int* arr, int left, int right)
{int medianIndex = MedianOfThree(arr, left, right);Swap(&arr[left], &arr[medianIndex]);int key = arr[left];int hole = left;while (left < right){while (left<right && arr[right]>key){right--;}arr[hole] = arr[right];hole = right;while (left<right && arr[left]<key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}

有人可能会疑惑，为什么挖坑法的循环的判定条件没有left==right?

我们要知道：

挖坑法（Hole Partitioning）
挖坑法的核心思想是：

始终维护一个“坑”（hole），用来存放待填充的元素。

left 和 right 指针向中间移动，找到合适的元素填入“坑”中。

最终 left 和 right 相遇时，基准值填入最后一个“坑”。

为什么用 left < right？
挖坑法的循环条件是 while (left < right)，因为：
当 left == right 时，说明已经找到了基准的最终位置（即 hole），此时不需要再进入循环。
如果使用 left <= right，可能会导致 left 和 right 越界（比如 right-- 后可能小于 left），影响正确性。

Hoare 分区法的核心思想是：

left 和 right 分别从两端向中间扫描，交换不符合条件的元素。

最终 left 和 right 交叉时，right 指向的位置就是基准的最终位置。

为什么用 left <= right？

Hoare 分区的循环条件是 while (left <= right)，因为：

必须让 left 和 right 交叉（即 left > right），才能确定基准的最终位置。

如果使用 left < right，可能会提前终止循环，导致分区不完整。

一切都是为了准确找到基准值。

4.2.3 lomuto前后指针

前后指针法的思路比较简单：创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

定义两个变量prev和cur
cur指向位置的数据和key指向位置数据比较
若arr[cur] < arr[key],prev想后走一步并和cur交换
若arr[cur] >= arr[key],cur往后走

动图：
在这里插入图片描述
实现代码：

int _QuickSort(int* arr, int left, int right)
{int medianIndex = MedianOfThree(arr, left, right);Swap(&arr[left], &arr[medianIndex]);int prev = left;int cur = left + 1;int key = left;while (cur <= right){if (arr[cur] < arr[key] && (++prev) != cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[key], &arr[prev]);return prev;
}

4.2.4 非递归实现

非递归版本求基准值需要借助栈这个数据结构。
下面关于栈函数的代码见栈与队列这篇博客。

void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//取栈顶元素---取两次int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//[begin,end]---找基准值int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);keyi = prev;//根据基准值划分左右区间//左区间：[begin,keyi-1]//右区间：[keyi+1,end]if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (keyi - 1 > begin){StackPush(&st, keyi - 1);StackPush(&st, begin);}}STDestroy(&st);
}

4.2.5优化版本----三路划分

三路划分快速排序是快速排序的优化版本，特别适合处理包含大量重复元素的数组。它通过将数组划分为 < key、= key、> key 三个部分，减少不必要的递归调用。

算法思路：
key 默认取 left 位置的值。
left 指向区间最左边，right 指向区间最后边，cur 指向 left+1 位置。
cur 遇到比 key 小的值后跟 left 位置交换，换到左边，left++，cur++。
cur 遇到比 key 大的值后跟 right 位置交换，换到右边，right–。
cur 遇到跟 key 相等的值后，cur++。
直到 cur > right 结束

void _QuickSort(int* arr, int left, int right, int* lt, int* gt) {if (left >= right) return;// 三数取中法选择基准值并交换到left位置int medianIndex = MedianOfThree(arr, left, right);Swap(&arr[left], &arr[medianIndex]);int key = arr[left];int cur = left + 1;*lt = left;    // 小于区的右边界（初始为left-1更合理，但这样实现需要调整）*gt = right;   // 大于区的左边界while (cur <= *gt) {if (arr[cur] < key) {// 当前元素小于基准值，交换到小于区Swap(&arr[cur], &arr[*lt + 1]);(*lt)++;cur++;} else if (arr[cur] > key) {// 当前元素大于基准值，交换到大于区Swap(&arr[cur], &arr[*gt]);(*gt)--;// 注意这里cur不递增，因为从右边换过来的元素还没处理} else {// 当前元素等于基准值，继续扫描cur++;}}// 将基准值放到正确位置（等于区的第一个位置）Swap(&arr[left], &arr[*lt]);// 此时：// arr[left..*lt-1] < key// arr[*lt..*gt] == key// arr[*gt+1..right] > key
}// 快速排序主函数
void QuickSort(int* arr, int left, int right) {if (left >= right) return;int lt, gt;_QuickSort(arr, left, right, &lt, &gt);// 递归处理小于区和大于区，跳过等于区QuickSort(arr, left, lt - 1);QuickSort(arr, gt + 1, right);
}

5.归并排序

归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为二路归并。归并排序核心步骤：
在这里插入图片描述

/*** 归并排序的递归辅助函数 - 对指定区间进行排序并合并* 时间复杂度：O(n log n) - 每次递归将问题规模减半，需要 log n 层递归，每层合并操作时间为 O(n)* 空间复杂度：O(n) - 主要用于临时数组存储合并结果* 稳定性：稳定 - 相等元素的相对顺序在合并过程中得以保留*/
void _MergeSort(int* arr, int left, int right, int* tmp)
{// 递归终止条件：当区间长度小于等于1时，已经有序if (left >= right){return;}// 计算中间点，将数组分为左右两部分int mid = (left + right) / 2;// 左半部分区间：[left, mid]// 右半部分区间：[mid+1, right]// 递归排序左右两部分（分治策略）_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);// 合并两个已排序的子数组（关键操作）int begin1 = left, end1 = mid;      // 左半部分区间指针int begin2 = mid + 1, end2 = right; // 右半部分区间指针int index = begin1;                 // 临时数组的当前填充位置// 比较两个子数组的元素，按升序放入临时数组// 稳定性保证：当元素相等时，优先取左半部分的元素while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}// 将剩余元素复制到临时数组（只会执行其中一个循环）while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}// 将临时数组中的有序元素复制回原数组// 注意：这里的循环条件应该是 i <= right，原代码存在错误for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}/*** 归并排序主函数 - 对整个数组进行排序* 时间复杂度：O(n log n) - 递归调用的时间复杂度分析同上* 空间复杂度：O(n) - 主要用于临时数组，递归栈深度为 O(log n)，相对较小可忽略* 稳定性：稳定 - 继承自合并操作的稳定性*/
void MergeSort(int* arr, int n)
{// 分配临时数组空间int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {// 内存分配失败处理return;}// 调用递归辅助函数进行排序_MergeSort(arr, 0, n - 1, tmp);// 释放临时数组free(tmp);
}

6.计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列中
示例图：
在这里插入图片描述

/*** 计数排序 - 非比较型排序算法，适用于整数范围较小的场景* 时间复杂度：O(n + k) - n是元素数量，k是数据范围(max-min+1)* 空间复杂度：O(k) - 需要额外的计数数组存储频率* 稳定性：不稳定 - 当前实现无法保证相等元素的相对顺序*/
void CountSort(int* arr, int n)
{// 1. 确定数据范围（最大值和最小值）int max = arr[0], min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}// 2. 创建计数数组，大小为数据范围int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(1);}// 初始化计数数组为0memset(count, 0, range * sizeof(int));// 3. 统计每个元素出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}// 4. 回写排序结果（不稳定版本）int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}free(count);
}

如果想要该排序变得稳定性稳定，可以这样修改：

// 稳定版本的计数排序（增加累加频率和反向填充）
void StableCountSort(int* arr, int n)
{// 确定数据范围int max = arr[0], min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL) exit(1);// 统计频率for (int i = 0; i < n; i++)count[arr[i] - min]++;// 计算累加频率（确定每个元素的最终位置）for (int i = 1; i < range; i++)count[i] += count[i-1];// 创建临时数组存储排序结果int* temp = (int*)malloc(n * sizeof(int));if (temp == NULL) exit(1);// 反向填充（保证稳定性）for (int i = n-1; i >= 0; i--){int pos = arr[i] - min;temp[--count[pos]] = arr[i];}// 复制回原数组memcpy(arr, temp, n * sizeof(int));free(count);free(temp);
}