排序算法详解：从冒泡到快速排序

为什么排序如此重要？

排序是计算机科学中最基础也最重要的算法之一。在信息学竞赛中：

• 很多题目需要对数据排序后才能处理
• 排序算法的思想可以应用到其他问题
• 理解排序有助于理解更复杂的算法

常见排序算法对比

冒泡排序

原理

冒泡排序通过不断交换相邻的逆序元素，将最大的元素"冒泡"到数组末尾。

代码实现

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        // 优化：如果某一轮没有交换，说明已经有序
        if (!swapped) break;
    }
}

适用场景

• 数据量很小（n < 50）
• 需要稳定的排序
• 教学演示

选择排序

原理

每一轮从未排序部分选择最小的元素，放到已排序部分的末尾。

代码实现

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) {
                minIdx = j;
            }
        }
        swap(a[i], a[minIdx]);
    }
}

特点

• 交换次数最少（最多 n-1 次）
• 不稳定（可能改变相等元素的相对顺序）

快速排序

原理

快速排序采用分治思想：

1. 选择一个"基准"（pivot）元素
2. 将数组分为两部分：小于基准的在左边，大于基准的在右边
3. 递归地对左右两部分排序

代码实现

int partition(int a[], int low, int high) {
    int pivot = a[high];  // 选择最后一个元素作为基准
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

void quickSort(int a[], int low, int high) {
    if (low < high) {
        int pi = partition(a, low, high);
        quickSort(a, low, pi - 1);
        quickSort(a, pi + 1, high);
    }
}

优化技巧

1. 随机选择基准：避免最坏情况
2. 三数取中：选择首、中、尾三个数的中位数作为基准
3. 小数组切换插入排序：当子数组很小时，插入排序更快

归并排序

原理

归并排序同样采用分治思想：

1. 将数组分成两半
2. 递归地对两半分别排序
3. 合并两个有序数组

代码实现

void merge(int a[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int* L = new int[n1];
    int* R = new int[n2];
    
    for (int i = 0; i < n1; i++) L[i] = a[left + i];
    for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) a[k++] = L[i++];
        else a[k++] = R[j++];
    }
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
    
    delete[] L;
    delete[] R;
}

void mergeSort(int a[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

特点

• 稳定排序
• 时间复杂度始终为 O(n log n)
• 需要额外空间 O(n)

C++ STL 中的排序

在竞赛中，直接使用 std::sort 是最高效的选择：

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

// 升序排序
sort(v.begin(), v.end());

// 降序排序
sort(v.begin(), v.end(), greater<int>());

// 自定义比较函数
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // 降序
});

// 对数组排序
int a[100];
sort(a, a + n);

std::sort 的时间复杂度是 O(n log n)，并且经过高度优化。

实战技巧

1. 结构体排序

struct Student {
    string name;
    int score;
};

// 按分数降序排序
bool cmp(const Student& a, const Student& b) {
    return a.score > b.score;
}

sort(students.begin(), students.end(), cmp);

2. 多关键字排序

// 先按分数降序，分数相同按名字升序
bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
}

3. 按照特定规则排序

// 按绝对值排序
bool cmp(int a, int b) {
    return abs(a) < abs(b);
}

总结

---

练习建议：在洛谷上搜索"排序"标签，从简单题开始练习！