C++排序算法详解（从冒泡到快排，小白也能轻松掌握）

什么是排序算法？

排序算法就是将一组无序的数据按照特定规则（如从小到大或从大到小）重新排列的过程。在 C++ 中，我们通常对数组或 vector 进行排序。

1. 冒泡排序（Bubble Sort）

冒泡排序是最简单直观的排序方法。它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们。这个过程会像“气泡”一样把最大（或最小）的元素逐渐“浮”到顶端。

#include <iostream>using namespace std;void bubbleSort(int arr[], int n) {    for (int i = 0; i < n - 1; i++) {        for (int j = 0; j < n - i - 1; j++) {            if (arr[j] > arr[j + 1]) {                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }    }}int main() {    int arr[] = {64, 34, 25, 12, 22, 11, 90};    int n = sizeof(arr) / sizeof(arr[0]);    bubbleSort(arr, n);    cout << "排序后的数组: ";    for (int i = 0; i < n; i++)        cout << arr[i] << " ";    cout << endl;    return 0;}

时间复杂度：O(n²)，适合小规模数据。

2. 选择排序（Selection Sort）

选择排序的工作原理是每一次从待排序的数据中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。

#include <iostream>using namespace std;void selectionSort(int arr[], int n) {    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;        }        if (minIndex != i) {            int temp = arr[i];            arr[i] = arr[minIndex];            arr[minIndex] = temp;        }    }}int main() {    int arr[] = {64, 25, 12, 22, 11};    int n = sizeof(arr) / sizeof(arr[0]);    selectionSort(arr, n);    cout << "排序后的数组: ";    for (int i = 0; i < n; i++)        cout << arr[i] << " ";    cout << endl;    return 0;}

时间复杂度同样是 O(n²)，但比冒泡排序减少了交换次数。

3. 快速排序（Quick Sort）

快速排序是一种高效的分治排序算法。它通过一个称为“基准”（pivot）的元素将数组分为两部分：一部分小于基准，另一部分大于基准，然后递归地对这两部分进行排序。

#include <iostream>using namespace std;int partition(int arr[], int low, int high) {    int pivot = arr[high];    int i = (low - 1);    for (int j = low; j <= high - 1; j++) {        if (arr[j] < pivot) {            i++;            int temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;        }    }    int temp = arr[i + 1];    arr[i + 1] = arr[high];    arr[high] = temp;    return (i + 1);}void quickSort(int arr[], int low, int high) {    if (low < high) {        int pi = partition(arr, low, high);        quickSort(arr, low, pi - 1);        quickSort(arr, pi + 1, high);    }}int main() {    int arr[] = {10, 7, 8, 9, 1, 5};    int n = sizeof(arr) / sizeof(arr[0]);    quickSort(arr, 0, n - 1);    cout << "排序后的数组: ";    for (int i = 0; i < n; i++)        cout << arr[i] << " ";    cout << endl;    return 0;}

平均时间复杂度为 O(n log n)，是实际应用中最常用的排序算法之一。

总结

通过本教程，你已经掌握了三种核心的 C++排序算法：简单易懂的 冒泡排序、减少交换的 选择排序 和高效实用的 快速排序。建议初学者先从冒泡和选择排序练手，再挑战快速排序。多写代码、多调试，你会发现排序其实并不难！

记住：理解算法思想比死记硬背代码更重要。加油，未来的 C++ 高手！