raindayinrain头像
常用排序算法封面图

常用排序算法

1.冒泡排序(Bubble Sort)

思想

每轮从左到右扫描,相邻两个元素逆序就交换。一轮结束后,当前未排序部分的最大值必然被「冒」到最右端——像气泡上浮。

核心不变量:

第 k 轮结束后,最后 k 个元素已就位且有序。所以每轮的内层扫描范围可以缩短 1。

加一个提前退出优化:

某一轮如果一次交换都没发生,说明已有序,直接结束。

时间:

最好 O(n)(已有序 + 提前退出),平均/最坏 O(n²)

空间 :

O(1),稳定(相等元素只在严格大于时才交换,相对顺序不变)

代码

void bubbleSort(vector<int>& a) {
    int n = a.size();
    for (int end = n - 1; end > 0; --end) {   // 每轮把最大值冒到 end
        bool swapped = false;
        for (int i = 0; i < end; ++i) {
            if (a[i] > a[i + 1]) {            // 严格大于 => 稳定
                swap(a[i], a[i + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;                  // 一轮无交换 => 已有序
    }
}

2.快速排序(Quick Sort)

思想

1. 选一个基准值 pivot
2. 划分(partition):把数组重排成 [≤ pivot] [pivot] [≥ pivot]
3. 对左右两段递归重复

核心在划分,排序只是划分的副产品——pivot 每轮落到的位置就是它最终的位置,这个性质还衍生出快速选择算法(找第 k 大,平均 O(n))。

时间:

平均 O(n log n),最坏 O(n²)(每次划分都极端不均,如已排序数组总取首元素当 pivot)

空间:

递归栈平均 O(log n)

是否稳定:

不稳定,原地(不需要额外数组)

实践中是最快的通用排序:划分是顺序扫描、交换在数组内部进行,cache 局部性极好

代码(随机基准 + Hoare 划分 + 小区间插排优化)

#include <vector>
#include <utility>

// Lomuto 分区:以 a[hi] 为 pivot,返回 pivot 最终位置
int partition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo;                 // i 指向"≤ pivot 区域"的下一个空位
    for (int j = lo; j < hi; ++j) {
        if (a[j] <= pivot) {
            std::swap(a[i], a[j]);
            ++i;
        }
    }
    std::swap(a[i], a[hi]);     // pivot 放到正确位置
    return i;
}

void quickSort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

void quickSort(std::vector<int>& a) {
    if (!a.empty()) quickSort(a, 0, (int)a.size() - 1);
}

值得知道的点:

  • 随机基准把最坏情况从「特定输入必触发」变成「概率上几乎不发生」,这是工程标配;再进一步是三数取中(取首中尾的中位数)

3.归并排序(Merge Sort)

思想

1. 把数组从中间分成两半,分别递归排好
2. 合并(merge):双指针比较两个有序段的头部,依次取较小者放入临时数组

核心在合并两个有序序列——这个操作本身还独立出现在合并两个有序链表、外部排序等场景。

时间:

任何输入都是 O(n log n),没有最坏退化

空间 :

O(n)(临时数组)

稳定:

(合并时左边元素优先于右边相等元素)

访存模式是顺序读写,对链表排序、外部排序天然友好

代码

void mergeSort(vector<int>& a, vector<int>& tmp, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(a, tmp, l, mid);
    mergeSort(a, tmp, mid + 1, r);
    if (a[mid] <= a[mid + 1]) return;          // 已有序,跳过合并(重要优化)

    // 合并 [l, mid] 和 [mid+1, r]
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= 取左边 => 稳定
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    copy(tmp.begin() + l, tmp.begin() + r + 1, a.begin() + l);
}
void mergeSort(vector<int>& a) {
    vector<int> tmp(a.size());
    mergeSort(a, tmp, 0, (int)a.size() - 1);
}

4.完整测试 main

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

int main() {
    vector<int> data = {9, 3, 7, 1, 8, 3, 5, 2, 6, 4};

    auto a = data; bubbleSort(a);
    auto b = data; quickSort(b);
    auto c = data; mergeSort(c);

    for (int x : a) cout << x << ' '; cout << "(bubble)\n";
    for (int x : b) cout << x << ' '; cout << "(quick)\n";
    for (int x : c) cout << x << ' '; cout << "(merge)\n";
}

稳定性指的是:值相等的元素,排序后是否保持它们原来的先后顺序。

5.外部排序

快速排序,归并排序均为数据全部在内存,通过排序将其有序。
外部排序指的是数据太大,无法一次性载入内存,采取的策略是:

  • 将原始数据切分为k个块,保证每一块可以一次性载入内存完成排序
  • 依次加载每一块到内存,完成排序,写入临时文件
  • 维护一个最小堆,从k个文件各自取元素加入最小堆
  • 从最小堆取堆顶写入最终文件,写入元素所在临时文件再填充一个新元素到最小堆

性能优化手段:

  • 每个临时文件安排一个缓存,一次读一批
  • 从堆取出先放入缓存,攒够一批一次性写入最终文件

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/x13262608581/article/details/170744224

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--