1.快速排序

1.快速排序

1.1快速排序的思想和复杂度

快排思想

1. 快速排序是在数组中选一个数字，然后按照这个数字将数组分为前后两部分，前半部分都比这个数字小，后半部分都比这个数字大。
2. 对第1步中的前半部分和后半部分分别作为一个独立的数组，按照第1步的规则进行切分。通过递归对整个数组排序。

用代码描述：

    void sort(vector<int> &vec)
    {
        sort(vec,0,vec.size()-1);
    }
    void sort(vector<int> &vec,int lo,int hi)
    {
        if(hi<=lo)return;
        int j=partition(vec,lo,hi); //选择切分数组的参考元素
        sort(vec,lo,j-1);
        sort(vec,j+1,hi);
    }

时间和复杂度

时间复杂度如表所示

算法	平均情况	最好情况	最差情况
快排	O(NlogN)	O(NlogN)	O(N^2)

空间复杂度：O(NlogN)

1.2快速排序的操作

假设有这样一个数组：

下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	5	2	1	9	8	6	0	7

对这个数组进行快速排序，我们首先要选择一个数在做切分，基本的快速排序选择数组vec的第一个数字作切分，我们选择下标为0，数字为v=4的元素作为切分依据。随后，对数组进行前后两部分的切分操作。具体来说，需要从左到右扫描的同时从右向左扫描。从左到右扫描的指针设置为i，从右到左扫描的指针设置为j。

指针		i								j
下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	5	2	1	9	8	6	0	7

1. 从左向右搜索大于切分元素的元素

从左到右的扫描过程中如果指针i向右移动的时候，vec[i]比参考元素v=4小，那么就继续向右移动。如果vec[i]比参考元素v=4大，那么就记录下标i，需要将vec[i]这个数字从数组vec的前半部分丢到后半部分。这里就有个问题了，需要把vec[i]丢到后半部分的哪个位置呢？不要急，丢到哪里需要我们从右向左扫描的时候找出这个位置。

指针			i							j
下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	5	2	1	9	8	6	0	7

（Q：后半部分和前半部分如何定义和理解呢？A：假设我们已经完成了一次扫描，那么分别向左和向右移动的下标i和下标j会相遇。下标i扫描所覆盖的区域就是这次扫描的前半部分，下标j扫描所覆盖的区域就是后半部分，这里有个概念即可）

2. 从右向左搜索小于切分元素的元素

从右到左的扫描过程中如果指针j向左移动的时候，vec[j]比参考元素v=4大，那么就继续向左移动。如果vec[j]比参考元素v=4小，那么就记录下标j，需要将vec[j]这个数字从数组vec的后半部分丢到前半部分。现在，我们就找到了从左向后扫描时丢过来的数字该放到哪里了。我们通过交换vec[i]和vec[j]两个数字就完成了一次扫描中的交换。

需要交换的两个数字找到了

指针			i						j
下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	5	2	1	9	8	6	0	7

交换两个数字

指针			i						j
下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	0	2	1	9	8	6	5	7

3. 重复第1步和第2步

在一次扫描中，需要把前半部分和后半部分都扫描一遍，直到下标i和下标j相遇。在扫描过程中，需要不断地进行第1步和第2步。所以i==j是边界条件(a)(b)，i>=j也是边界条件(c)。边界条件的逻辑是这样的：
(a)从左向右扫描，如果扫描到了最右端，那么达到边界条件，终止从左向右的扫描。
(b)从右向左扫描，如果扫描到了最左端，那么达到边界条件，终止从右向左的扫描。
(c)i从向左向右扫描，j从右向左扫描，i肯定小于j，如果相遇了那么就是i==j，终止这一次扫描。

4. 切分元素归位

完成一次扫描后，还需要将参考的数字v放在扫描完成的前半部分和后半部分的中间。

第一次扫描，交换了两个数字，最后把参考元素和前后两部分中间的元素互换

指针			i						j
下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	0	2	1	9	5	6	5	7
数组	1	3	0	2	4	9	8	6	5	7

OK, 可以上代码了。

1.3 C++代码

#include <iostream>
#include <vector>
using namespace std;

class Sort
{
public:
    void sort(vector<int> &vec)
    {
        sort(vec,0,vec.size()-1);
    }
    void sort(vector<int> &vec,int lo,int hi)
    {
        if(hi<=lo)return;
        int j=partition(vec,lo,hi);
        sort(vec,lo,j-1);
        sort(vec,j+1,hi);

    }
    void show(vector<int> &vec)
    {
        for(int i=0;i<vec.size();i++)
        {
            cout << vec[i] << " ";
        }
        cout << endl;
    }
    vector<int> init()
    {
        vector<int> vec;
        int arr[10]={4,3,5,2,1,9,8,6,0,7};
        vec.insert(vec.begin(),arr,arr+10);
        cout <<"ori:"<<endl;
        show(vec);
        return vec;
    }
    bool checkorder(vector<int> &vec)
    {
        for(int i=0;i<vec.size()-1;i++)
        {
            if(vec[i]>vec[i+1])return false;
        }
        return true;
    }
private:
    void exch(vector<int> &vec,int a,int b)
    {
        int tmp;
        tmp=vec[a];
        vec[a]=vec[b];
        vec[b]=tmp;
    }
    int partition(vector<int> &vec,int lo,int hi)
    {
        int v=vec[lo];
        int i=lo,j=hi+1;
        cout <<"scan round, before scan:"<<endl;
        show(vec);
        while(true)
        {
            while(vec[++i]<v){if(i==hi)break;}
            while(v<vec[--j]){if(j==lo)break;}
            if(i>=j)break;
            exch(vec,i,j);
        }
        cout <<"scan round, after scan:"<<endl;
        show(vec);
        exch(vec,lo,j);
        cout <<"scan round, exchange reference values:"<<endl;
        show(vec);
        cout <<"-----------------------"<<endl;
        return j;
    }
};

int main()
{
    Sort sortob;
    vector<int> mvec=sortob.init();
    sortob.sort(mvec);
    sortob.show(mvec);
    cout <<"--------result-------"<<endl;
    if(sortob.checkorder(mvec))
        sortob.show(mvec);
    else
    {
        cout << sortob.checkorder(mvec);
    }
    return 0;
}

输出结果：

image.png