数据结构——排序算法：冒泡、快速排序与归并排序详解

1.2.1 Hoare 版本 快排

算法思路： 创建左右指针，确定基准值。 从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环。 其实就是确定一个数为基准值，然后根据基准值，把当前区域的数据分成两部分，左边小于基准值，右边大于基准值，然后再递归到分好的区域，继续重复操作，一个大问题划分成无数个一样的子问题。

int QuickSort_Hoare(int* a, int left, int right) {
    int keyi = left; // 先定义区间第一个数为基准值
    while (left <= right) { // 只要 left<right 就继续循环
        // 我们这里 right 是找比基准值小的数据，left 是找比基准值大的数据，然后进行调换
        while (left <= right && a[right] > a[keyi]) // 当右边的值大于基准值时 right-- 直到找到小于基准值的再跳出循环
            right--;
        while (left <= right && a[left] < a[keyi]) // 当左边的数据小于基准值时 left++ 直到找到大于基准值的再跳出循环
            left++;
        // 两个循环跳出后 left 对应的数据大于基准值，right 对应的数据小于基准值
        // 对数据进行调换，这样就把小的放在左边，大的放在右边
        if (left <= right) {
            swap(a[right--], a[left++]);
        }
    }
    // 当 left>right 的时候，交换最开始的基准值的位置，这个时候新的基准值就取 right
    swap(a[right], a[keyi]);
    return right; // 到此，新的区间划分就处理好了，新的基准值返回就好啦
}

为什么跳出循环后 right 位置的值一定不大于 key？ 当 left > right 时，即 right 走到 left 的左侧，而 left 扫描过的数据均不大于 key，因此 right 此时指向的数据一定不大于 key。

问题 2：为什么 left 和 right 指定的数据和 key 值相等时也要交换？ 相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，相等也交换能进行有效的分割排序。 如果不相等才交换的话，假设数据全是相同的数据，那每次基准值只能找到初始基准值的下一个，时间复杂度会变成 O(N^2)。

快排是挺快的，但好东西总有缺陷。

快排：Hoare 版本的时间复杂度 划分区间递归的时间复杂度为 logn 每次区间内找新的基准值时间复杂度为 n 时间复杂度为 N*logN 但是在数据有序的时候，时间复杂度还是 O(N^2)，新的基准值只能找到 key 的下一个数字，划分区间的效率很低

1.2.2 挖坑法 快排

思路： 创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的'坑'，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的'坑'，结束循环后将最开始存储的分界值放入当前的'坑'中，返回当前'坑'下标（即分界值下标）。 就是先从右往左找，再从左往右找，不断循环，直到 left>right，过程中数值一直在迭代交换，这个时候最后一个坑刚好放最开始挖的值。

相比 Hoare 还是有差别的。

int QuickSort_Pit(int* a, int left, int right) {
    int hole = left; // 找到第一个坑
    int key = a[left]; // 把第一个坑保存起来
    while (left < right) { // left==right 时跳出循环，最后一个坑
        while (left < right && a[right] >= key) // 从右开始往左找
            right--;
        a[hole] = a[right]; // 当 right--的循环跳出后，这个时候 right 对应的值小于 key，把当前 right 的值换到坑里
        hole = right; // right 变成新的坑
        while (left < right && a[left] <= key) // 从左开始往右找
            left++;
        a[hole] = a[left]; // 当 left++的循环跳出后，这个时候 left 对应的值大于 key，把当前 left 的值换到坑里
        hole = left; // left 变成新坑
    }
    a[hole] = key; // 大循环结束后 left=right
    return hole; // 这个新坑留给一开始的 key 值，返回新的基准值下标
}

挖坑法完毕。

挖坑法和 Hoare 版本的时间复杂度一样 n*logn 但是在特殊情况也会有不好的地方，在数据有序的时候或者数据全部相同时，时间复杂度还是会变成 O(N^2)

1.2.3 Lomuto 前后指针 快排

创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。 前后指针是我认为最好理解，也是代码最简单的一个。 就是定义一个 cur 指针向前走，一个 prev 指针在后面跟着，cur 找比基准值小的数据。

话不多说，上代码。

int QuickSort_Lomuto(int* a, int left, int right) {
    int prev = left; // 定义 prev cur 指针
    int key = left;
    int cur = left + 1;
    while (cur <= right) {
        if (a[cur] < a[key] && ++prev != cur) // 当 cur 对应的值小于 key 时，可以考虑将 prev 与 cur 对应的值交换
        {
            // 但如果这个时候，cur 刚好是 prev 的下一个值，是没有必要交换的
            // 所以要判断 prev++与 cur 是否相等
            swap(a[prev], a[cur]);
        }
        ++cur; // 每次循环 cur++一次
    }
    swap(a[key], a[prev]); // 循环结束之后，prev 对应的值是小于 key 的，prev 的下一个就是大于 key 的，这个时候调换 key 和 prev 的值
    return prev; // 找到新的基准值下标返回
}

仔细了解前后指针的流程，想必也会感觉到，当数据有序或者是全部相同时，前后指针也是 O(N^2) 的时间复杂度。 想想数据全部相同或者有序，其实也没有排序的需要了，除非是算法题卡了数据相同的样例。 所以快排的三种方法还是可行的。

快速排序特性总结：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

快排的基本内容就到这里啦。

二、归并排序

归并排序算法思想： 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

底层核心还是递归，把一个大区间逐渐分成无数个小区间，（一个大问题分成无数个相同的子问题），快排和归并都是用到了递归，想想递归真的好用。

还有一个问题就是在递归到最后一层之后，怎么合并两个子区间让他们有序，这里我想到前面我们做过的习题，供参考。

话不多说上代码。

void MergeSort(int* arr, int left, int right, int* tmp) {
    // 把大区间分配数个小空间
    // 两个小空间 排序成一个空间 用 tmp 接受 返回赋值给原数组
    if (left >= right) // 递归出口
        return;
    int mid = left + (right - left) / 2; // 分成两个区间 采用二分
    MergeSort(arr, left, mid, tmp); // 左区间
    MergeSort(arr, mid + 1, right, tmp); // 右区间
    // 递归处理之后 现在就是合并两个子区间 使他们有序
    int begin1 = left, end1 = mid; // 第一个区间的 begin 和 end
    int begin2 = mid + 1, end2 = right; // 第二个区间的 begin 和 end
    int index = begin1; // 新的下标 对应 tmp 数组
    while (begin1 <= end1 && begin2 <= end2) // 合并两个数组的流程 不多赘述啦
    {
        if (arr[begin1] < arr[begin2]) {
            tmp[index++] = arr[begin1++];
        } else {
            tmp[index++] = arr[begin2++];
        }
    }
    while (begin1 <= end1) // 有数组没有全部传给 tmp 的情况
        tmp[index++] = arr[begin1++];
    while (begin2 <= end2)
        tmp[index++] = arr[begin2++];
    for (int i = left; i <= right; i++) // 赋值返回原数组
        arr[i] = tmp[i];
}

void MergeSortWrapper(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n); // 我们这里传一个新开的 tmp 数组空间进去，辅助合并两个子区间
    MergeSort(arr, 0, n - 1, tmp);
    free(tmp);
}

仔细回看，归并其实也不难，就是一个递归的处理，然后再合并两个区间而已。

实话实说，归并稳定，时间复杂度一直是 O(nlogn)，不管数据是否有序是否相同。

归并排序特性总结：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)