​ 几个排序算法

🔸 插入排序（Insertion Sort）

基本思路： 将当前元素插入到前面已经排好序的部分中。

情况 时间复杂度
最好情况 O(n)
平均情况 O(n²)
最坏情况 O(n²)
空间复杂度 O(1)
稳定性 ✅ 稳定

优化：

  • 当数组基本有序时，插入排序性能非常好。
  • 可以用二分查找优化插入位置（但写法稍复杂）。
1
2
3
4
5
6
7
8
9
10
11
void insertionSort(vector<int>& arr) {
    for (int i = 1; i < arr.size(); ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

🔸 希尔排序（Shell Sort）

基本思路： 将数组按一定间隔分组做插入排序，逐渐减小间隔到1。

情况 时间复杂度
最好情况 O(n log n)
平均情况 O(n^1.3) ~ O(n²)
最坏情况 O(n²)
空间复杂度 O(1)
稳定性 ❌ 不稳定

优化：

  • 不同的“增量序列”会影响性能，如：Shell、Hibbard、Sedgewick 等。
  • 一般建议使用 gap = gap / 2 的方式即可满足普通需求。
1
2
3
4
5
6
7
8
9
10
11
12
13
void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i], j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

🔸 冒泡排序（Bubble Sort）

基本思路： 每轮从前往后，两两比较，把最大的“冒”到最后。

情况 时间复杂度
最好情况 O(n)
平均情况 O(n²)
最坏情况 O(n²)
空间复杂度 O(1)
稳定性 ✅ 稳定

优化：

  • 加一个 flag，如果某一轮没有发生交换，说明已经有序，可以提前结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

🔸 快速排序（Quick Sort）

基本思路： 选一个“基准值”，把比它小的放左边，大的放右边，然后递归。

情况 时间复杂度
最好情况 O(n log n)
平均情况 O(n log n)
最坏情况 O(n²)
空间复杂度 O(log n)
稳定性 ❌ 不稳定

优化：

  • 随机化选取 pivot（避免最坏情况如已排序数组）
  • 小数组可用插排代替递归（如 n < 10）
  • 使用“三数取中法”选 pivot 更稳健
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) --high;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) ++low;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}