快速排序

快速排序类似于冒泡排序，冒泡排序是在一次排序中找出最大或者最小的数，然后将它冒出，快速排序是依次排序找出基准数的位置（或者说确定所有数的性质，大于基准数或者小于基准数），一般取数组第一个元素为基准数

过程是先确定一个基准数，然后经过一次排序，将所有大于基准的数放到基准数右边，所有小于基准数的都放大基准数左边。原数组就以基准数为标准分成了左右两个子集，对这两个子集继续做快速排序，直到所有子集都只剩下一个元素。

快速排序的平均时间复杂度时O（nlogn），最坏情况下的时间复杂度时O(n^2)

具体方法有挖坑法和指针交换法。

挖坑法就是将要移位的元素移到前一个挖的坑，然后它移位前的位置变成了下一个坑，数组的第一个元素作为基准数，也是第一个坑，然后基准数放到最后一个坑里面。

最后一个坑的判断条件：收尾下标为i,j，i后移，j前移，当i==j时，当前的i就是最后一个坑

代码

#include<iostream>
using namespace std;

int AdjArray(int* Array,int L,int R);
void QuickSort(int* Array, int L, int R);

int main(void)
{
    // Init array & Input Array
    int ArrayLen;
    cin >> ArrayLen;
    int* Array = new int[ArrayLen];
    for (int i = 0; i < ArrayLen; ++i)
        cin >> Array[i];

    QuickSort(Array, 0, ArrayLen - 1);

    for (int i = 0; i < ArrayLen; ++i)
        cout << Array[i] << " ";
    cout << endl;

    delete[] Array;
    system("pause");
    return 0;
}


// 挖坑法
int AdjArray(int* Array, int L, int R)
{
    int i = L;
    int j = R;
    int Hole = Array[L];// 第一个坑,注意是从传入的第一个坐标开始，不是从0开始

    while (i < j)
    {
        // 从后往前,顺序很重要
        while (i<j&&Array[j]>Hole)
            --j;
        if (i < j)
        {
            Array[i] = Array[j];
            ++i;
        }

        // 从前往后
        while (i<j&&Array[i]<Hole)
            ++i;
        if (i < j)
        {
            Array[j] = Array[i];
            --j;
        }
    }
    Array[i] = Hole;
    /*for (int t = 0; t <=R; ++t)
        cout << Array[t] << " ";
    cout << endl;*/
    return i;
}


// 递归调用
void QuickSort(int* Array, int L, int R)
{
    if (L < R)
    {
        int Loc=AdjArray(Array, L, R);
        QuickSort(Array, L, Loc - 1);
        QuickSort(Array, Loc + 1, R);
    }
}

拓展：数组中的第K大元素

比较基准数下标和K下标来决定走哪个递归

#include<iostream>

using namespace std;

int SingleSort(int* Array, int L, int R);
void QuickSort(int* Array, int L, int R,int MaxTh);
int ArrLen;
int main(void)
{
    //int ArrayLen;
    cin >> ArrLen;
    int* Array = new int[ArrLen];
    for (int i = 0; i < ArrLen; ++i)
        cin >> Array[i];

    int MaxTh;
    cin >> MaxTh;

    QuickSort(Array, 0, ArrLen - 1,MaxTh);

    cout << endl;
    system("pause");
    return 0;
}

int SingleSort(int* Array, int L, int R)
{
    int i = L;
    int j = R;
    int Hole = Array[i];
    while (i < j)
    {
        while (i<j&&Array[j]>Hole)
        {
            --j;
        }
        if (i < j)
        {
            Array[i] = Array[j];
            ++i;
        }

        while (i < j&&Array[i] < Hole)
        {
            ++i;
        }
        if (i < j)
        {
            Array[j] = Array[i];
            --j;
        }
    }

    Array[i] = Hole;
    return i;
}

void QuickSort(int* Array, int L, int R,int MaxTh)
{
    if (L < R)
    {
        int Loc = SingleSort(Array, L, R);
        if (Loc > ArrLen - MaxTh)
        {
            QuickSort(Array, L, Loc - 1, MaxTh);
        }
        if (Loc < ArrLen - MaxTh)
        {
            QuickSort(Array, Loc + 1, R, MaxTh);
        }
        if (Loc == ArrLen - MaxTh)
            cout << Array[Loc];
    }
}