排序算法是计算机科学中最基础也最重要的算法之一，它的应用无处不在：从考试成绩排名到电商商品筛选，从数据库查询优化到操作系统任务调度。掌握经典排序算法不仅是编程入门的必经之路，更是理解算法设计思想（如分治、贪心、动态规划）的关键。
本文将详细讲解十种最常用的排序算法，包括它们的核心思想、实现步骤、代码实现、时间/空间复杂度分析以及适用场景。无论您是编程初学者还是准备算法竞赛的选手，都能从本文中获得有价值的内容。
核心思想：通过相邻元素的比较和交换，将较大的元素逐步"冒泡"到数组的末尾，就像水中的气泡向上浮起一样。每一轮冒泡都会确定一个最大元素的最终位置。
算法步骤：
代码实现：
/*======= 冒泡排序 =======*/
void bubbleSort(int *arr, int n)
{
for (int i = 0; i < n-1; i++) // i表示已确定位置的元素个数
{
bool swapped = false; // 优化：标记本轮是否发生交换
for (int j = 0; j < n-i-1; j++) // 未排序部分的长度为n-i
{
if (arr[j] > arr[j+1]) // 前一个元素更大，需要交换
{
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
swapped = true;
}
}
if (!swapped) break; // 本轮没有交换，数组已经有序，提前退出
}
}
优缺点分析：
适用场景：小规模数据集、要求排序稳定、教学演示场景
核心思想：将数组分为已排序和未排序两部分，每次从未排序部分中选择最小的元素，放到已排序部分的末尾。与冒泡排序不同，选择排序每轮只进行一次交换。
算法步骤：
代码实现：
/*======= 选择排序 =======*/
void selectSort(int *arr, int n)
{
for (int i = 0; i < n-1; i++) // i表示已排序部分的末尾索引
{
int minIndex = i; // 假设当前元素是最小值
for (int j = i+1; j < n; j++) // 在未排序部分找最小值
{
if (arr[j] < arr[minIndex])
{
minIndex = j; // 更新最小值索引
}
}
// 将最小值交换到已排序部分的末尾
if (minIndex != i)
{
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
优缺点分析：
适用场景：小规模数据集、内存受限、不需要稳定性的场景
核心思想：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。类似于我们整理扑克牌的过程。
算法步骤：
代码实现：
/*======= 插入排序 =======*/
void insertSort(int *arr, int n)
{
for (int i = 1; i < n; i++) // 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; // 插入到正确位置
}
}
优缺点分析：
适用场景：
核心思想：插入排序的改进版，也称为"缩小增量排序"。通过设置不同的步长（gap）将数组分为多个子序列，分别进行插入排序。随着步长逐渐减小，数组变得越来越有序，最后当步长为1时，对整个数组进行一次插入排序。
算法步骤：
代码实现：
/*======= 希尔排序 =======*/
void shellSort(int *arr, int n)
{
// 初始步长为数组长度的一半，每次减半
for (int gap = n/2; gap > 0; gap /= 2)
{
// 对每个子序列进行插入排序
for (int i = gap; i < n; i++)
{
int tmp = arr[i];
int j;
for (j = i; j >= gap && arr[j-gap] > tmp; j -= gap)
{
arr[j] = arr[j-gap];
}
arr[j] = tmp;
}
}
}
优缺点分析：
适用场景：中等规模数据集、内存受限环境、对稳定性无要求
核心思想：采用分治策略，选择一个基准元素（pivot），将数组分为两部分：左边部分小于等于基准，右边部分大于等于基准。然后递归地对左右两部分进行排序。
算法步骤：
代码实现：
/*======= 快速排序 =======*/
void quickSort(int *arr, int start, int end)
{
if (start >= end) return; // 递归终止条件
int left = start, right = end;
int pivot = arr[left]; // 选择第一个元素作为基准
while (left < right)
{
// 从右往左找第一个小于基准的元素
while (arr[right] > pivot && left < right) right--;
if (left < right) arr[left++] = arr[right];
// 从左往右找第一个大于基准的元素
while (arr[left] < pivot && left < right) left++;
if (left < right) arr[right--] = arr[left];
}
arr[left] = pivot; // 将基准放到正确位置
// 递归排序左右两部分
quickSort(arr, start, left-1);
quickSort(arr, left+1, end);
}
// 对外提供的统一接口
void quickSort(int *arr, int size)
{
quickSort(arr, 0, size-1);
}
优缺点分析：
适用场景：
核心思想：同样采用分治策略，将数组不断地分成两半，直到每个子数组只有一个元素（天然有序）。然后将两个有序的子数组合并成一个更大的有序数组，最终得到完全有序的数组。
算法步骤：
图解参考：
代码实现：
/*======= 归并排序 =======*/
/*------- 合并两个有序子数组 -------*/
void merge(int *arr, int left, int mid, int right)
{
int *temp = new int[right-left+1]; // 临时数组存储合并结果
int i = left, j = mid + 1, k = 0;
// 同时遍历两个子数组，将较小的元素放入临时数组
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
// 处理剩余元素
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 将临时数组的内容复制回原数组
for (i = left, k = 0; i <= right; i++, k++)
{
arr[i] = temp[k];
}
delete[] temp; // 释放临时数组
}
/*------- 递归排序函数 -------*/
void mergeSort(int *arr, int start, int end)
{
if (start >= end) return; // 递归终止条件
int mid = (start + end) / 2;
mergeSort(arr, start, mid); // 排序左半部分
mergeSort(arr, mid+1, end); // 排序右半部分
merge(arr, start, mid, end); // 合并两个有序部分
}
// 对外提供的统一接口
void mergeSort(int *arr, int size)
{
mergeSort(arr, 0, size-1);
}
优缺点分析：
适用场景：需要稳定排序、链表排序、外部排序（数据无法完全加载到内存）
核心思想：利用堆这种数据结构进行排序。堆是一棵完全二叉树，满足堆性质：大根堆中每个父节点的值都大于等于其子节点的值，小根堆则相反。我们可以利用大根堆的性质，每次取出堆顶的最大值，放到数组末尾，最终得到升序排列的数组。
基础知识：
算法步骤：
排序过程演示：
代码实现：
#include <algorithm> // 用于swap函数
/*======= 堆排序 =======*/
// 下沉操作：将索引为i的节点下沉到正确位置
void siftDown(int arr[], int size, int i)
{
int value = arr[i]; // 保存当前节点的值
while (i < size / 2) // 只要不是叶子节点就继续
{
int child = 2 * i + 1; // 左子节点索引
// 如果右子节点存在且大于左子节点，选择右子节点
if (child + 1 < size && arr[child+1] > arr[child])
{
child++;
}
// 如果子节点大于当前节点，将子节点上移
if (arr[child] > value)
{
arr[i] = arr[child];
i = child;
}
else
{
break; // 当前节点已经大于等于子节点，停止下沉
}
}
arr[i] = value; // 将当前节点放到正确位置
}
void heapSort(int *arr, int size)
{
// 第一步：建堆，从最后一个非叶子节点开始
for (int i = (size-1)/2; i >= 0; i--)
{
siftDown(arr, size, i);
}
// 第二步：排序
for (int i = size-1; i > 0; i--)
{
swap(arr[0], arr[i]); // 交换堆顶和最后一个元素
siftDown(arr, i, 0); // 对新的堆顶进行下沉调整
}
}
优缺点分析：
适用场景：大规模数据集、内存有限、不需要稳定性、优先队列相关应用
核心思想：将数组元素按照数值范围分配到多个桶中，每个桶内的元素再单独排序，最后将所有桶中的元素按顺序合并，得到有序数组。桶排序是一种非比较排序算法。
算法步骤：
图解参考：
代码实现：
#include <vector>
#include <algorithm>
#include <cmath>
/*======= 桶排序 =======*/
void bucketSort(int *arr, int size)
{
if (size <= 1) return;
// 找出最大值和最小值
int maxNum = arr[0], minNum = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] > maxNum) maxNum = arr[i];
if (arr[i] < minNum) minNum = arr[i];
}
// 计算桶的数量（工业界通用经验：桶的数量为数据量的平方根+1）
int bucketCount = (int)sqrt(size) + 1;
vector<vector<int>> buckets(bucketCount);
// 计算每个桶的数值范围
double range = (double)(maxNum - minNum + 1) / bucketCount;
// 将元素分配到对应的桶中
for (int i = 0; i < size; i++)
{
int bucketIndex = (int)((arr[i] - minNum) / range);
buckets[bucketIndex].push_back(arr[i]);
}
// 对每个桶内的元素进行排序，并合并到原数组
int index = 0;
for (int i = 0; i < bucketCount; i++)
{
// 使用标准库的sort函数对桶内元素排序
sort(buckets[i].begin(), buckets[i].end());
// 将桶内元素复制到原数组
for (int j = 0; j < (int)buckets[i].size(); j++)
{
arr[index++] = buckets[i][j];
}
}
}
优缺点分析：
适用场景：数据分布均匀、数值范围已知、大规模整数/浮点数排序
核心思想：桶排序的特殊情况，当数组元素的数值范围较小时，可以用一个计数数组来统计每个数值出现的次数，然后根据计数数组将元素按顺序放回原数组。计数排序也是一种非比较排序算法。
算法步骤：
代码实现：
/*======= 计数排序 =======*/
void countingSort(int *arr, int size)
{
if (size <= 1) return;
// 找出最大值和最小值
int maxNum = arr[0], minNum = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] > maxNum) maxNum = arr[i];
if (arr[i] < minNum) minNum = arr[i];
}
// 创建计数数组并初始化
int range = maxNum - minNum + 1;
int *count = new int[range](); // 初始化为0
// 统计每个元素出现的次数
for (int i = 0; i < size; i++)
{
count[arr[i] - minNum]++;
}
// 根据计数数组将元素放回原数组
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i] > 0)
{
arr[index++] = i + minNum;
count[i]--;
}
}
delete[] count; // 释放计数数组
}
优缺点分析：
适用场景：数据范围小且集中、整数排序、作为基数排序的子程序
核心思想：按照数字的每一位进行排序，从最低位到最高位依次进行。每一位的排序可以使用计数排序或桶排序。基数排序也是一种非比较排序算法。
算法步骤：
图解参考：
代码实现：
#include <vector>
/*======= 基数排序 =======*/
void radixSort(int *arr, int size)
{
if (size <= 1) return;
// 找出最大值，确定最大位数
int maxNum = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] > maxNum) maxNum = arr[i];
}
// 从最低位开始，依次对每一位排序
for (int exp = 1; maxNum / exp > 0; exp *= 10)
{
vector<vector<int>> buckets(10); // 创建10个桶，对应0-9
// 将元素按当前位分配到对应的桶中
for (int i = 0; i < size; i++)
{
int digit = (arr[i] / exp) % 10;
buckets[digit].push_back(arr[i]);
}
// 将桶中的元素按顺序放回原数组
int index = 0;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < (int)buckets[i].size(); j++)
{
arr[index++] = buckets[i][j];
}
}
}
}
优缺点分析：
适用场景：整数排序、位数固定且较少、大规模数据排序
| 类型 | 时间复杂度-最好 | 时间复杂度-最坏 | 时间复杂度-平均 | 空间复杂度-最好 | 空间复杂度-最坏 | 空间复杂度-平均 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | O(1) | O(1) | 稳定 | 小规模数据集、要求排序稳定、教学演示 |
| 选择 | O(n²) | O(n²) | O(n²) | O(1) | O(1) | O(1) | 不稳定 | 小规模数据集、内存受限、不需要稳定性 |
| 插入 | O(n) | O(n²) | O(n²) | O(1) | O(1) | O(1) | 稳定 | 小规模数据集(n<32)、数据基本有序、高级排序子程序 |
| 希尔 | O(n) | O(n²) | O(n^1.3) | O(1) | O(1) | O(1) | 不稳定 | 中等规模数据集、内存受限、不需要稳定性 |
| 快速 | O(nlogn) | O(n²) | O(nlogn) | O(logn) | O(n) | O(logn) | 不稳定 | 大规模数据集、平均性能要求高、内存充足 |
| 归并 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | O(n) | O(n) | 稳定 | 需要稳定排序、链表排序、外部排序 |
| 堆 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | O(1) | O(1) | 不稳定 | 大规模数据集、内存有限、优先队列应用 |
| 桶 | O(n) | O(n²) | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定* | 数据分布均匀、数值范围已知、大规模数值排序 |
| 计数 | O(n+k) | O(n+k) | O(n+k) | O(k) | O(k) | O(k) | 稳定 | 数据范围小且集中、整数排序、基数排序子程序 |
| 基数 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | O(n+k) | O(n+k) | 稳定 | 整数排序、位数固定且较少、大规模数据排序 |
注：桶排序的稳定性取决于桶内使用的排序算法
符号说明：
作者是大学生，到目前为止只会这十种排序算法，并且有些说明得不是很好，如果您发现文章中有任何错误或不足之处，或者有其他更好的排序算法推荐，欢迎在评论区留言交流。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。