五大经典排序算法详解：插入、希尔、冒泡、选择与堆排序

然后，逐步缩小增量（通常取上一次的一半），重复上述分组和插入排序的操作。当增量缩小到 1 时，整个数组就变成了一个子序列，此时再进行一次插入排序，数组就完全有序了。

这个过程就像先把乱序的扑克牌按花色分组整理，再按点数细分整理，最后整体微调：

大增量时，元素移动的跨度大，能快速把乱序的数组变得'大致有序'。

小增量时，数组已经基本有序，插入排序的效率会非常高。

2、示例代码

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;
            }
        }
    }
}

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;
    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 轮遍历，总比较次数为等差数列求和 n(n−1)/2，时间复杂度为 O(N^2)；若加入提前终止优化，最优情况可降至 O(n)。

**空间复杂度：**冒泡排序仅需常数级别的临时变量用于元素交换，因此空间复杂度为 O(1)。

稳定性：冒泡排序是稳定的排序算法，因为它仅在相邻元素前大于后时才交换，相同值的元素不会改变相对顺序。

上述五大排序性能对比：

希尔排序和堆排序时间复杂度都是 N*logN 这个量级，是这几个中效率最高的两个了。

（注：希尔排序的时间复杂度是一个简化说法，严格来说它介于 O(NlogN) 和 O(N^2) 之间，取决于增量序列的选择，但常归为 O(NlogN) 量级）

接下来就是插入排序和冒泡排序，它们俩在数组有序时，时间复杂度都能达到 O(N)，最坏都是 O(N^2) 这个量级，但是他们在一些场景下的性能还是有差距的：

**有序：**一样

**接近有序：**有一些差距

**部分有序：**差距就很大

这是由于这两个算法的单次操作导致的。

最后一个就是选择排序，无论是否有序时间复杂度都是在 O(N^2) 这个量级，也是这几个中效率最差的排序算法。

稳定性补充：冒泡、插入排序是稳定的；希尔、堆、选择排序是不稳定的。