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

效率分析

• 时间复杂度：取决于增量序列的选择。通常认为介于 O(NlogN) 和 O(N²) 之间，常归为 O(NlogN) 量级。
• 空间复杂度：O(1)。
• 稳定性：不稳定。跳跃式交换可能破坏相同值元素的原始相对顺序。

选择排序

核心思想

选择排序的核心是'挑最小'。每次从未排序部分选出最小（或最大）的元素，与未排序部分的第一个元素交换。重复此过程，直到整个数组有序。

代码实现

这里展示一种双向选择排序的优化版本，每轮同时找出最大值和最小值，分别放到两端。

void SelectSort(int* a, int n) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        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--;
    }
}

效率分析

• 时间复杂度：无论数据是否有序，都需要遍历比较，固定为 O(N²)。
• 空间复杂度：O(1)。
• 稳定性：不稳定。交换操作可能打乱相等元素的顺序。

堆排序

核心思想

堆排序利用二叉堆的特性。首先将数组构建为大顶堆（或小顶堆），堆顶即为当前最大值。将堆顶与末尾元素交换，使最大值归位，然后重新调整剩余元素为堆。重复此过程直至有序。

代码实现

// 向下调整算法
void AdjustDown(int* a, int n, int parent) {
    int child = 2 * parent + 1;
    while (child < 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;
        }
    }
}

// 堆排序
void HeapSort(int* a, int n) {
    // 向下调整建堆 -- O(N)
    for (int i = (n - 2) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    
    // 排序阶段
    int end = n - 1;
    while (end > 0) {
        swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

效率分析

• 时间复杂度：建堆 O(N)，排序阶段 N 次调整每次 O(logN)，总体 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; // 若本轮无交换，说明已有序，提前结束
        }
    }
}

效率分析

• 时间复杂度：常规情况 O(N²)，加入提前终止优化后，最好情况（已有序）可达 O(N)。
• 空间复杂度：O(1)。
• 稳定性：稳定。仅在严格大于时才交换。

性能对比总结

在实际开发中，如果数据量小或部分有序，插入排序往往表现优异；对于大规模数据，堆排序或希尔排序的效率更高。选择排序虽然简单但效率较低，通常不作为首选。冒泡排序因易于理解和优化，常用于教学或特定小规模场景。理解这些算法的底层逻辑，有助于我们在不同场景下做出更合适的选择。