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

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

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

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

4、0AN-1，首先通過(guò)時(shí)間函數(shù)余作為關(guān)鍵數(shù)據(jù)piot，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，通過(guò)前后指針的移動(dòng)，實(shí)現(xiàn)快速排序。再將piot值左右兩邊的線性表進(jìn)行快速排序，直到需要快速排序的線性表只有1個(gè)元素。4.程序基本流程程序分為三個(gè)模塊：輸入模塊：由用戶讀入任務(wù)總數(shù)n以及各個(gè)任務(wù)所花時(shí)間；排序模塊：對(duì)這些時(shí)間進(jìn)行快速排序；輸出模塊：輸出排序后的序列。三詳細(xì)設(shè)計(jì)1.物理數(shù)據(jù)類型由于線性表長(zhǎng)度已知，并且進(jìn)行大量的交換操作，所以使用順序表來(lái)實(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è)計(jì)獲取piot值partationquicksort獲取piot值：獲取隨機(jī)數(shù)，通過(guò)隨機(jī)數(shù)獲得piot值。為了防止隨機(jī)數(shù)大于所有數(shù)，對(duì)隨機(jī)數(shù)就行求余，對(duì)求余后的值加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（劃分）：開(kāi)始參數(shù)l.r緊挨要分割子線性表的實(shí)際邊界。每一輪執(zhí)行外層do循環(huán)時(shí)，l和r都將向的線性表中間移動(dòng)，若在移動(dòng)過(guò)程中，l遇到比piot值大的值就停止，l遇到比piot小的就停止，交換l和r所對(duì)應(yīng)的值，再次移動(dò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（快速排序）：通過(guò)遞歸，獲取piot值后，對(duì)線性表從位置i到位置j進(jìn)行一次劃分，通過(guò)k值獲得排序后poit值所在位置，對(duì)起始位置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 算法的時(shí)空分析及改進(jìn)設(shè)想 最好情況O（nlogn），最差情況（n2）4. 輸入和

8、輸出的格式輸入： 輸入任務(wù)數(shù)量，任務(wù)時(shí)間：請(qǐng)輸入任務(wù)數(shù): .請(qǐng)輸入任務(wù)時(shí)間: .cout n;alist a(n);cout 輸入任務(wù)時(shí)間n;for (int i = 0; i temp;a.append(temp);輸出：任務(wù)所花時(shí)間排序如下：.cout 任務(wù)所花時(shí)間排序如下n;for (int i = 0; i n; i+)cout a.listarryi ;cout endl;4 測(cè)試結(jié)果測(cè)試1測(cè)試2測(cè)試3測(cè)試4測(cè)試55 試驗(yàn)心得書上快速排序十分詳細(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 輸入任