#include <iostream>

 #include <fstream>

 #include <cstdlib>

 #include <ctime>

 #include <algorithm>

 using namespace std;

 #define limit 100000

 void quicksort(int a[], int low ,int high)

 {

     if(low<high){                //递归的终止条件

         int i = low, j = high;   //使用i,j在对应区间内对数组进行排序；

         int x = a[low];          //将数组的第一个元素作为哨兵,通过这种方式取出哨兵元素

         while(i < j){

           while(i < j && a[j] >= x)

               j--;               //从右向左寻找第一个比哨兵元素小的元素

           if(i < j){

               a[i] = a[j];

               i++;               //把找到的第一个小于哨兵元素的元素值赋值给第一个元素，并把下界（i）向后移一位

           }

           while(i < j && a[i] <= x)

               i++;                //从左向右寻找第一个比哨兵元素大的元素

           if(i < j){

               a[j] = a[i];

               j--;

           }                       //把找到的第一个大于哨兵元素的元素值赋值给下标为j的元素，并把上界（j）向前移一位

         }

         a[i] = x;                 //把哨兵赋值到下标为i的位置，i前的元素均比哨兵元素小，i后的元素均比哨兵元素大

         quicksort(a, low ,i-);   //递归进行哨兵前后两部分元素排序

         quicksort(a, i+ ,high);

     }

 }

 int main(void)

 {

     ifstream fin;

     ofstream fout;

     int x;

     int i;

     int a[limit];

     fin.open("random_number.txt");

     if(!fin){

         cerr<<"Can not open file 'random_number.txt' "<<endl;

         return -;

     }

     time_t first, last;

     for(i=; i<limit; i++){

         fin>>a[i];

     }

     fin.close();

     first = clock();

     quicksort(a,,limit-);

     last = clock();

     fout.open("sort_number.txt");

     if(!fout){

         cerr<<"Can not open file 'sort_number.txt' "<<endl;

         return -;

     }

     for(i=; i<limit; i++){

         fout<<a[i]<<endl;

     }

     fout.close();

     cout<<"Sort completed (already output to file 'sort_number.txt')!"<<endl;

     cout<<"Time cost: "<<last-first<<endl;

     return ;

 }