快速排序

欢迎前往个人博客 驽马点滴 和视频空间 哔哩哔哩-《挨踢日志》

快速排序算法的思路很简单：
通过交换数组中的项，来确定一个位置 k ，使得左边的值小等于它，右边的值大于它，然后递归此方法即可。

#include "stdafx.h"
#include <iostream>
using namespace std;
const int SIZE = 100;

class LankeHelper
{
private:
    int *arr;
public:
    LankeHelper(int a[]){arr=a;};
    void QuickSort(int p, int r);
    int Partition(int p, int r);
    void print(int n);
};
void LankeHelper::QuickSort(int p, int r)
{
    if(p<r)
    {
        int k = Partition(p,r);
        QuickSort(p,k-1);
        QuickSort(k+1,r);
    }
}

int LankeHelper::Partition(int p, int r)
{
    int i=p;
    int j=r;
    int x=arr[p];
    while(i<j)
    {
        while(i<j&&arr[j]>=x)
        {
            --j;
        }
        arr[i] = arr[j];
        while(i<j&&arr[i]<=x)
        {
            ++i;
        }
        arr[j] = arr[i];
    }
    arr[i] = x;
    return i;
}

void LankeHelper::print(int n)
{
    for(int i=0;i<n;++i)
    {
        cout<<arr[i]<<"\t";
    }
    cout<<"\n";
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[8]={1,2,3,8,5,3,4,7};
    LankeHelper lh(a);
    cout<<"Original:"<<endl;
    lh.print(8);
    lh.QuickSort(0,7);
    cout<<"Sorted:"<<endl;
    lh.print(8);
    system("pause");
    return 0;
}