#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;
}

快速排序