#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
/*
* 交换两个数
*/
void exchange(unsigned int *p,unsigned int *q)
{
unsigned int temp;
temp=*p;
*p=*q;
*q=temp;
}
/*
* 快速排序
*
*/
unsigned int partition_sort(unsigned int array[],unsigned int start,unsigned int end);
unsigned int partition_sort_another(unsigned int array[],unsigned int start,unsigned int end);
unsigned int randomized_partition_sort(unsigned int array[],unsigned int start,unsigned int end);
void quicksort(unsigned int array[],unsigned int start,unsigned int end)
{
unsigned int cut;
if(start<end)
{
cut=randomized_partition_sort(array,start,end);
quicksort(array,start,cut-1);
quicksort(array,cut+1,end);
}
}
/*
* 随机化快速排序 算法导论版本
*/
unsigned int randomized_partition_sort(unsigned int array[],unsigned int start,unsigned int end)
{
unsigned int select_index=start+rand()%(end-start+1);
exchange(&array[select_index],&array[start]);
return partition_sort_another(array, start, end);
}
/*
* 快速排序 算法导论版本
*/
unsigned int partition_sort(unsigned int array[],unsigned int start,unsigned int end)
{
unsigned int pivot=array[end];
unsigned int index=start-1;
for(unsigned int i=start;i<end;i++)
{
if(array[i]<=pivot)
{
++index;
exchange(&array[index],&array[i]);
}
}
exchange(&array[index+1],&array[end]);
return index+1;
}
/*
* 快速排序 个人版本
*/
unsigned int partition_sort_another(unsigned int array[],unsigned int start,unsigned int end)
{
unsigned int pivot=array[start];
unsigned int index=start;
for(unsigned int i=start+1;i<=end;i++)
{
if(array[i]<=pivot)
{
++index;
exchange(&array[index],&array[i]);
}
}
exchange(&array[index],&array[start]);
return index;
}
void PrintArray(unsigned int array[],unsigned int length)
{
for(unsigned int i=0;i<length;i++)
{
cout<<array[i]<<"\t";
}
cout<<endl;
}
void initial_array(unsigned int array[],unsigned int length)
{
for(unsigned int i=0;i<length;i++)
array[i]=rand();
}
int main()
{
unsigned int length=900000;
unsigned int array[length];
clock_t start, finish;
double duration;
//int array[10]={10,3,8,2,78,34,9,28,7,43};
initial_array(array,length);
//cout << "排序前 数组元素的排列:" << endl;
//PrintArray(array,length);
//cout << "排序后 数组元素的排列:" << endl;
start = clock();
quicksort(array,0,length-1);
finish = clock();
duration = (double)(finish-start)/CLOCKS_PER_SEC;
cout<<duration<<" seconds duration!";
// PrintArray( array,length);
//cout << "Hello world!" << endl;
return 0;
}