排序算法之快速排序-蒲公英云

排序算法之快速排序

快速排序是冒泡排序的改进版，也是最好的一种内排序，也是作为程序员必须掌握的一种排序方法。

快速排序的基本思想是

1、先从数列中取出一个数作为基准数

2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3、再对左右区间重复第二步，直到各区间只有一个数

所以我是把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。

下面再看看示图理解下吧：

下面是快速排序的C++代码：

//
// Created by liushihao on 19-6-5.
//
#include "iostream"
using namespace std;
typedef int KeyType;
typedef struct
{
    KeyType key;
    int data;
}RecType;
int partition(RecType R[], int s,int t)
{
    int i=s,j=t;
    RecType tmp=R[i];
    while(i<j)
    {
        while(j>i && R[j].key>=tmp.key)
            j--;
        R[i]=R[j];
        while(i<j && R[i].key<=tmp.key)
            i++;
        R[j]=R[i];
    }
    R[i]=tmp;
    return i;
}
void QuickSort(RecType R[], int s, int t)
{
    int i;
    if(s<t)
    {
        i=partition(R, s, t);
        QuickSort(R, s, i-1);
        QuickSort(R, i+1, t);
    }
}
int main()
{
    int n;
    cin>>n;
    RecType R[n];
    for(int i=0;i<n;i++)
    {
        cin>>R[i].key;
    }
    for(int i=0;i<n;i++)
    {
        cout<<R[i].key<<" ";
    }
    QuickSort(R, 0, n-1);
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<R[i].key<<" ";
    }
    return 0;
}