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

HUNANUIVERITY課程實(shí)驗(yàn)報(bào)告題目：快速排序 學(xué)生姓名學(xué)生學(xué)號(hào) 專(zhuān)業(yè)班級(jí) 指導(dǎo)老師 李曉鴻 一、需求分析1．程序的功能由用戶(hù)輸入任務(wù)件數(shù)和任務(wù)時(shí)間，使用快速排序，輸出使得所有任務(wù)等待時(shí)間最小的序列。2.輸入的形式本程序由用戶(hù)輸入任務(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í)間：534261573任務(wù)所花時(shí)間從小到大的排序如下：123345567請(qǐng)輸入任務(wù)總數(shù)：10請(qǐng)輸入各個(gè)任務(wù)所花時(shí)間：6512354861任務(wù)所花時(shí)間從小到大的排序如下：1123455668請(qǐng)輸入任務(wù)總數(shù)：6請(qǐng)輸入各個(gè)任務(wù)所花時(shí)間：10101945235任務(wù)所花時(shí)間從小到大的排序如下：51010192345請(qǐng)輸入任務(wù)總數(shù)：8請(qǐng)輸入各個(gè)任務(wù)所花時(shí)間：87654321任務(wù)所花時(shí)間從小到大的排序如下：12345678請(qǐng)輸入任務(wù)總數(shù)：10請(qǐng)輸入各個(gè)任務(wù)所花時(shí)間：24681012142615任務(wù)所花時(shí)間從小到大的排序如下：01246812141526二、概要設(shè)計(jì)1.抽象數(shù)據(jù)類(lèi)型將每一個(gè)元素儲(chǔ)存在一個(gè)有序并且有限的序列中，每一個(gè)元素都有一個(gè)自己的位置，也都有一個(gè)數(shù)據(jù)類(lèi)型，所以使用線(xiàn)性表來(lái)儲(chǔ)存各個(gè)任務(wù)所花的時(shí)間。ADTADTalist{數(shù)據(jù)對(duì)象：定義線(xiàn)性表的最大儲(chǔ)存元素maxsize;當(dāng)前儲(chǔ)存元素?cái)?shù)listsize;數(shù)據(jù)關(guān)系：若listsize=0,則線(xiàn)性表沒(méi)有元素，為空;基本操作：alist(intn)//構(gòu)造函數(shù)~alist()//析構(gòu)函數(shù) boolappend(inta)//增加元素}3.算法的基本思想設(shè)要排序的線(xiàn)性表中元素是A[0]……A[N-1]，首先通過(guò)時(shí)間函數(shù)余作為關(guān)鍵數(shù)據(jù)piot，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，通過(guò)前后指針的移動(dòng)，實(shí)現(xiàn)快速排序。再將piot值左右兩邊的線(xiàn)性表進(jìn)行快速排序，直到需要快速排序的線(xiàn)性表只有1個(gè)元素。4.程序基本流程程序分為三個(gè)模塊：輸入模塊：由用戶(hù)讀入任務(wù)總數(shù)n以及各個(gè)任務(wù)所花時(shí)間；排序模塊：對(duì)這些時(shí)間進(jìn)行快速排序；輸出模塊：輸出排序后的序列。三．詳細(xì)設(shè)計(jì)1.物理數(shù)據(jù)類(lèi)型由于線(xiàn)性表長(zhǎng)度已知，并且進(jìn)行大量的交換操作，所以使用順序表來(lái)實(shí)現(xiàn)。順序表的偽代碼classalist{public: intmaxsize; intlistsize; int*listarry; alist(intn) { maxsize=n; listsize=0; listarry=newint[maxsize]; } ~alist() { delete[]listarry; } boolappend(inta) { if(listsize==maxsize)returnfalse; listarry[listsize++]=a; returntrue; }};詳細(xì)設(shè)計(jì)獲取piot值——partation——quicksort獲取piot值：獲取隨機(jī)數(shù)，通過(guò)隨機(jī)數(shù)獲得piot值。為了防止隨機(jī)數(shù)大于所有數(shù)，對(duì)隨機(jī)數(shù)就行求余，對(duì)求余后的值加1（防止左邊界為0，右邊界為1的情況，（r+l）/2==0）.intfindpiot(inta,intb) { srand(time(0)); intn=rand()%((a+b)/2+1); returnn; }partation（劃分）：開(kāi)始參數(shù)l.r緊挨要分割子線(xiàn)性表的實(shí)際邊界。每一輪執(zhí)行外層do循環(huán)時(shí)，l和r都將向的線(xiàn)性表中間移動(dòng)，若在移動(dòng)過(guò)程中，l遇到比piot值大的值就停止，l遇到比piot小的就停止，交換l和r所對(duì)應(yīng)的值，再次移動(dòng)，直到它們交叉為止。intpartition(intl,intr,int&pivot) { do { while(listarry[++l]<pivot); while((r!=0)&&(listarry[--r]>pivot)); swap(l,r); }while(l<r); swap(l,r); returnl; }quicksort（快速排序）：通過(guò)遞歸，獲取piot值后，對(duì)線(xiàn)性表從位置i到位置j進(jìn)行一次劃分，通過(guò)k值獲得排序后poit值所在位置，對(duì)起始位置i到k和k+1到末尾j再次快速排序。 voidqsort(inti,intj) { if(j<=i) return; intpivotindex=findpiot(i,j); intk=partition(i-1,j,listarry[j]); swap(k,j); qsort(i,k-1); qsort(k+1,j); }算法的時(shí)空分析及改進(jìn)設(shè)想最好情況O（nlogn），最差情況（n^2）輸入和輸出的格式輸入：輸入任務(wù)數(shù)量，任務(wù)時(shí)間：請(qǐng)輸入任務(wù)數(shù):.....請(qǐng)輸入任務(wù)時(shí)間:......cout<<"輸入任務(wù)數(shù)\n"; cin>>n; alista(n); cout<<"輸入任務(wù)時(shí)間\n"; for(inti=0;i<n;i++) { cin>>temp; a.append(temp); }輸出：任務(wù)所花時(shí)間排序如下：.........cout<<"任務(wù)所花時(shí)間排序如下\n"; for(inti=0;i<n;i++) cout<<a.listarry[i]<<""; cout<<endl;測(cè)試結(jié)果測(cè)試1測(cè)試2測(cè)試3測(cè)試4測(cè)試5試驗(yàn)心得書(shū)上快速排序十分詳細(xì)，用抽象數(shù)據(jù)類(lèi)型做也就多了定義類(lèi)。附錄#include"iostream"#include"time.h"usingnamespacestd;classalist{public: intmaxsize; intlistsize; int*listarry; alist(intn) { maxsize=n; listsize=0; listarry=newint[maxsize]; } ~alist() { delete[]listarry; } boolappend(inta) { if(listsize==maxsize)returnfalse; listarry[listsize++]=a; returntrue; } intfindpiot(inta,intb) { srand(time(0)); intn=rand()%((a+b)/2); returnn; } intpartition(intl,intr,int&pivot) { do { while(listarry[++l]<pivot); while((r!=0)&&(listarry[--r]>pivot)); swap(l,r); }while(l<r); swap(l,r); returnl; } voidqsort(inti,intj) { if(j<=i) return; intpivotindex=findpiot(i,j); intk=partition(i-1,j,listarry[j]); swap(k,j); qsort(i,k-1); qsort(k+1,j); } voidswap(inta,intb) { inttemp; temp=listarry[a]; listarry[a]=listarry[b]; listarry[b]=temp; }};intmain(){ intn,temp; cout<<"輸入任務(wù)數(shù)\n"; cin>>n; alista(n); cout<<"輸入任務(wù)時(shí)間\n"; for(inti=0;i<n;