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

时间复杂度取决于增量序列的选择，通常介于 O(NlogN) 和 O(N^2) 之间，常归为 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^2)，无论数据是否有序。空间复杂度 O(1)。由于交换操作可能会破坏相同值元素的相对顺序，属于不稳定排序。

堆排序

堆排序利用堆的特性进行排序。将待排序数组构建为大顶堆（或小顶堆），堆顶即为当前未排序部分的最大值。每次将堆顶元素与当前未排序部分的末尾元素交换，使该最大值归位。交换后堆结构被破坏，需重新调整为大顶堆。重复此过程直到数组有序。

建堆阶段使用向下调整算法，时间复杂度为 O(N)；排序阶段共需 N-1 次堆顶交换与向下调整，每次调整 O(logN)，总复杂度 O(NlogN)。空间复杂度 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) {
        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) {
    // 向下调整建堆
    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--;
    }
}

冒泡排序

冒泡排序通过相邻元素的比较与交换，让较大（较小）的元素逐步'冒泡'到数组的末尾。每一轮遍历后，当前未排序部分的最大值会被推到末尾。加入提前终止优化后，若某趟遍历未发生交换，说明数组已有序，可直接结束。

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^2)，最优情况（已有序）为 O(N)。空间复杂度 O(1)，且是稳定排序。

性能对比总结

希尔排序和堆排序时间复杂度都是 O(NlogN) 量级，效率最高。其中堆排序不受输入数据分布影响，最优、最坏与平均均为 O(NlogN)。

插入排序和冒泡排序在数组有序时能达到 O(N)，但最坏情况均为 O(N^2)。两者在接近有序或部分有序场景下性能有差距，插入排序通常优于冒泡排序。

选择排序无论数据状态如何，时间复杂度始终为 O(N^2)，效率相对较低。

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