C++排序算法全解析

排序算法是计算机科学中的基础内容，在C++编程中有着广泛的应用。本文将详细介绍C++中常见的排序算法，包括它们的原理、实现代码及性能分析。

冒泡排序（Bubble Sort）

原理

冒泡排序通过重复遍历待排序序列，比较相邻元素并交换顺序错误的元素，直到没有需要交换的元素为止。每一轮遍历会将最大的元素“冒泡”到序列末尾。

代码实现

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 提前终止优化
    }
}

性能

• 时间复杂度：$O(n^2)$（最好情况$O(n)$）
• 空间复杂度：$O(1)$
• 稳定性：稳定

---

选择排序（Selection Sort）

原理

每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。

代码实现

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        std::swap(arr[i], arr[minIndex]);
    }
}

性能

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定

---

插入排序（Insertion Sort）

原理

将未排序元素插入到已排序部分的适当位置，逐步构建有序序列。

代码实现

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++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;
    }
}

性能

• 时间复杂度：$O(n^2)$（最好情况$O(n)$）
• 空间复杂度：$O(1)$
• 稳定性：稳定

---

快速排序（Quick Sort）

原理

采用分治法，选择一个基准元素（pivot），将数组分为小于基准和大于基准的两部分，递归排序子数组。

代码实现

#include <cstdlib> // for rand()

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low + rand() % (high - low + 1)]; // 随机选择基准
    int i = low - 1, j = high + 1;
    while (i < j) {
        do ++i; while (arr[i] < pivot);
        do --j; while (arr[j] > pivot);
        if (i < j) std::swap(arr[i], arr[j]);
    }
    return j;
}

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

性能

• 时间复杂度：平均$O(n\times {\log }_{2}n)$，最坏$O(n^2)$
• 空间复杂度：$O({\log }_{2}n)$（递归栈）
• 稳定性：不稳定

---

归并排序（Merge Sort）

原理

将数组分成两半，递归排序后合并两个有序子数组。

代码实现

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int x = 0; x < temp.size(); ++x) {
        arr[left + x] = temp[x];
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

性能

• 时间复杂度：$O(n\times {\log }_{2}n)$
• 空间复杂度：$O(n)$
• 稳定性：稳定

---

堆排序（Heap Sort）

原理

将数组构建成大顶堆，依次将堆顶元素（最大值）与末尾元素交换，调整剩余元素为新堆。

代码实现

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

性能

• 时间复杂度：$O(n\times {\log }_{2}n)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定

---

C++标准库排序（std::sort）

原理

C++标准库的std::sort通常基于快速排序（结合堆排序和插入排序优化）。

使用示例

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5, 9};
    std::sort(arr.begin(), arr.end()); // 默认升序
    // 自定义降序排序
    std::sort(arr.begin(), arr.end(), [](int a, int b) { return a > b; });
    return 0;
}

性能

• 时间复杂度：平均$O(n\times {\log }_{2}n)$
• 空间复杂度：$O({\log }_{2}n)$（依赖实现）
• 稳定性：不稳定（需稳定排序请用std::stable_sort）

---

总结对比

算法	时间复杂度（平均）	空间复杂度	稳定性	适用场景
冒泡排序（Bubble Sort）	$O(n^2)$	$O(1)$	稳定	小规模数据，教学演示
选择排序（Selection Sort）	$O(n^2)$	$O(1)$	不稳定	少量数据，对稳定性无要求
插入排序（Insertion Sort）	$O(n^2)$	$O(1)$	稳定	小规模或近乎有序的数据
快速排序（Quick Sort）	$O(n\times {\log }_{2}n)$	$O({\log }_{2}n)$	不稳定	大规模数据，追求效率
归并排序（Merge Sort）	$O(n\times {\log }_{2}n)$	$O(n)$	稳定	大规模数据，需稳定排序
堆排序（Heap Sort）	$O(n\times {\log }_{2}n)$	$O(1)$	不稳定	大规模数据，空间受限
C++标准库排序（std::sort）	$O(n\times {\log }_{2}n)$	$O({\log }_{2}n)$	不稳定	通用场景，标准库优先

实际编程中，建议优先使用C++标准库的std::sort或std::stable_sort，它们经过高度优化且易于使用。