[数据结构与算法]快速排序 C++递归实现

一、思路

快速排序是冒泡排序的进阶版。

快速排序和归并排序的思路是差不多的，都是分治的思想，即把一个数组划分成小数组来处理。我写的归并排序讲解
只不过，归并排序每次划分小数组的方式都是把他对半分，而快速排序需要一个基准值pivot，来把数组分成两部分。

1. 选取pivot

基准值的选取方式会影响到算法的实际效率，这里我们从最简单的讲起，把基准值开始选定位数组的第一项。

int pivot = arr[left];

2. 确定pivot位置

确定pivot的位置，结果是数组左边的值都小于pivot，数组右边的值都大于pivot。
这个步骤可以用双指针实现，一个指针指向数组左端，另一个指针指向数组右端。

注意：第一步已经记录下了left位置上的值pivot，所以下面操作不会覆盖。

先从右端找到第一个小于pivot的值，把它的值赋值给left上的元素。然后从左端找到第一个大于pivot的元素，把他的值赋值给right上的元素。重复上述操作，直到 left >= right。

 while (left < right)
    {
        // 先从数组右边开始找，找到第一个小于pivot的元素
        // 就将其赋值给当前left处的元素，由于第一步已经把left的值
        // 赋值给pivot，所以不会覆盖丢失
        while (left < right && arr[right] >= pivot)
        {
            right--;
        }
        arr[left] = arr[right];
        // 再从数组left位置向后找到第一个大于pivot的位置
        // 将其赋值给right上的元素
        while (left < right && arr[left] <= pivot)
        {
            left++;
        }
        arr[right] = arr[left];
        // swap(arr[left], arr[right]);
        // 结束的条件是left>=right，说明此时数组都被扫描了一遍
    }
    // 最后left的位置就是pivot的位置，将left的位置赋值pivot。
    arr[left] = pivot;

然后把pivot赋值给left位置，此时pivot的位置就已经确定，就是left，这里记作pivotIndex。

3. 分离数组

按找到的位置把数组分成两部分，递归处理左右部分即可。

二、代码

代码部分我把寻找基准位置封装了一个函数quick。

#include <bits/stdc++.h>
using namespace std;
int quick(int arr[], int left, int right)
{
    // 选一个位置作为基准值，使排序后的数组：
    // 左边的数都小于它，右边的数都大于他
    // 随机选择基准可以提高性能
    int pivot = arr[left];
    while (left < right)
    {
        // 先从数组右边开始找，找到第一个小于pivot的元素
        // 就将其赋值给当前left处的元素，由于第一步已经把left的值
        // 赋值给pivot，所以不会覆盖丢失
        while (left < right && arr[right] >= pivot)
        {
            right--;
        }
        arr[left] = arr[right];
        // 再从数组left位置向后找到第一个大于pivot的位置
        // 将其赋值给right上的元素
        while (left < right && arr[left] <= pivot)
        {
            left++;
        }
        arr[right] = arr[left];
        // swap(arr[left], arr[right]);
        // 结束的条件是left>=right，说明此时数组都被扫描了一遍
    }
    // 最后left的位置就是pivot的位置，将left的位置赋值pivot。
    arr[left] = pivot;
    // 由于接下来要分别处理pivot两边的数组，所以返回他的位置
    // 方便下一轮排序
    return left;
}
void quickSort(int arr[], int left, int right)
{
    // 外层if的目的是当划分到最小单位时，作为递归退出条件
    if (left < right)
    {
        int pivotIndex = quick(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    else
    {
        return;
    }
}
int main()
{
    int arr[10] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    quickSort(arr, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        cout << arr[i] << ' ';
    }
    system("pause");
    return 0;
}

三、时间复杂度和空间复杂度

时间复杂度： 递归次数 * 单层逻辑执行次数

单层逻辑：每次都要比较和赋值，也就是数组长度length次；

最坏：
递归：划分数组为一个空数组和一个少一个元素的数组。也就是要递归 n - 1次
总体次数就是：n + (n - 1) + … + 2
时间复杂度就是O(n ^ 2)

平均：
跟归并排序一样，每次都划分成两个长度相等的数组.
那么时间复杂度就是O(nlogn)

空间复杂度：在原数组上操作，每次只是传入处理区间，所以复杂度为O(1)。