快速排序 以第一個元素為中軸 并測試1000000個整形元素的速度

#include<iostream>

#include<ctime>

using namespace std;

int Partition(int A[], int l, int r);

void QSort(int A[], int l, int r);

void QuickSort(int A[], int N)

{

 QSort(A, 0, N-1);

}

void QSort(int A[], int l, int r)

{

 if(l < r)

 {

  int pivot = Partition(A, l, r);

  QSort(A, l, pivot-1);

  QSort(A, pivot+1, r);

 }

}

int Partition(int A[], int l, int r)

{

 int pivot_key = A[l];

 while(l < r)

 {

  while(l < r && A[r] >= pivot_key) --r;

  A[l] = A[r];

  while(l < r && A[l] <= pivot_key) ++l;

  A[r] = A[l];

 }

 A[l] = pivot_key;

 return l;

}

int main()

{

 long const N = 1000000;

 int *A = new int[N];

 srand((unsigned)time(NULL));  //随機種子

 for(int i=0; i<N; i++)

 {

  A[i] = rand();  //産生随機數

 }

 clock_t start, finish, total_time; 

 start = clock();  //開始時間

 QuickSort(A,N);  //排序

 finish = clock();//結束時間

 total_time = finish - start;//計算時間差

 cout<<"Total time is: "<<total_time<<endl;

 cout<<endl;

 return 0;

}