數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)八 快速排序?qū)嶒?yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程最終報(bào)告題 目：實(shí)驗(yàn)八快速排序?qū)I(yè)班級：計(jì)算機(jī)科學(xué)與技術(shù)姓 名：XXX學(xué) 號：指導(dǎo)老師： 李曉鴻完成日期：一、 需求分析背景排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。假設(shè)含n個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。排序算法是計(jì)算機(jī)科學(xué)中最重要的研究問題之一。對于排序的研究既有理論上的重要意義，又有實(shí)際應(yīng)用價(jià)值。它在

2、計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、模式識別、及統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛應(yīng)用。 常見的排序算法有起泡排序、直接插入排序、簡單選擇排序、快速排序、堆排序等。例1：有時(shí)候應(yīng)用程序本身就需要對信息進(jìn)行排序。為了準(zhǔn)備客戶賬目，銀行需要根據(jù)支票的號碼對支票排序；例2：在一個(gè)繪制互相重疊的圖形對象的程序中，可能需要根據(jù)一個(gè)“在上方”關(guān)系將各對象排序，以便自下而上地繪出對象。例3：在一個(gè)由n個(gè)數(shù)構(gòu)成的集合上，求集合中第i小/大的數(shù)。例4：對一個(gè)含有n個(gè)元數(shù)的集合，求解中位數(shù)、k分位數(shù)。1. 問題描述在操作系統(tǒng)中，我們總是希望以最短的時(shí)間處理完所有的任務(wù)。但事情總是要一件件地做，任務(wù)也要操作系統(tǒng)一件件地處理。當(dāng)操

3、作系統(tǒng)處理一件任務(wù)時(shí)，其他待處理的任務(wù)就需要等待。雖然所有任務(wù)的處理時(shí)間不能降低，但我們可以安排它們的處理順序，將耗時(shí)少的任務(wù)先處理，耗時(shí)多的任務(wù)后處理，這樣就可以使所有任務(wù)等待的時(shí)間和最小。只需要將n 件任務(wù)按用時(shí)去從小到大排序，就可以得到任務(wù)依次的處理順序。當(dāng)有 n 件任務(wù)同時(shí)來臨時(shí)，每件任務(wù)需要用時(shí)ni，求讓所有任務(wù)等待的時(shí)間和最小的任務(wù)處理順序。2. 程序要求實(shí)現(xiàn)的功能當(dāng)有 n 件任務(wù)同時(shí)來臨時(shí)，每件任務(wù)需要用時(shí)ni，求出讓所有任務(wù)等待的時(shí)間和最小的任務(wù)處理順序。3. 輸入輸出要求a) 輸入要求：第一行是一個(gè)整數(shù)n，代表任務(wù)的件數(shù)。接下來一行，有n個(gè)正整數(shù)，代表每件任務(wù)所用的時(shí)間。b)

4、 輸出要求：輸出有n行，每行一個(gè)正整數(shù)，從第一行到最后一行依次代表著操作系統(tǒng)要處理的任務(wù)所用的時(shí)間。按此順序進(jìn)行，則使得所有任務(wù)等待時(shí)間最小。4. 測試數(shù)據(jù)1. 輸入：請輸入任務(wù)件數(shù)：-1輸出： 輸入有誤，請重新輸入！2. 輸入： 請輸入任務(wù)件數(shù)：4 請輸入各任務(wù)所需時(shí)間：2 4 3 0輸出：輸入有誤，請重新輸入！3. 輸入：請輸入任務(wù)件數(shù)：4請輸入各任務(wù)所需時(shí)間：2 4 3 6輸出：任務(wù)執(zhí)行的先后順序?yàn)椋?2 3 4 64. 輸入： 請輸入任務(wù)件數(shù)：9 請輸入各任務(wù)所需時(shí)間：5 3 4 2 6 1 5 7 3輸出：任務(wù)執(zhí)行的先后順序?yàn)椋?23345567二、 概要設(shè)計(jì)(一) 函數(shù)調(diào)用關(guān)系圖主

5、函數(shù)void QuickSort(int a,int start,int end);void QuickSort(int a,int start,int end); int Partition(int a,int start,int end); int random(int start,int end) ;void change(int a,int i,int j); 三、 詳細(xì)設(shè)計(jì)（一）物理數(shù)據(jù)類型本程序所輸入的任務(wù)件數(shù)和任務(wù)時(shí)間均為整數(shù)，可使用整數(shù) int實(shí)現(xiàn)數(shù)據(jù)的存儲。使用數(shù)組實(shí)現(xiàn)快速排序。(二)具體步驟和偽代碼1. 輸入任務(wù)件數(shù)及任務(wù)時(shí)長 while(1)coutsize; while

6、(size) /任務(wù)件數(shù)大于0，則執(zhí)行該循環(huán)，否則重新輸入件數(shù)int i;cout請輸入各任務(wù)所需時(shí)間:; for(i=0;iai;if(ai=0)cout輸入有誤，請重新輸入！endl;break;if(i=size)break; cout輸入有誤，請重新輸入！=start) return t; 3. 數(shù)組中的兩個(gè)元素交換位置void change(int aN,int i,int j) int t; t=ai; ai=aj; aj=t; 4. 快速排序時(shí)對數(shù)據(jù)進(jìn)行劃分區(qū)域int Partition(int a,int start,int end) int temp=random(start

7、,end);/得到隨機(jī)軸值 change(a,temp,end);int i=start-1;/i用來指示軸值之后插入的位置int base=aend; /以最后一個(gè)數(shù)作為劃分的基點(diǎn)for(int j=start;jend;j+)if(aj=base)i+;change(a,i,j);change(a,i+1,end);return i+1; 5. 快速排序void QuickSort(int aN,int start,int end) if(end=start) return;/沒有數(shù)據(jù)或只有一個(gè)數(shù)據(jù) if(startend)/大于1個(gè)數(shù)據(jù) int i=Partition(a,start,e

8、nd); /劃分區(qū)域/對兩個(gè)區(qū)域分別進(jìn)行快排QuickSort(a,start,i-1); QuickSort(a,i+1,end); （三） 算法的具體步驟1) 通過用戶輸入任務(wù)件數(shù)n及任務(wù)時(shí)長，并對輸入合法性進(jìn)行驗(yàn)證；若合法，則進(jìn)行下一步，否則重新輸入；2) 通過調(diào)用random()函數(shù)，獲取非負(fù)且小于n的隨機(jī)數(shù)，該隨機(jī)數(shù)作為下標(biāo)所表示的元素作為軸值；3) 根據(jù)所得軸值，進(jìn)行快速排序。所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分割結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。原本數(shù)列被劃分為兩部分4) 遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。5) 遞歸的基例是數(shù)列的大小是零或一，此時(shí)排序完成輸出排序后的數(shù)列結(jié)果到界面。四、 輸入輸出格式輸入：a. 輸入任務(wù)件數(shù)coutsize;b. 輸入每件任務(wù)時(shí)長cout請輸入各任務(wù)所需時(shí)間:; for(i=0;iai;輸出：1、輸入不合法：if(size=0)cout輸入有誤，請重新輸入！endl;if(ai=0)cout輸入有誤，請重新輸入！endl;break;2、輸入合法