快速排序(Quick Sort)其是速度最快的排序方式，時間復雜度為O(nlogn),最差情況下為O(n^2).由于O(nlogn)中的系數(shù)很小，所以很快，在實際中應用多。其是in place的排序方式，但是unstable（不穩(wěn)定）
快速排序也是使用分而治之方法的應用，將任務分成子任務(divide)，然后解決子任務(conquer)，最后將結(jié)果組合起來。
其主要由2部分組成，partition(int p,int r)和quicksort(int p,int r).
其中quicksort(int p,int r)
{
if(p<r)
{
int q = parition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
而parition（int p,int r)函數(shù)只是選取一個pivot，然后將pivot將兩部分分開。
具體的代碼如下：
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define MAXSIZE 10000000
int arr[MAXSIZE];
using namespace std;
void print(bool flag=false)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
void merge(int A[],int p,int q,int r)
{
int left = q-p+1;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
delete [] L;
delete [] R;
}
void mergesort(int A[],int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
/*********************************
/**** Heap Sort Functions
/********************************/
void max_heapify(int i,int size)//size stands for heap size
{
int left = i<<1;
int right = left+1;
//get the largest of the i/left/right
int largest;
if((left<=size)&&(arr[left]>arr[i]))
{
largest = left;
}
else
largest = i;
if((right<=size)&&(arr[right]>arr[largest]))
largest = right;
//exchange the value of i and largest
if(i!=largest)
{
int temp =arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
max_heapify(largest,size);
}
}
void build_max_heap()
{
int size = sizeof(arr)/sizeof(arr[0])-1;
for(int i=size/2;i>0;i--)
max_heapify(i,size);
}
void heapsort()
{
build_max_heap();
int size = sizeof(arr)/sizeof(arr[0])-1;
//int heapsize = size;
for(int i=size;i>1;i--)
{
int temp = arr[1];
arr[1]=arr[i];
arr[i]=temp;
//heapsize--;
max_heapify(1,i-1);
}
}
/***********************************
/*********** Quick Sort
/*********************************/
int partition(int p,int r)
{
int i=p-1;
int pivot = arr[r];
for(int j=p;j<=r;j++)
{
if(arr[j]<pivot)
{
i++;
int temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
arr[r]=arr[i+1];
arr[i+1]=pivot;
return i+1;
}
void quicksort(int p,int r)
{
if(p<r)
{
int q = partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
int main(int argc,char* argv[])
{
int size = MAXSIZE;
for(int i=0;i<size;i++)
{
arr[i] = rand()%MAXSIZE;
}
print();
DWORD start = timeGetTime();
//mergesort(arr,0,MAXSIZE-1);
//heapsort();
quicksort(0,MAXSIZE-1);
DWORD end = timeGetTime();
print();
cout<<end-start<<endl;
system("pause");
return 0;
}