問題描述：
給定一個未知順序的n個元素組成的陣列，現要利用快速排序演算法對這n個元素進行非遞減排序，
細節須知：
（1）代碼實作了利用遞回對陣列進行快速排序，其中limit為從已有的亂數檔案中輸入的所要進行排序的資料的數量（生成亂數并寫入檔案的程序已在前篇中寫出），
（2）演算法主要利用哨兵元素對資料進行分塊，遞回無限細分之后實作排序，
（3）代碼同樣利用clock函式對演算法的執行時間進行計算以進行演算法的效率評估，
（4）為了驗證排序結果，代碼實作了將排序后的內容輸出到同檔案夾下的sort_number.txt檔案中，
演算法原理：
它的完成程序主要是將陣列分解為兩部分，然后分別對每一部分排序，在劃分陣列時，是將所有小于某個哨兵元素的專案放到該專案之前，將所有大于該哨兵元素的專案放到該專案之后，哨兵元素可以是任意專案，為方便起見，通常直接選擇第一個專案，因而可以總結為三步：（1）分解；（2）遞回求解；（3）合并，其中，演算法的核心部分為對陣列進行劃分，將小于x的元素放在原陣列的左半部分，將大于x的元素放在原陣列的右半部分，
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 }
程式設計思路：
（1）分解：以a[p]為基準元素將a[p：r]劃分成3段a[p：q-1]，a[q]和a[q+1：r]，使得a[p：q-1]中任何元素小于等于a[q]，a[q+1：r]中任何元素大于等于a[q]，下標q在劃分程序中確定，
（2）遞回求解：通過遞回呼叫快速排序演算法，分別對a[p：q-1]和a[q+1：r]進行排序，
（3）合并：由于對a[p：q-1]和a[q+1：r]的排序是就地進行的，所以在a[p：q-1]和a[q+1：r]都已排好序后不需要執行任何計算，a[p：r]就已排好序，
結果資料格式為time_t格式相減得到的長整型以及輸出到檔案的整形資料，
時間復雜性分析：
對于輸入序列a[p:r],演算法的計算時間顯然為O（r-p-1）.
快速排序的運行時間與劃分是否對稱有關，其最壞情況發生在劃分程序中產生的兩個區域分別包含n-1個元素和1個元素的時候，由于演算法的計算時間為O（n），所以如果演算法的每一步都出現這種不對稱劃分，則其計算時間復雜性T（n）滿足
T（n）= O（1），n≤1
T（n）= T（n-1）+O（n），n＞1
解此遞回方程可得T（n）=O（n2），
在最好情況下，每次劃分所取的基準都恰好為中值，即每次劃分都產生兩個大小為n/2的區域，此時，演算法的計算時間T（n）滿足
T（n）= O（1），n≤1
T（n）= 2T（n/2）+O（n），n＞1
其解為T（n）=O（nlogn），
可以證明，快速排序演算法在平均情況下的時間復雜性也是O（nlogn），
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100183.html
標籤：C++
上一篇：背包問題
下一篇：交換排序