C++分治策略實現快速排序

代碼實現了利用遞歸對數組進行快速排序，其中limit為從已有的隨機數文件中輸入的所要進行排序的數據的數量（生成隨機數並寫入文件的過程已在前篇中寫出）。

演算法主要利用哨兵元素對數據進行分塊，遞歸無限細分之後實現排序。

代碼同樣利用clock函數對演算法的執行時間進行計算以進行演算法的效率評估。

為了驗證排序結果，代碼實現了將排序後的內容輸出到同文件夾下的sort_number.txt文件中。

 1 #include <iostream>
 2 #include <fstream>
 3 #include <cstdlib>
 4 #include <ctime>
 5 #include <algorithm>
 6 using namespace std;
 7 #define limit 100000
 8 
 9 void quicksort(int a[], int low ,int high)
10 {
11     if(low<high){                //遞歸的終止條件
12         int i = low, j = high;   //使用i,j在對應區間內對數組進行排序；
13         int x = a[low];          //將數組的第一個元素作為哨兵,通過這種方式取出哨兵元素
14 
15         while(i < j){
16           while(i < j && a[j] >= x)
17               j--;               //從右向左尋找第一個比哨兵元素小的元素
18           if(i < j){
19               a[i] = a[j];
20               i++;               //把找到的第一個小於哨兵元素的元素值賦值給第一個元素，並把下界（i）向後移一位
21           }
22 
23           while(i < j && a[i] <= x)
24               i++;                //從左向右尋找第一個比哨兵元素大的元素
25           if(i < j){
26               a[j] = a[i];
27               j--;
28           }                       //把找到的第一個大於哨兵元素的元素值賦值給下標為j的元素，並把上界（j）向前移一位
29         }
30         a[i] = x;                 //把哨兵賦值到下標為i的位置，i前的元素均比哨兵元素小，i後的元素均比哨兵元素大
31 
32         quicksort(a, low ,i-1);   //遞歸進行哨兵前後兩部分元素排序
33         quicksort(a, i+1 ,high);
34     }
35 }
36 int main(void)
37 {
38     ifstream fin;
39     ofstream fout;
40     int x;
41     int i;
42     int a[limit];
43 
44     fin.open("random_number.txt");
45     if(!fin){
46         cerr<<"Can not open file 'random_number.txt' "<<endl;
47         return -1;
48     }
49     time_t first, last;
50 
51 
52     for(i=0; i<limit; i++){
53         fin>>a[i];
54     }
55     fin.close();
56 
57     first = clock();
58 
59     quicksort(a,0,limit-1);
60 
61     last = clock();
62 
63     fout.open("sort_number.txt");
64 
65     if(!fout){
66         cerr<<"Can not open file 'sort_number.txt' "<<endl;
67         return -1;
68     }
69     for(i=0; i<limit; i++){
70         fout<<a[i]<<endl;
71     }
72 
73     fout.close();
74 
75     cout<<"Sort completed (already output to file 'sort_number.txt')!"<<endl;
76     cout<<"Time cost: "<<last-first<<endl;
77 
78     return 0;
79 }