一文拿捏快速排序算法

🔥前言

今天还是算法的主题，分享快速排序的算法解析，并且使用vector容器实现，算是对知识的练习与巩固。

快速排序算法解析

一、掌握快排的算法流程

算法思想如下：

通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。

其中的基准元素选择不唯一，可以采取以下五种方法：
- 取第一个元素
- 取最后一个元素
- 取位于中间位置的元素
- “三者取中的规则”
- 取位于low和high之间的随机数，用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high)，用A[P]作为基准，这相当于强迫R[low:high]中的元素是随机分布的
二、快排的代码实现与效果

C++源码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//快排,分两步骤：分区和递归

//初始化动态数组
void getArray(vector<int>& v)
{
    srand((unsigned int)time(NULL));
    int n = 0;
    cout << "请出入数组的大小为："; cin >> n;
    for (int i = 0; i < n; i++) {
        v.push_back(rand() % 100 + 1);
    }
    cout << endl;
}
//使用迭代器打印数组元素
void printArray(vector<int>v) {
    for(vector<int>::iterator it=v.begin();it!=v.end();it++)
    {
        cout << *it << " " ;
    }
    cout << endl;
}
//快排第一步：分区
int divided(vector<int>&v,int low,int high)
{
    int p = v[low];
    while (low < high)
    {
        while (low < high && p <= v[high])
            high--;
        v[low] = v[high];
        while (low < high && p >= v[low])
            low++;
        v[high] = v[low];
    }
    v[low] = p;
    return low;
}
//快排第二部，递归
void repeact(vector<int>&v,int low,int high)
{
    if (low > high)    return;
    int flag = divided(v, low, high);
    repeact(v,low,flag-1);
    repeact(v,flag+1,high);

}
int main(void)
{
    vector<int>v;
    getArray(v);
    //sort(v.begin(),v.end());
    printArray(v);
    repeact(v, 0, v.size() - 1);
    printArray(v);
    return 0;
}

运行效果：

在这里插入图片描述

三、具体代码分析

快速排序的代码相信网上有很多一样的，所以博主分享一个特别的：用动态数组vector容器实现快速排序。下面就是代码解析：

1、分区函数 divided

这里选择数组中左边界作为基准元素 p，外层while循环以及内层while循环的条件都要有low<high，这样做的目的是为了退出循环时让low和high相等。

对于内层while循环，由于我选的是左边界作为基准元素，那么我们就应该从数组右端往前依次与基准元素标记：如果基准元素小，右端元素向前移动，high递减；如果基准元素大，直接将右边小的元素扔到数组下标low的位置，不用担心左边界被覆盖，因为我们用基准元素记录了。然后用左端元素与基准元素比较，如果基准元素大，左端向右移动，low递增；如果基准元素小，将左端元素大的值扔到数组下标high的位置。直到low==high，循环结束，此时数组被分为两部分：low左边的值都要小于或者等于low右边的值。最后将基准元素赋到下标low的位置并返回该下标即可。

2、递归 repeact

使用递归来对数组的子序列进行划分，同样的子序列也会调用递归来对其子序列划分，直到子序列长度为零，这时候整个数组就是一个有序的序列了

首先给出递归结束的条件：low>high，这个条件什么时候会触发呢？上面以及提到了是子序列长度为零，所以我们每次调用递归 都要缩减序列的边界 。通过diveded函数来得到每次划分成两部分序列的下标，以此作为子序列的某一边界，这样随着程序的运行，子序列逐渐缩小，最终排序的结果就是我所想的。