快速排序

#include "stdafx.h"
#include <iostream>

using namespace std;
int RandomInRange(int start,int end);
void Swap(int *p,int *q);

int patition(int data[],int length,int start,int end)
{
    if(data==NULL||length<=0||start<0||end>=length)
        throw new exception("Invalid Parameters");
    int index=RandomInRange(start,end);
    Swap(&data[index],&data[end]);

    int small=start-1;//存储要交换的位置
    for(index=start;index<end;index++)
    {
        if(data[index]<data[end])
        {
            ++small;
            if(small!=index)
                Swap(&data[index],&data[small]);
        }
    }
    ++small;
    Swap(&data[small],&data[end]);
    return small;
}

int RandomInRange(int start,int end)
{
    return start+rand()%(end-start);
}

void Swap(int *p,int *q)
{
    int temp;
    temp=*p;
    *p=*q;
    *q=temp;
}

void QuickSort(int data[],int length,int start,int end)
{
    if(start==end)
        return;
    int index=patition(data,length,start,end);
    if(index>start)
        QuickSort(data,length,start,index-1);
    if(index<end)
        QuickSort(data,length,index+1,end);
}


int _tmain(int argc, _TCHAR* argv[])
{
    int data[10]={1,4,7,0,6,10,3,8,2,9};
    QuickSort(data,10,0,9);
    cout<<"After QuickSort:"<<endl;
    for(int i=0;i<10;i++)
        cout<<data[i] <<" ";
    cout<<endl;
    return 0;
}

PS:在数组本身已经排好序，而每轮都是以最后一个数字作为比较标准，此时快速排序的效率只有O(n^2)