数据结构：排序算法详解（下）

4.交换排序

4.1 冒泡排序（BubbleSort）

基本思想： 所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

冒泡排序在 C 语言部分进行过详细的解析，这里就不过多赘述

4.2 快速排序（QuickSort）

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

4.2.1 hoare 版本

动图理解：

💻排序实现：

void QuickSort1(int* a, int left, int right) {
    if (left >= right) return;
    int begin = left, end = right;
    // 随机选 key
    int randi = left + (rand() % (right - left + 1));
    Swap(&a[left], &a[randi]);
    // 三数取中
    // int midi = GetMidNumi(a, left, right);
    // Swap(&a[midi], &a[left]);
    int keyi = left;
    while (left < right) {
        // 右边找小
        while (left < right && a[right] >= a[keyi]) --right;
        // 左边找大
        while (left < right && a[left] <= a[keyi]) ++left;
        Swap(&a[left], &a[right]);
    }
    Swap(&a[keyi], &a[left]);
    keyi = left;
    QuickSort1(a, begin, keyi - 1);
    QuickSort1(a, keyi + , end);
}