快速排序

快速排序：使用的是分治思想（归并排序也是）；

（1）选一个元素M作为基准数。

（2）把小于等于M的元素放在数组的左边，大于M的元素放在数组右边；这是M的位置已是正确的，不再改变。

（3）对M左边、右边的的数组分别使用（1）（2），知道数组中只有一个元素。

性能：

最坏时间复杂度是O(n²)，平均时间复杂度是（nlogn）,最好时间复杂度是（nlogn），是一种不稳定排序。

快速排序的三步分治过程：分解，解决，合并。由于子数组是原址排序，所以不需要合并操作。

注：在代码中，p r 均是数组下标，p 是首元素的下标， r 是最后一个元素的下标

QuickSort( A, p, r)

if p < r

q = Partition( A, p, r )

QuickSort( A, p, q-1)

QuickSort( A, q+1, r)

算法的关键是 Partition 过程，他实现了对子数组 A[p, r] 的原址重排

Partition ( A, p, r )

x = A[ r ]

i = p - 1

for j = p to r -1

if A[ j ] <= x

i = i + 1

exchange A[ i ] with A[ j]

exchange A[ i+1] with A[ r ]

return i + 1

快速排序的随机化版本（使得算法对所有的输入都有较好的期望性能），新的划分程序中，只在真正进行划分前进行一次交换，QuickSort( A, p, r)代码不变；

RandomPartition( A, p, r)

i = Random(p, r)

exchance A[ r ] with A[ i ]

return Partition( A, p, r)

代码：

#include<iostream>
#include<vector>
using namespace std;
template<class T>
int Partition(vector<T>&A, int p, int r)    // p 和 r 均为数组段的下标，p是数组首元素下标，r是数组最后一个元素下标
{
    T x = A[r];
    int  flag = p - 1;
    for (int j = p; j <= r-1; j++)    //遍历数组中的元素
    {
        if (A[j] <= x)                // 将数组中小于 A[r]的元素移到数组的左边
        {
            flag = flag + 1;
            T temp = A[flag];
            A[flag] = A[j];
            A[j] = temp;
        }
    }
    T tem = A[flag + 1];
    A[flag + 1] = A[r];
    A[r] = tem;
    return flag + 1;
}
template<class T>
void QuickSort(vector<T>& Arry,int p,int r)
{
    if (p <= r-1)
    {
        int q = Partition(Arry,p,r); //返回的元素位置已经被正确分类，即下面函数参数有 q-1,q+1，
        for (int i = 0; i <= r; i++)
            cout << Arry[i] << " ";
        cout << endl;
        QuickSort(Arry,p,q-1);         //这里也是分治的思想，q位置的元素位置已正确，只需对（q,q-1）与（q+1,r）排序
        QuickSort(Arry, q+1,r);
    }
}

测试代码：

int main()
{
    vector<int> arry= { 210, 12,19, 4, 7, 10, 15,21, 41, 51, 61, 81, 71, 91, 100,310,250,630,0,17};
    for (int i = 0; i < 20; i++)
        cout << arry[i] << " ";
    cout << endl;
    QuickSort<int>(arry, 0, 19);
    for (int i = 0; i < 20; i++)
        cout << arry[i] << " ";
    cout << endl;
    cout << "BigThink" << endl;
    system("pause");
    return 0;
}

View Code

vector 容器做函数参数：

void Example( vector<int> vec);

void Example( vector<int> *vec);

void Example( const vector<int> * vec); //在函数内不能改变 vec指向的对象

void Example( vector<int>& vec);

void Example( const vector<int>& vec); // 在函数内不能改变 vec 对象