五大经典排序算法：插入、希尔、冒泡、选择、堆排序全攻略
目录
--------------插入排序-------------
--------------希尔排序-------------
--------------选择排序-------------
---------------堆排序--------------
--------------冒泡排序-------------
--------------插入排序-------------
1、插入排序思想
插入排序的核心思想是逐步构建有序序列：
将数组分为 “已排序” 和 “未排序” 两部分，初始时已排序部分只包含第一个元素。
每次从未排序部分取出第一个元素，将其向前插入到已排序序列中的正确位置，使得插入后的序列依然保持有序。
重复这个过程，直到所有元素都被插入到已排序序列中。
这个过程就像整理扑克牌：你会把每一张新摸到的牌，插入到手中已排好序的牌堆里，最终让整副牌都有序。
2、示例代码
// 插入排序（此处为降序，升序将 a[end] < tmp 改为 a[end] > tmp） 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; // 插入到正确位置 } }3、效率分析
时间复杂度：最坏情况下，插入第 1 个待排序元素时最多比较 1 次，第 2 个元素最多比较 2 次…… 第 n-1 个元素最多比较 n-1 次，总比较次数为等差数列求和，因此时间复杂度为O(N^2)；但在数组已有序的情况下，每个元素仅需比较 1 次，时间复杂度可优化至O(N)。
空间复杂度：仅定义了常数级的辅助变量，未额外开辟大规模空间，因此空间复杂度为O(1)。
稳定性：排序是稳定的。因为元素是逐个向前插入的，当遇到相等元素时不会移动，因此相等元素的相对位置在排序前后保持不变。
--------------希尔排序-------------
1、希尔排序思想
希尔排序的核心思想是分组插入排序，逐步缩小增量：
将整个待排序数组按照某个 增量（步长）分割成若干个子序列，每个子序列的元素在原数组中是等间隔的。对每个子序列分别进行插入排序，通过这种分组排序，让数组整体变得 “基本有序”。
然后，逐步缩小增量（通常取上一次的一半），重复上述分组和插入排序的操作。当增量缩小到 1 时，整个数组就变成了一个子序列，此时再进行一次插入排序，数组就完全有序了。
这个过程就像先把乱序的扑克牌按花色分组整理，再按点数细分整理，最后整体微调：
大增量时，元素移动的跨度大，能快速把乱序的数组变得 “大致有序”。
小增量时，数组已经基本有序，插入排序的效率会非常高。
2、示例代码
void ShellSort(int* a, int n) { //gap > 1 预排序 //gap == 1 插入排序 int gap = n; while (gap > 1) { gap = gap / 3 + 1; /*----------------多组并排----------------*/ //for (int i = 0; i < n - gap; i++) //{ // 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; //} /*-------------一组排完排另一组-------------*/ 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; } } } } 3、效率分析
时间复杂度：
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)
稳定性：由于是跳跃调整，相同值的元素可能在分组插入排序的过程中，被交换到彼此的原始相对位置之前，破坏了稳定性，所以希尔排序是不稳定排序。
--------------选择排序-------------
1、选择排序思想
选择排序的核心思想是逐步选择最值，构建有序序列：
将数组分为 “已排序” 和 “未排序” 两部分，初始时已排序部分为空。每次从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，该元素就加入到已排序部分的末尾。
重复这个过程，直到所有元素都被纳入已排序部分，整个数组就完全有序了。
这个过程就像从一堆打乱的扑克牌里，每次挑出最小的一张，放到已整理好的牌堆后面，最终完成整副牌的排序。
2、示例代码
void SelectSort(int* a, int n) { /* int left = 0; while (left < n) { int min = left; for (int i = left + 1; i < n; i++) { if (a[min] > a[i]) { min = i; } } swap(&a[min],&a[left]); left++; } */ 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--; } } 修正：
3、效率分析
时间复杂度：第一趟遍历 n-1 遍数组，第二趟遍历 n-2 遍数组，第 n-1 遍遍历1遍数组，是个等差数列，所以时间复杂度为O(N^2)
空间复杂度：仅使用常量级别的变量，因此空间复杂度是O(1)
稳定性：由于交换操作可能会破坏相同值元素的相对顺序，所以选择排序是不稳定排序
---------------堆排序--------------
1、堆排序思想
堆排序的核心思想是利用堆的特性进行排序：
将待排序数组构建成一个大顶堆（或小顶堆），堆顶即为当前未排序部分的最大值（或最小值）。每次将堆顶元素与当前未排序部分的末尾元素交换，使该最大值（或最小值）归位到正确的排序位置。交换后，堆的结构会被破坏，需要对剩余的未排序元素重新调整为大顶堆（或小顶堆）。重复这个过程，直到整个数组有序。
这个过程就像从一堆石头里每次挑出最重的一块，放到已排好的序列末尾，最终让所有石头按重量从大到小排好。
2、示例代码
//向上调整算法 - 建大堆 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--; } } 3、效率分析
时间复杂度：
向下调整建堆的时间复杂度为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)
稳定性：堆排序是不稳定的排序算法。因为在堆的调整过程中（无论是向上还是向下调整），相同值的节点可能会因为交换而改变相对顺序，破坏了原有的稳定性。
--------------冒泡排序-------------
1、冒泡排序思想
冒泡排序的核心思想是通过相邻元素的比较与交换，让较大（较小）的元素逐步 “冒泡” 到数组的末尾。
将数组视为一个未排序的整体，从头部开始，依次比较相邻的两个元素。
如果前一个元素大于（小于）后一个元素，就交换它们的位置，使较大（较小）的元素向后移动一位。
每一轮遍历后，当前未排序部分的最大值（最小值）会被 “推” 到末尾，成为已排序部分。
重复这个过程，直到所有元素都完成排序。
这个过程就像水里的气泡一样，较大（较小）的元素会慢慢浮到水面（数组末尾）。
2、示例代码
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; } } }3、效率分析
时间复杂度：冒泡排序共进行 n−1 轮遍历，总比较次数为等差数列求和 2n(n−1)，时间复杂度为 O(N^2)；若加入提前终止优化，最优情况可降至 O(n)。
空间复杂度：冒泡排序仅需常数级别的临时变量用于元素交换，因此空间复杂度为 O(1)。
稳定性：冒泡排序是稳定的排序算法，因为它仅在相邻元素前大于后时才交换，相同值的元素不会改变相对顺序。
上述五大排序性能对比：
希尔排序和堆排序时间复杂度都是N*logN这个量级，是这几个中效率最高的两个了
（（希尔排序的时间复杂度）这是一个简化说法，严格来说它介于 O(NlogN) 和 O(N2) 之间，取决于增量序列的选择，但常归为 O(NlogN) 量级）
接下来就是插入排序和冒泡排序，它俩在数组有序时，时间复杂度都能达到 O (N)，最坏都是 O(N^2) 这个量级，但是他们在一些场景下的性能还是有差距的：
有序：一样
接近有序：有一些差距
部分有序：差距就很大
这是由于这两个算法的单次操作导致的：
最后一个就是选择排序，无论是否有序时间复杂度都是在O(N^2)这个量级，也是这几个中效率最差的排序算法
稳定性补充：冒泡、插入排序是稳定的；希尔、堆、选择排序是不稳定的。
