實(shí)驗(yàn)八 快速排序.doc

HUNAN UNIVERSITY課程預(yù)習(xí)報(bào)告題 目： 快速排序 學(xué)生姓名 學(xué)生學(xué)號 2012080102 專業(yè)班級 計(jì)算機(jī)科學(xué)與技術(shù)班 完 成 日 期 4 一、需求分析輸入的形式和輸入值的范圍：第一行是一個(gè)整數(shù)n，代表任務(wù)的件數(shù)。接下來一行，有n個(gè)正整數(shù)，代表每件任務(wù)所用的時(shí)間。中間用空格或者回車隔開。不對非法輸入做處理，及假設(shè)用戶輸入都是合法的。輸出的形式：輸出有n行，每行一個(gè)正整數(shù)，從第一行到最后一行依次代表著操作系統(tǒng)要處理的任務(wù)所用的時(shí)間。按此順序進(jìn)行，則使得所有任務(wù)等待時(shí)間最小。程序所能達(dá)到的功能：在操作系統(tǒng)中，當(dāng)有 n 件任務(wù)同時(shí)來臨時(shí)，每件任務(wù)需要用時(shí)ni，輸出所有任務(wù)等待的時(shí)間和最小的任務(wù)處理順序。測試數(shù)據(jù)：輸入請輸入任務(wù)個(gè)數(shù)：9請輸入任務(wù)用時(shí)：5 3 4 2 6 1 5 7 3輸出任務(wù)執(zhí)行的順序：1 2 3 3 4 5 5 6 7二、概要設(shè)計(jì)抽象數(shù)據(jù)類型為實(shí)現(xiàn)上述程序的功能，應(yīng)以整數(shù)存儲用戶的第一個(gè)輸入。并將隨后輸入的一組數(shù)據(jù)儲存在整數(shù)數(shù)組中。算法的基本思想如果將任務(wù)按完成時(shí)間從小到大排序，則在完成前一項(xiàng)任務(wù)時(shí)后面任務(wù)等待的時(shí)間總和最小，即得到最小的任務(wù)處理順序。采取對輸入的任務(wù)時(shí)間進(jìn)行快速排序的方法可以在相對較小的時(shí)間復(fù)雜度下得到從小到大的順序序列。三、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型：第一次輸入的正整數(shù)要求大于零，為了能夠存儲，采用int型定義變量。接下來輸入的一組整數(shù)，數(shù)據(jù)范圍大于零，為了排序需要，采用線性結(jié)構(gòu)存儲，即int類型的數(shù)組。實(shí)現(xiàn)程序的具體步驟：程序主要采取快速排序的方法處理無序數(shù)列：1在序列中根據(jù)隨機(jī)數(shù)確定軸值，根據(jù)軸值將序列劃分為比軸值小和比軸值大的兩個(gè)子序列。2對每個(gè)子序列采取從左右兩邊向中間搜索的方式，不斷將值與軸值比較，如果左邊的值大于軸值而右邊的小于軸值則將二者交換，直到左右交叉。3分別對處理完畢的兩個(gè)子序列遞歸地采取1，2步的操作，直到子序列中只有一個(gè)元素。程序各模塊的偽代碼：主函數(shù)int main() int n; coutn; int an; cout請輸入任務(wù)用時(shí)：; for(int i=0;iai; qsort(a,0,n-1);/調(diào)用“快排函數(shù)” cout任務(wù)執(zhí)行的順序：; for(int i=0;in;i+)coutai ; /輸出排序結(jié)果快速排序算法：void qsort(int a,int i,int j) if(j=i)return;/只有一個(gè)元素 int pivotindex=findpivot(a,i,j);/調(diào)用“軸值尋找函數(shù)”確定軸值 swap(a,pivotindex,j);/調(diào)用“交換函數(shù)”將軸值置末 int k=partition(a,i-1,j,aj);/調(diào)用“分割函數(shù)”根據(jù)軸值分割序列 swap(a,k,j); qsort(a,i,k-1);/遞歸調(diào)用，實(shí)現(xiàn)子序列的調(diào)序 qsort(a,k+1,j); 軸值尋找算法：/為了保證軸值的“隨機(jī)性”，采用時(shí)間初始化種子。int findpivot(int a,int i,int j) srand(unsigned int)time(NULL); int n=rand()%(j-i+1)+i; /返回傳入范圍內(nèi)的軸值 數(shù)據(jù)交換算法：void swap(int a,int i,int j) int temp; temp=ai; ai=aj; aj=temp; 序列分割算法：int partition(int a,int l,int r,int &pivot) do while(a+lpivot); swap(a,l,r); while(lr); swap(a,l,r); return l;/返回右邊部分的首位置 算法的時(shí)空分析對于長度為n的序列，進(jìn)行快速排序的效率取決于對主值的選擇。隨機(jī)化快速排序雖然在最壞情況下的時(shí)間復(fù)雜度仍然是O(n2），但是隨機(jī)數(shù)取值不佳的概率比較低，所以大部分能夠達(dá)到O(nlogn）的時(shí)間復(fù)雜度。另輸入輸出的時(shí)間復(fù)雜度為（n）。所以該算法的時(shí)間復(fù)雜度為O(nlogn）。函數(shù)的調(diào)用關(guān)系圖輸入Findpivot 確定軸值Swap 交換快排主函數(shù)Pa