C++ 七大排序算法详解

二、冒泡排序

1. 思路

• 冒泡排序就是通过不断比较相邻元素：如果它们顺序有错误，就交换它们的位置，让较大的元素（或较小的元素）逐渐'冒泡'移动到列表的一端，经过多次循环这样的过程，最终使得整个列表变得有序。

2. 时间复杂度：O(n) ~ O(n^2)

• 最好情况（已排序）为 O(n)，最坏情况（逆序）为 O(n^2)。

3. 空间复杂度：O(1)

• 原地排序。

4. 稳定性：稳定

• 相同元素不会交换顺序。

代码示例：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void Bubble_Sort(vector<int>& vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        bool flag = 1;
        for (int j = 0; j < vec.size() - 1 - i; j++) {
            swap(vec[j], vec[j + 1]);
            flag = 0;
        }
        if (flag) return;
    }
}

int main() {
    vector<int> vec = { 4,3,1,5,9,2 };
    Bubble_Sort(vec);
    for (auto it : vec) {
        cout << it << " ";
    }
    return 0;
}

三、计数排序（桶排下标）

1. 思路

• 将数值作为桶号，遍历整个数组，对相应的桶进行计数。
  • 遍历原数组，找到最大值 max，申请 max+1 个空间的 bucket 数组（桶），初始化为 0，下标：0-max（vector bucket(max+1,0)）。
  • 遍历原数组，找到每个数值对应的桶号，并对桶计数 ++，即 bucket[vec[i]]++。
  • 遍历桶数组，根据桶内计数取出下标值，放入原数组中。

2. 时间复杂度：O(n)

• 线性时间，依赖于输入范围。

3. 空间复杂度：O(m)

• m 为最大值 max，需要额外空间。

4. 稳定性：不稳定

• 相同元素可能改变顺序。

代码示例：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void Bucket_Sort(vector<int>& vec) {
    // 找出 vec 最大值
    int vec_max = vec[0];
    for (auto it : vec) {
        vec_max = vec_max > it ? vec_max : it;
    }
    // 创建 bucket 数组：大小为：max+1
    vector<int> bucket(vec_max + 1, 0);
    // 使用 bucket 记录 vec 中的元素个数
    for (auto it : vec) {
        bucket[it]++; // 统计个数
    }
    // 遍历 bucket 输出并回填到 vec
    int idx = 0;
    for (int i = 0; i < bucket.size(); i++) {
        while (bucket[i] > 0) {
            vec[idx++] = i;
            bucket[i]--;
        }
    }
}

int main() {
    vector<int> vec = { 4,3,1,5,9,2,1,2,1,7,1 };
    Bucket_Sort(vec);
    for(auto it:vec) cout<<it<<" ";
    return 0;
}

四、插入排序（两个下标）

1. 思路

• 将数组分为有序与无序两部分，每次从无序表取出一个元素，插入到有序表的适当位置。开始时有序表只有一个元素，无序表有 n-1 个数。
• 每遍历一次，有序表元素增加 1，无序表减少 1，重复 n-1 次。

2. 时间复杂度：O(n) ~ O(n^2)

• 最好情况（已排序）为 O(n)，最坏情况（逆序）为 O(n^2)。

3. 空间复杂度：O(1)

• 原地排序。

4. 稳定性：稳定

• 相同元素不会改变相对顺序。

代码示例：

#include<iostream>
#include<vector>
using namespace std;

void insert_Sort(vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        int temp = vec[i]; // 要插入的元素
        // j-有序部分最后一个元素位置
        int j = i - 1;
        for (; j >= 0; j--) {
            if (temp < vec[j]) {
                vec[j + 1] = vec[j];
            } else {
                break;
            }
        }
        vec[j + 1] = temp;
    }
}

int main() {
    vector<int> vec = { 7,1,3,4,0,6 };
    insert_Sort(vec);
    for (auto it : vec) {
        cout << it << " ";
    }
    return 0;
}

五、堆排序

1. 思路

• 首先，从最后一个非叶子节点开始，自底向上调整数组使其成为最大堆，确保每个父节点都大于其子节点。
• 然后，重复将堆顶元素（最大值）与当前末尾元素交换，并调整剩余部分使其重新成为最大堆，最终实现排序。这一过程的时间复杂度为 O(n log n)，空间复杂度为 O(1)（原地排序），但稳定性较差，因为相同元素的相对顺序可能改变。

2. 时间复杂度：O(n \log n)

• 建堆和调整堆的过程。

3. 空间复杂度：O(1)

• 原地排序。

4. 稳定性：不稳定

• 相同元素可能改变顺序。

代码示例：

#include<iostream>
#include<vector>
using namespace std;

void adjustHeap(vector<int>& vec, int start, int end) {
    int father = start; // 根节点
    int child = 2 * father + 1; // 左子树
    // while 循环为了调整最大堆的过程中破坏子树结构，继续向下调整
    while (child <= end) {
        // 因为 child 是左子树，根节点要大于左右子树，所以在子树中找最大的与根节点比较
        // 防止右子树越界在数组中下标为 child+1 元素，child 就是子树中最大的元素
        if (child + 1 <= end && vec[child + 1] > vec[child]) {
            child++;
        }
        // 如果根节点小于 child 就交换
        if (vec[child] > vec[father]) {
            swap(vec[child], vec[father]);
            // 如果发生交换就继续向下调整，因为可能破坏子树最大堆结构
            father = child;
            child = 2 * father + 1;
        } else {
            return;
        }
    }
}

void HeapSort(vector<int>& vec) {
    // 从最后一个有子节点的节点开始调整
    for (int i = vec.size() / 2 - 1; i >= 0; i--) // vec.size()/2-1 是完全二叉树中最后一个有子节点子树的根
    {
        adjustHeap(vec, i, vec.size() - 1);
    }
    for (int i = vec.size() - 1; i >= 1; i--) {
        swap(vec[0], vec[i]); // 只有下标为 0 的元素被打乱，从根节点开始向下调整
        adjustHeap(vec, 0, i - 1);
    }
}

int main() {
    vector<int> vec = { 53,17,22,89,33,45,12 };
    HeapSort(vec);
    for (auto it : vec) {
        cout << it << " "; // 12 17 22 33 45 53 89
    }
    return 0;
}

六、快速排序

快速排序是一种分治算法，通过选择基准元素将序列分区，然后递归排序子序列。以下是两种版本：一个是三色旗分区（用于特定问题），另一个是完整的递归实现。

1. 三色旗分区版本

• 问题背景：此版本针对类似'荷兰国旗问题'的场景，序列只包含三种值（例如 0、1、2）。算法将序列分为三个区域：小于基准、等于基准、大于基准。
• 时间复杂度：O(n)，因为它只遍历序列一次进行分区。
• 算法步骤：
  • 初始化指针：i（左边界）、j（右边界）、index（当前索引）。
  • 遍历序列：比较当前元素与基准 temp（通常设为中间值，如 1）。
    • 如果 vec[index] == temp，则 index++。
    • 如果 vec[index] < temp，则交换到左侧区域（i++ 后交换）。
    • 如果 vec[index] > temp，则交换到右侧区域（j-- 后交换）。
  • 分区完成后，序列被划分为三个部分。

代码示例：

#include<iostream>
#include<vector>
using namespace std;

void quickSort(vector<int>& vec, int L, int R) {
    if (L > R) return;
    int temp = 1; // 基准值设为 1
    int i = L - 1;
    int j = R + 1;
    int index = L;
    while (index < j) {
        if (temp == vec[index]) index++;
        else if (temp > vec[index]) swap(vec[++i], vec[index++]);
        else swap(vec[--j], vec[index]);
    }
}

int main() {
    vector<int> vec = { 1,0,2,0,1,1,2,0 };
    quickSort(vec, 0, vec.size() - 1);
    for (auto it : vec) cout << it << " ";
    return 0;
}

2. 完整递归版本（三色旗 + 两次递归）

• 算法描述：在分区的基础上，递归排序左右子序列。基准值选择序列首元素 vec[L]。
• 时间复杂度分析：
  • 最好情况：每次分区基准值接近中位数，序列均匀划分。此时时间复杂度：O(n log n)，空间复杂度：O(log n)（递归栈深度）。
  • 最坏情况：每次基准值是最小或最大值，序列极度不平衡。此时时间复杂度：O(n^2)，空间复杂度：O(n)（递归栈深度）。
• 稳定性：不稳定，因为分区过程涉及交换，可能改变相同元素的相对顺序。

代码示例：

#include<iostream>
#include<vector>
using namespace std;

void quickSort(vector<int>& vec, int L, int R) {
    if (L > R) return;
    int temp = vec[L]; // 基准值为首元素
    int i = L - 1;
    int j = R + 1;
    int index = L;
    while (index < j) {
        if (temp == vec[index]) index++;
        else if (temp > vec[index]) swap(vec[++i], vec[index++]);
        else swap(vec[--j], vec[index]);
    }
    quickSort(vec, L, i);
    quickSort(vec, j, R);
}

int main() {
    vector<int> vec = { 7,3,0,9,4,2,2,6,5 };
    quickSort(vec, 0, vec.size() - 1);
    for (auto it : vec) cout << it << " ";
    return 0;
}

七、归并排序

归并排序是一种分治算法，基于二分法将序列递归分割，然后合并有序子序列。

1. 二分法基础

• 问题背景：二分查找是归并排序的灵感来源，用于在有序序列中高效定位元素。
• 时间复杂度：O(log n)，因为每次比较将搜索范围减半。
• 算法步骤：
  • 初始化指针：L（左边界）、R（右边界）。
  • 循环：计算中点 mid，比较目标值与 vec[mid]。
    • 如果 target < vec[mid]，则 R = mid - 1。
    • 如果 target > vec[mid]，则 L = mid + 1。
    • 如果相等，则返回元素。

代码示例：

#include<iostream>
#include<vector>
using namespace std;

int HalfSearch(vector<int>& vec, int target) {
    int L = 0;
    int R = vec.size() - 1;
    while (L <= R) {
        int mid = (R - L) / 2 + L;
        if (target < vec[mid]) {
            R = mid - 1;
        } else if (target > vec[mid]) {
            L = mid + 1;
        } else {
            return vec[mid];
        }
    }
    return -1;
}

int main() {
    vector<int> vec = { 1,4,2,5,8,3,7,7,2,9 };
    int n = HalfSearch(vec, 8);
    cout << n;
    return 0;
}

2. 归并排序算法

• 算法原理：递归将序列分为两半，排序子序列后合并。核心：合并过程，确保有序性。
• 时间复杂度：O(n log n)，因为分割和合并各需 O(log n) 层，每层 O(n) 工作。
• 空间复杂度：O(n)，由于需要辅助数组存储合并结果。
• 稳定性：稳定，因为合并时相同元素保持相对顺序（代码中使用 <= 比较）。

代码示例：

#include<iostream>
#include<vector>
using namespace std;

void Merge(vector<int>& vec, int L, int mid, int R) {
    vector<int> temp(R - L + 1);
    int i = L, j = mid + 1, index = 0;
    while (i <= mid && j <= R) {
        if (vec[i] <= vec[j]) temp[index++] = vec[i++];
        else temp[index++] = vec[j++];
    }
    while (i <= mid) temp[index++] = vec[i++];
    while (j <= R) temp[index++] = vec[j++];
    for (int k = 0; k < temp.size(); k++) vec[L + k] = temp[k];
}

void MergeSort(vector<int>& vec, int L, int R) {
    if (L >= R) return;
    int mid = (R + L) / 2;
    MergeSort(vec, L, mid);
    MergeSort(vec, mid + 1, R);
    Merge(vec, L, mid, R);
}

int main() {
    vector<int> vec = { 1,4,2,5,8,3,7,7,2,9 };
    MergeSort(vec, 0, vec.size() - 1);
    for (auto it : vec) {
        cout << it << " "; // 1 2 2 3 4 5 7 7 8 9
    }
    return 0;
}

八、整体比较与总结

时间复杂度对比

• O(n²) 级别：选择排序、冒泡排序、插入排序。适用于小规模数据或部分有序数据，其中插入排序在接近有序时效率最高（接近 O(n)）。
• O(n log n) 级别：堆排序、快速排序、归并排序。适合大规模数据，快速排序平均性能最优，但最坏情况退化为 O(n²)；堆排序稳定在 O(n log n)；归并排序稳定但需额外空间。
• O(n) 级别：计数排序（桶排）。仅适用于整数且范围较小的数据，空间消耗与数据范围相关。

空间复杂度对比

• 原地排序（O(1)）：选择排序、冒泡排序、插入排序、堆排序、快速排序（递归栈空间不计入，但最坏情况下递归深度为 O(n)）。
• 非原地排序：归并排序（O(n)）、计数排序（O(m)，m 为数据范围）。

稳定性对比

• 稳定算法：冒泡排序、插入排序、归并排序。保持相同元素的相对顺序。
• 不稳定算法：选择排序、堆排序、快速排序、计数排序（依赖具体实现）。

通过对比可见，不同排序算法在时间、空间、稳定性上各有优劣，实际选择需结合数据规模、分布特征及稳定性需求。