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

hunanuniversIty課程實驗報告題目:快速排序?qū)W生姓名學(xué)生學(xué)號專業(yè)班級指導(dǎo)老師李曉鴻完成日期201年1月7日一、需求分析.程序的功能由用戶輸入任務(wù)件數(shù)和任務(wù)時間，使用快速排序，輸出使得所有任務(wù)等待時間最小的序列。輸入的形式本程序由用戶輸入任務(wù)總數(shù)以及每個任務(wù)所花時間，中間用空格或換行隔開，任務(wù)總數(shù)必須為正整數(shù)。請輸入任務(wù)總數(shù)：請輸入各個任務(wù)所花時間：輸出形式在對這些任務(wù)所花時間進行快速排序后，將這些數(shù)據(jù)從小到大輸出任務(wù)時間。任務(wù)所花時間的排序如下：測試數(shù)據(jù)請輸入任務(wù)總數(shù)：9請輸入各個任務(wù)所花時間：534261573任務(wù)所花時間從小到大的排序如下:123345567請輸入任務(wù)總數(shù)：10請輸入各個任務(wù)所花時間：6512354861任務(wù)所花時間從小到大的排序如下:1123455668請輸入任務(wù)總數(shù)：6請輸入各個任務(wù)所花時間：10101945235任務(wù)所花時間從小到大的排序如下:51010192345請輸入任務(wù)總數(shù)：8請輸入各個任務(wù)所花時間：87654321任務(wù)所花時間從小到大的排序如下:請輸入任務(wù)總數(shù):10請輸入各個任務(wù)所花時間：4681012142615任務(wù)所花時間從小到大的排序如下：01246812141526二、概要設(shè)計抽象數(shù)據(jù)類型將每一個元素儲存在一個有序并且有限的序列中，每一個元素都有一個自己的位置，也都有一個數(shù)據(jù)類型，所以使用線性表來儲存各個任務(wù)所花的時間。ADTADTalist{數(shù)據(jù)對象：定義線性表的最大儲存元素maxsize;當前儲存元素數(shù)listsize;數(shù)據(jù)關(guān)系：若listsize=0,則線性表沒有元素，為空；基本操作：alist(intn)//構(gòu)造函數(shù)~alist()//析構(gòu)函數(shù)boolappend(inta)//增加元素算法的基本思想設(shè)要排序的線性表中元素是A[0]……A[N-1]，首先通過時間函數(shù)余作為關(guān)鍵數(shù)據(jù)piot，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，通過前后指針的移動，實現(xiàn)快速排序。再將piot值左右兩邊的線性表進行快速排序，直到需要快速排序的線性表只有1個元素。程序基本流程程序分為三個模塊：輸入模塊：由用戶讀入任務(wù)總數(shù)n以及各個任務(wù)所花時間；排序模塊：對這些時間進行快速排序；輸出模塊：輸出排序后的序列。詳細設(shè)計物理數(shù)據(jù)類型由于線性表長度已知，并且進行大量的交換操作，所以使用順序表來實現(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;}};詳細設(shè)計獲取piot值partationquicksort獲取piot值：獲取隨機數(shù)，通過隨機數(shù)獲得piot值。為了防止隨機數(shù)大于所有數(shù)，對隨機數(shù)就行求余，對求余后的值加1(防止左邊界為0，右邊界為1的情況，(r+l)/2==0).intfindpiot(inta,intb){srand(time(0));intn=rand()%((a+b)/2+1);returnn;}partation(劃分)：開始參數(shù)l.r緊挨要分割子線性表的實際邊界。每一輪執(zhí)行外層do循環(huán)時，l和r都將向的線性表中間移動，若在移動過程中，l遇到比piot值大的值就停止，l遇到比piot小的就停止，交換l和r所對應(yī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(快速排序):通過遞歸，獲取piot值后，對線性表從位置i到位置j進行一次劃分，通過k值獲得排序后poit值所在位置，對起始位置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è)想最好情況O(nlogn)，最差情況(nA2)4.輸入和輸出的格式輸入：輸入任務(wù)數(shù)量，任務(wù)時間：請輸入任務(wù)數(shù)：.....請輸入任務(wù)時間:cout<<"輸入任務(wù)數(shù)\n";cin>>n;alista(n);cout<<"輸入任務(wù)時間\n";for(inti=0;i<n;i++){cin>>temp;a.append(temp);}輸出：任務(wù)所花時間排序如下：cout<<"任務(wù)所花時間排序如下\n";for(inti=0;i<n;i++)cout<<a.listarry[i]<<"";cout<<endl;四.測試結(jié)果測試1E;\myc^SSSSVProject1\Debug\Project1.exe情輸/J壬務(wù)的件教；怙輸入各個任務(wù)的時間：5342E：i1573|壬務(wù)等待時間最小的排序：123345567臘按任意鑲催象■-.測試3■JE:\my試驗8\自己寫\Debu必自己寫.次巳■J輸入任務(wù)數(shù)6俞入任務(wù)時間10101945235任務(wù)所花時間排序如下51010192345請按任意鍵繼續(xù).?.挫狗拼音輸入法全：測試4*E:\myc—試驗8\自己寫\D巳bug\自己寫.次巳輸i入任務(wù)數(shù)8輸入任務(wù)時間87654321任務(wù)所花時間排序如下12345678請按任意鍵繼續(xù)?..測試5試驗心得書上快速排序十分詳細，用抽象數(shù)據(jù)類型做也就多了定義類。附錄#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ù)時間\n";