數(shù)據(jù)結(jié)構(gòu)實(shí)驗八：快速排序

1、HUNAN UNIVERSITY課程實(shí)驗報告題 目： 快速排序 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 李 曉 鴻 完 成 日 期 2 0 1 5年 1月 7日 一、需求分析1程序的功能由用戶輸入任務(wù)件數(shù)和任務(wù)時間，使用快速排序，輸出使得所有任務(wù)等待時間最小的序列。2.輸入的形式本程序由用戶輸入任務(wù)總數(shù)以及每個任務(wù)所花時間，中間用空格或換行隔開，任務(wù)總數(shù)必須為正整數(shù)。請輸入任務(wù)總數(shù)：請輸入各個任務(wù)所花時間：3.輸出形式在對這些任務(wù)所花時間進(jìn)行快速排序后，將這些數(shù)據(jù)從小到大輸出任務(wù)時間。任務(wù)所花時間的排序如下：4.測試數(shù)據(jù)1.請輸入任務(wù)總數(shù)：9請輸入各個任務(wù)所花時間：5 3 4 2 6 1 5

2、7 3任務(wù)所花時間從小到大的排序如下：1 2 3 3 4 5 5 6 7 2. 請輸入任務(wù)總數(shù)： 10請輸入各個任務(wù)所花時間：6 5 1 2 3 5 4 8 6 1 任務(wù)所花時間從小到大的排序如下：1 1 2 3 4 5 5 6 6 83. 請輸入任務(wù)總數(shù)：6請輸入各個任務(wù)所花時間：10 10 19 45 23 5 任務(wù)所花時間從小到大的排序如下：5 10 10 19 23 454. 請輸入任務(wù)總數(shù)： 8請輸入各個任務(wù)所花時間：8 7 6 5 4 3 2 1任務(wù)所花時間從小到大的排序如下： 1 2 3 4 5 6 7 85. 請輸入任務(wù)總數(shù)： 10請輸入各個任務(wù)所花時間：2 4 6 8 1 0

3、 12 14 26 15任務(wù)所花時間從小到大的排序如下：0 1 2 4 6 8 12 14 15 26二、概要設(shè)計1.抽象數(shù)據(jù)類型將每一個元素儲存在一個有序并且有限的序列中，每一個元素都有一個自己的位置，也都有一個數(shù)據(jù)類型，所以使用線性表來儲存各個任務(wù)所花的時間。2. ADTADT alist數(shù)據(jù)對象：定義線性表的最大儲存元素maxsize; 當(dāng)前儲存元素數(shù)listsize;數(shù)據(jù)關(guān)系：若listsize=0,則線性表沒有元素，為空;基本操作：alist(int n)/構(gòu)造函數(shù) alist()/析構(gòu)函數(shù) bool append(int a)/增加元素3.算法的基本思想 設(shè)要排序的線性表中元素是A

4、0AN-1，首先通過時間函數(shù)余作為關(guān)鍵數(shù)據(jù)piot，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，通過前后指針的移動，實(shí)現(xiàn)快速排序。再將piot值左右兩邊的線性表進(jìn)行快速排序，直到需要快速排序的線性表只有1個元素。4.程序基本流程程序分為三個模塊：輸入模塊：由用戶讀入任務(wù)總數(shù)n以及各個任務(wù)所花時間；排序模塊：對這些時間進(jìn)行快速排序；輸出模塊：輸出排序后的序列。三詳細(xì)設(shè)計1.物理數(shù)據(jù)類型由于線性表長度已知，并且進(jìn)行大量的交換操作，所以使用順序表來實(shí)現(xiàn)。順序表的偽代碼class alistpublic:int maxsize;int listsize;int* listarry;a

5、list(int n)maxsize = n;listsize = 0;listarry = new intmaxsize;alist()deletelistarry;bool append(int a)if (listsize = maxsize)return false;listarrylistsize+ = a;return true;2. 詳細(xì)設(shè)計獲取piot值partationquicksort獲取piot值：獲取隨機(jī)數(shù)，通過隨機(jī)數(shù)獲得piot值。為了防止隨機(jī)數(shù)大于所有數(shù)，對隨機(jī)數(shù)就行求余，對求余后的值加1（防止左邊界為0，右邊界為1的情況，（r+l）/2=0）.int findpi

6、ot(int a, int b)srand(time(0);int n = rand() % (a+b)/2+1);return n;partation（劃分）：開始參數(shù)l.r緊挨要分割子線性表的實(shí)際邊界。每一輪執(zhí)行外層do循環(huán)時，l和r都將向的線性表中間移動，若在移動過程中，l遇到比piot值大的值就停止，l遇到比piot小的就停止，交換l和r所對應(yīng)的值，再次移動，直到它們交叉為止。int partition(int l, int r, int &pivot)dowhile (listarry+l pivot);swap( l, r); while (l r);swap( l, r);ret

7、urn l; quicksort（快速排序）：通過遞歸，獲取piot值后，對線性表從位置i到位置j進(jìn)行一次劃分，通過k值獲得排序后poit值所在位置，對起始位置i到k和k+1到末尾j再次快速排序。void qsort( int i, int j)if (j = i)return;int pivotindex = findpiot( i, j);int k = partition(i - 1, j, listarryj);swap( k, j);qsort( i, k - 1);qsort( k + 1, j);3 算法的時空分析及改進(jìn)設(shè)想 最好情況O（nlogn），最差情況（n2）4. 輸入和

8、輸出的格式輸入： 輸入任務(wù)數(shù)量，任務(wù)時間：請輸入任務(wù)數(shù): .請輸入任務(wù)時間: .cout n;alist a(n);cout 輸入任務(wù)時間n;for (int i = 0; i temp;a.append(temp);輸出：任務(wù)所花時間排序如下：.cout 任務(wù)所花時間排序如下n;for (int i = 0; i n; i+)cout a.listarryi ;cout endl;4 測試結(jié)果測試1測試2測試3測試4測試55 試驗心得書上快速排序十分詳細(xì)，用抽象數(shù)據(jù)類型做也就多了定義類。6 附錄#includeiostream#includetime.husing namespace std

9、;class alistpublic:int maxsize;int listsize;int* listarry;alist(int n)maxsize = n;listsize = 0;listarry = new intmaxsize;alist()deletelistarry;bool append(int a)if (listsize = maxsize)return false;listarrylistsize+ = a;return true;int findpiot(int a, int b)srand(time(0);int n = rand() % (a+b)/2);ret

10、urn n;int partition(int l, int r, int &pivot)dowhile (listarry+l pivot);swap( l, r); while (l r);swap( l, r);return l;void qsort( int i, int j)if (j = i)return;int pivotindex = findpiot( i, j);int k = partition(i - 1, j, listarryj);swap( k, j);qsort( i, k - 1);qsort( k + 1, j);void swap( int a, int b)int temp;temp = listarrya;listarrya = listarryb;listarryb = temp;int main()int n,temp;cout n;alist a(n);cout 輸入任