快速排序

没想到在网站上发布的第一篇算法居然是快排😉

1. 什么是快速排序❓️

今天我们介绍的算法是快速排序，又是一个有关排序的算法。正如它的名字所表达的那样，快速排序的最大优点在于它的速度非常快。在有些时候要比堆排序、归并排序等优秀算法更加快速。⏩️

快速排序的基本思想与归并排序的一样，主打一个分治。其整体思路如下：

1. 选定一个数num作为中间值
2. 将比num小的数放在其左边，比num大的数放在其右边
3. 分别对num左侧和右侧的新数组进行前两步操作
4. 直到最终新数组只剩下1个元素，排序完成

接下来通过图示的方式展示一下快排的策略。

2. 快排图示🎞️

首先这里有一组无序数组，我们用长度不同的矩形表示。

我们从中随机选取一个数字最为中间值。

现在，将所有小于中间值的元素放在中间值的左侧，大于它的放在它的右侧。

现在可以看到，在中间值左侧的元素都比它矮，右侧的都比它高。我们将中间值左侧的元素视为新的数组，并从中随机选取中间值。

然后，对左侧的新数组进行同样的操作；将小于中间值的放在左侧，大于它的放在右侧。

现在可以看到，左侧小数组还可以进行进一步划分。中间值的左侧没有元素，相当于数组为空，我们不考虑。中间值的右侧有元素，再一次建立小数组。并且，在这个小数组里，再一次随机选择中间值。

最后，对这个小小数组再进行一次排列，小放左，大放右。

此时，小小数组里面中间值的左侧没有元素，不考虑；中间值的右侧有元素，而右侧形成的数组长度为1，本身就是有序的，所以无需处理。这样我们发现，对于刚开始时候选择的中间值，其左侧已经排列完全。

运用同样的方式，对中间值右侧的数组进行处理，最终可得到一个从小到大排列完全的数组。

由此可见，快排本身的思想还是分治。对形成的小数组以递归的方式层层调用快排函数，直到数组长度为0或1，即可停止递归。所以其中最重要的操作，是大小分类（即 将比中间值小的放左边，大的放右边）。

来一段C++实现一下：

// 快排主体
// 选定中值元素，调用分割函数
// 再对分割好的左右两个子数组快排
void QuickSort(int left, int right)
{
    if(right <= left)  // 如果左右指针重合，证明只有一个元素
        return;
    int middle = Partition(left, right);  // 分割并获取中间元素下标
    // 分别快排
    QuickSort(left, middle - 1);
    QuickSort(middle + 1, right);
}

上面的代码实现了一个非常简单的内容。主要就是快排分治递归的一个实现。可以看出，其中最重要的操作就是Partition函数。Partition函数中包含了选择中间值和根据大小分类的操作。接下来我们看一下它是如何实现的。

3. 如何进行大小分类📊

首先，从这段数组中随机选取一个数作为中间值，这里我们直接选择最后一个数字，并标记它的下标middle。同时创建两个指针i j放置于最左端。

注意：这里的middle i j全部为下标指针，并不是数值本身。在后期交换数值时，只交换下标对应的数值。

现在，j将要从最左端扫到middle前面（从left到right-1）。依次检查是否有数值小于middle的数值。如果有，则进行下面的操作：

• 将i和j的数值交换。
• i向右移动1位。

也就是说，j只有在小于middle时才会与i交换；而i只有在与j交换后才会移动1次。

此时，我们会发现，i j middle将整个数组分成了4个部分。分别是：

1. 小于等于middle的数
2. 大于等于middle的数
3. 未探索的区域
4. middle本身

j就是一个判断扫描，i是一个限制位，用于限制小于middle的数的范围。i与j交换时就相当于把一个小的数移到区域1里面；而因为区域1因此多了一个数，所以i要加1来扩大区域1的长度。

最后，j扫描到了middle的前面。此时i左侧的元素都大于middle，i（包含i）到middle-1的元素都大于middle。

此时，只需要将i与middle的数值交换，就完成了大小分类的操作。

再来看一下上面展示过的C++代码：

// 快排主体
// 选定中值元素，调用分割函数
// 再对分割好的左右两个子数组快排
void QuickSort(int left, int right)
{
    if(right <= left)  // 如果左右指针重合，证明只有一个元素
        return;
    int middle = Partition(left, right);  // 分割并获取中间元素下标
    // 分别快排
    QuickSort(left, middle - 1);
    QuickSort(middle + 1, right);
}

可以看出Partition函数的返回值为大小分类操作后中间值的下标；由上图可知只需要返回i就完成了操作。

再来一段C++实现一下：

// 分割函数
// 将区间里的元素按照选定的中值元素进行分类
// 比中值元素小的放左边，大的放右边
int Partition(int left, int right)
{
    int middle = right;  // 选取最后一个作为中值元素
    int i = left;
    for(int j = left; j < right; j ++)
        if(number_list[j] <= number_list[middle])
        {
            Swap(number_list[i], number_list[j]);
            i ++;
        }
    Swap(number_list[i], number_list[middle]);
    return i;
}

这样便完成了大小分类。

4. 完整快排代码🧾

将上面介绍过的代码进行合并，就形成了基本快排的完整代码。

#include <iostream>

using namespace std;

int number_list[100];


// 交换两个数字
void Swap(int &numberA, int &numberB)
{
    int numberC = numberA;
    numberA = numberB;
    numberB = numberC;
}


// 分割函数
// 将区间里的元素按照选定的中值元素进行分类
// 比中值元素小的放左边，大的放右边
int Partition(int left, int right)
{
    int middle = right;  // 选取最后一个作为中值元素
    int i = left;
    for(int j = left; j < right; j ++)
        if(number_list[j] <= number_list[middle])
        {
            Swap(number_list[i], number_list[j]);
            i ++;
        }
    Swap(number_list[i], number_list[middle]);
    return i;
}


// 快排主体
// 选定中值元素，调用分割函数
// 再对分割好的左右两个子数组快排
void QuickSort(int left, int right)
{
    if(right <= left)  // 如果左右指针重合，证明只有一个元素
        return;
    int middle = Partition(left, right);  // 分割并获取中间元素下标
    // 分别快排
    QuickSort(left, middle - 1);
    QuickSort(middle + 1, right);
}

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i ++)
        cin >> number_list[i];
    
    QuickSort(0, n - 1);

    for(int i = 0; i < n; i ++)
        cout << number_list[i] << ' ';

    return 0;
}

---

OK，这就是快排的简单介绍，作为网站的第一篇算法介绍发布出来，还是花了很多心思的🤧。后期会以相同的方式发布算法介绍🫡。如果感兴趣的话可以加入收藏夹哦🤗！

文章完全原创，如引用文本和图片，希望添加来源。欢迎大家取用，营造良好开源环境！😘😘😘