C算法
五大经典排序算法详解：插入、希尔、冒泡、选择与堆排序
本文详细介绍了插入、希尔、冒泡、选择和堆排序五种经典算法。涵盖各算法的核心思想、示例代码（C 语言）、时间复杂度、空间复杂度及稳定性分析。插入和冒泡适合小规模或近有序数据；希尔通过分组优化插入效率；选择排序简单但不稳定；堆排序利用堆结构实现 O(NlogN) 高效排序。最后对比了五者的性能差异，指出堆和希尔在大数据量下更优，而插入和冒泡在特定场景下表现良好。
本文详细介绍了插入、希尔、冒泡、选择和堆排序五种经典算法。涵盖各算法的核心思想、示例代码（C 语言）、时间复杂度、空间复杂度及稳定性分析。插入和冒泡适合小规模或近有序数据；希尔通过分组优化插入效率；选择排序简单但不稳定；堆排序利用堆结构实现 O(NlogN) 高效排序。最后对比了五者的性能差异，指出堆和希尔在大数据量下更优，而插入和冒泡在特定场景下表现良好。
插入排序的核心思想是逐步构建有序序列：
将数组分为'已排序'和'未排序'两部分，初始时已排序部分只包含第一个元素。
每次从未排序部分取出第一个元素，将其向前插入到已排序序列中的正确位置，使得插入后的序列依然保持有序。
重复这个过程，直到所有元素都被插入到已排序序列中。
这个过程就像整理扑克牌：你会把每一张新摸到的牌，插入到手中已排好序的牌堆里，最终让整副牌都有序。
void InsertSort(int* a, int n) {
// 遍历未排序元素（从第 2 个元素开始）
for (int i = 1; i < n; i++) {
int end = i - 1;
// 已排序部分末尾下标
int tmp = a[i];
// 保存当前待插入元素
// 向前查找合适位置，大于 tmp（降序）则后移
while (end >= 0) {
if (a[end] < tmp) {
a[end + 1] = a[end];
// 元素后移腾位置
end--;
} else {
break;
// 找到位置，退出循环
}
}
a[end + 1] = tmp;
// 插入到正确位置
}
}
时间复杂度：最坏情况下，插入第 1 个待排序元素时最多比较 1 次，第 2 个元素最多比较 2 次…… 第 n-1 个元素最多比较 n-1 次，总比较次数为等差数列求和，因此时间复杂度为O(N^2)；但在数组已有序的情况下，每个元素仅需比较 1 次，时间复杂度可优化至O(N)。
空间复杂度：仅定义了常数级的辅助变量，未额外开辟大规模空间，因此空间复杂度为O(1)。
稳定性：排序是稳定的。因为元素是逐个向前插入的，当遇到相等元素时不会移动，因此相等元素的相对位置在排序前后保持不变。
希尔排序的核心思想是分组插入排序，逐步缩小增量：
将整个待排序数组按照某个 增量（步长）分割成若干个子序列，每个子序列的元素在原数组中是等间隔的。对每个子序列分别进行插入排序，通过这种分组排序，让数组整体变得'基本有序'。
然后，逐步缩小增量（通常取上一次的一半），重复上述分组和插入排序的操作。当增量缩小到 1 时，整个数组就变成了一个子序列，此时再进行一次插入排序，数组就完全有序了。
这个过程就像先把乱序的扑克牌按花色分组整理，再按点数细分整理，最后整体微调：
大增量时，元素移动的跨度大，能快速把乱序的数组变得'大致有序'。
小增量时，数组已经基本有序，插入排序的效率会非常高。
void ShellSort(int* a, int n) {
// gap > 1 预排序
// gap == 1 插入排序
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;
/*----------------多组并排----------------*/
/*-------------一组排完排另一组-------------*/
for (int j = 0; j < gap; j++) {
for (int i = 0; i < n - gap; i += gap) {
int end = i;
int tmp = a[i + gap];
while (end >= 0) {
if (tmp > a[end]) {
a[end + gap] = a[end];
end -= gap;
} else {
break;
}
}
a[end + gap] = tmp;
}
}
}
}
时间复杂度：
1、外层：外层循环控制增量gap（公式不同如gap/2、gap/3+1会影响效率）从n逐步缩小至 1，迭代次数为对数级别，时间复杂度为 O(logN)
2、内层：刚开始gap很大，for 循环大致在 N 这个量级（具体看图），while 循环插入判断跳的很快，是常量级别的，所以最开始是时间复杂度为O(N)，最后gap 很小，按理来说应该是 N^2，但是由于数组已经无限接近有序，所以按最好的情况算O(N)
因此我们可以大概计算出来应该在 N*logN 这个量级
这是关于希尔排序时间复杂度不同教材的分析：
空间复杂度：仅定义了常量级的辅助变量，所以为O(1)
稳定性：由于是跳跃调整，相同值的元素可能在分组插入排序的过程中，被交换到彼此的原始相对位置之前，破坏了稳定性，所以希尔排序是不稳定排序。
选择排序的核心思想是逐步选择最值，构建有序序列：
将数组分为'已排序'和'未排序'两部分，初始时已排序部分为空。每次从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，该元素就加入到已排序部分的末尾。
重复这个过程，直到所有元素都被纳入已排序部分，整个数组就完全有序了。
这个过程就像从一堆打乱的扑克牌里，每次挑出最小的一张，放到已整理好的牌堆后面，最终完成整副牌的排序。
void SelectSort(int* a, int n) {
int left = 0;
int right = n - 1;
// left == right 就表示只有一个元素了，所以没有选择的必要了
while (left < right) {
// 必须要初始为 left，因为是内层循环从 left+1 开始比较的
// 如果有一个初始不为 left，就会跳过 left 这个值
int max = left;
int min = left;
for (int i = left + 1; i <= right; i++) {
if (a[max] < a[i]) {
max = i;
}
if (a[min] > a[i]) {
min = i;
}
}
swap(&a[left], &a[min]);
// 修正:max 有可能和 left 重叠
if (left == max) {
max = min;
}
swap(&a[right], &a[max]);
left++;
right--;
}
}
修正：
时间复杂度：第一趟遍历 n-1 遍数组，第二趟遍历 n-2 遍数组，第 n-1 遍遍历 1 遍数组，是个等差数列，所以时间复杂度为O(N^2)
空间复杂度：仅使用常量级别的变量，因此空间复杂度是O(1)
稳定性：由于交换操作可能会破坏相同值元素的相对顺序，所以选择排序是不稳定排序
堆排序的核心思想是利用堆的特性进行排序：
将待排序数组构建成一个大顶堆（或小顶堆），堆顶即为当前未排序部分的最大值（或最小值）。每次将堆顶元素与当前未排序部分的末尾元素交换，使该最大值（或最小值）归位到正确的排序位置。交换后，堆的结构会被破坏，需要对剩余的未排序元素重新调整为大顶堆（或小顶堆）。重复这个过程，直到整个数组有序。
这个过程就像从一堆石头里每次挑出最重的一块，放到已排好的序列末尾，最终让所有石头按重量从大到小排好。
// 向上调整算法 - 建大堆
void AdjustUp(int* a, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (a[child] > a[parent]) {
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
// 向下调整算法
void AdjustDown(int* a, int n, int parent) {
int child = 2 * parent + 1;
while (child < n)// 等于 n 时越界一个位置
{
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
if (a[child] > a[parent]) {
swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
// 堆排序
// N*logN
void HeapSort(int* a, int n) {
// 向下调整建堆 -- N
for (int i = (n - 2) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
// 向上调整建堆 -- N*logN
// for (int i = 1; i < n; i++)
// {
// AdjustUp(a, i);
// }
// 排序
int end = n - 1;
while (end > 0) {
swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
时间复杂度：
向下调整建堆的时间复杂度为**O(N)：**向下调整建堆的时间复杂度是 O(N)，而不是 O(NlogN)，核心原因是调整成本被平摊了。堆的底层节点数量最多，占了总节点数的一半左右，但它们的调整深度最小；而堆的上层节点数量很少，调整深度才会达到 O(logN)。这种'数量多的节点成本低，数量少的节点成本高'的反向分布，把整体的平均调整成本从 O(logN) 拉低到了 O(1)，最终时间复杂度就成了 O(N)。
向上调整建堆的时间复杂度为O(NlogN)，它的调整逻辑与向下调整正好相反：上层节点的调整深度较浅，但下层节点的调整深度很深，而堆的下层恰恰包含了大部分元素。因此，整体来看，大部分节点都需要进行约 logN 次调整，最终时间复杂度为 O(NlogN)。
堆排序的完整过程分为建堆和排序阶段两部分：
建堆阶段：使用向下调整建堆，时间复杂度为 O(N)
排序阶段：共需进行 N−1 次堆顶交换与向下调整，每次调整的时间复杂度为 O(logN)，因此这一阶段的时间复杂度为 O(NlogN)
将两部分时间复杂度相加，取主导项，堆排序的整体时间复杂度为 O(NlogN)，且该复杂度不受输入数据分布的影响，最优、最坏与平均时间复杂度均为 O(NlogN)。
空间复杂度：仅仅使用了常数级别的变量，所以空间复杂度为O(1)
**稳定性：**堆排序是不稳定的排序算法。因为在堆的调整过程中（无论是向上还是向下调整），相同值的节点可能会因为交换而改变相对顺序，破坏了原有的稳定性。
冒泡排序的核心思想是通过相邻元素的比较与交换，让较大（较小）的元素逐步'冒泡'到数组的末尾。
将数组视为一个未排序的整体，从头部开始，依次比较相邻的两个元素。
如果前一个元素大于（小于）后一个元素，就交换它们的位置，使较大（较小）的元素向后移动一位。
每一轮遍历后，当前未排序部分的最大值（最小值）会被'推'到末尾，成为已排序部分。
重复这个过程，直到所有元素都完成排序。
这个过程就像水里的气泡一样，较大（较小）的元素会慢慢浮到水面（数组末尾）。
void BubbleSort(int* a, int n) {
// 多少趟
for (int i = 0; i < n - 1; i++) {
// 单趟
int flag = 0;
for (int j = 1; j < n - i; j++) {
if (a[j - 1] > a[j]) {
swap(&a[j - 1], &a[j]);
flag = 1;
}
}
if (flag == 0) {
break;
}
}
}
**时间复杂度：**冒泡排序共进行 n−1 轮遍历，总比较次数为等差数列求和 2n(n−1)，时间复杂度为 O(N^2)；若加入提前终止优化，最优情况可降至 O(n)。
**空间复杂度：**冒泡排序仅需常数级别的临时变量用于元素交换，因此空间复杂度为 O(1)。
稳定性：冒泡排序是稳定的排序算法，因为它仅在相邻元素前大于后时才交换，相同值的元素不会改变相对顺序。
希尔排序和堆排序时间复杂度都是 N*logN 这个量级，是这几个中效率最高的两个了
（（希尔排序的时间复杂度）这是一个简化说法，严格来说它介于 O(NlogN) 和 O(N^2) 之间，取决于增量序列的选择，但常归为 O(NlogN) 量级）
接下来就是插入排序和**冒泡排序，**它俩在数组有序时，时间复杂度都能达到 O (N)，最坏都是 O(N^2) 这个量级，但是他们在一些场景下的性能还是有差距的：
**有序：**一样
**接近有序：**有一些差距
**部分有序：**差距就很大
这是由于这两个算法的单次操作导致的：
最后一个就是**选择排序，**无论是否有序时间复杂度都是在 O(N^2) 这个量级，也是这几个中效率最差的排序算法
稳定性补充：冒泡、插入排序是稳定的；希尔、堆、选择排序是不稳定的。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online