算法排序問題實驗報告_第1頁
算法排序問題實驗報告_第2頁
算法排序問題實驗報告_第3頁
算法排序問題實驗報告_第4頁
算法排序問題實驗報告_第5頁
已閱讀5頁,還剩6頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、排序問題求解實驗報告1、 算法的基本思想1、直接插入排序算法思想 直接插入排序的基本思想是將一個記錄插入到已排好序的序列中,從而得到一個新的,記錄數(shù)增 1 的有序序列。 直接插入排序算法的偽代碼稱為 InsertionSort,它的參數(shù)是一個數(shù)組 A1.n,包含了 n個待排序的數(shù)。用偽代碼表示直接插入排序算法如下:InsertionSort (A)for i2 to ndo keyAi /key 表示待插入數(shù)/Insert Ai into the sorted sequence A1.i-1ji-1while j0 and Ajkeydo Aj+1Ajjj-1Aj+1key2、 快速排序算法思

2、想 快速排序算法的基本思想是,通過一趟排序?qū)⒋判蛐蛄蟹指畛瑟毩⒌膬刹糠?,其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小,則可對這兩部分記錄繼續(xù)進(jìn)行排序,以達(dá)到整個序列有序。 假設(shè)待排序序列為數(shù)組 A1.n,首先選取第一個數(shù) A0,作為樞軸(pivot),然后按照下述原則重新排列其余數(shù):將所有比 A0大的數(shù)都排在它的位置之前,將所有比 A0小的數(shù)都排在它的位置之后,由此以 A0最后所在的位置 i 作為分界線,將數(shù)組 A1.n分成兩個子數(shù)組 A1.i-1和 Ai+1.n。這個過程稱作一趟快速排序。通過遞歸調(diào)用快速排序,對子數(shù)組A1.i-1和 Ai+1.n排序。 一趟快速排序算法的偽代碼稱為 P

3、artition,它的參數(shù)是一個數(shù)組 A1.n和兩個指針 low、high,設(shè)樞軸為 pivotkey,則首先從 high 所指位置起向前搜索,找到第一個小于pivotkey 的數(shù),并將其移到低端,然后從 low 所指位置起向后搜索,找到第一個大于 pivotkey 的數(shù),并將其移到高端,重復(fù)這兩步直至 low=high。最后,將樞軸移到正確的位置上。用偽代碼表示一趟快速排序算法如下:Partition ( A, low, high)A0Alow/用數(shù)組的第一個記錄做樞軸記錄privotkeyAlow/樞軸記錄關(guān)鍵字while lowhigh /從表的兩端交替地向中間掃描while low=p

4、rivotkey do highhigh-1AlowAhigh /將比樞軸記錄小的記錄移到低端while lowhigh & Alow=pivotkey) do lowlow+1AhighAlow /將比樞軸記錄大的記錄移到高端AlowA0 /樞軸記錄到位return low /返回樞軸位置2、 算法的理論分析1. 直接插入排序算法理論分析從空間來看,直接插入排序只需要一個數(shù)的輔助空間;從時間來看,直接插入排序的基本操作為:比較兩個關(guān)鍵字的大小和移動記錄。先分析一趟直接插入排序的情況。偽代碼InsertionSort 中 while 循環(huán)的次數(shù)取決于待插入的數(shù)與前 i-1 個數(shù)之間的關(guān)系。若

5、AiA0,則在 while 循環(huán)中,待插入數(shù)需與有序數(shù)組 A1.i-1中 i-1 個數(shù)進(jìn)行比較,并將 Ai-1中 i-1 個數(shù)后移。則在整個排序過程(進(jìn)行 n-1 趟插入排序)中,當(dāng)待排序數(shù)組中數(shù)按非遞減有序排列時,則需進(jìn)行數(shù)間比較次數(shù)達(dá)最小值 n-1,數(shù)不需要移動;反之,當(dāng)待排序數(shù)組中數(shù)按非遞增有序排列時,總的比較次數(shù)達(dá)最大值(n+2)(n-1)/2,數(shù)移動的次數(shù)也達(dá)到最大值(n+4)(n-1)/2。若待排序數(shù)組是隨機(jī)的,即待排序數(shù)組中的數(shù)可能出現(xiàn)的各種排序的概率相同,則我們可取上述最小值和最大值的平均值,作為直接插入排序時所需進(jìn)行數(shù)間的比較次數(shù)和數(shù)的移動次數(shù),約為 n2/4。因此直接插入排

6、序算法,在最佳情況下的時間復(fù)雜度是 O(n),在最壞情況下的時間復(fù)雜度為 O(n2)。2. 快速排序算法理論分析下面我們來分析快速排序的平均時間性能。 假設(shè) T(n)為對 n 個記錄 A1.n進(jìn)行快速排序所需時間,則由算法 QuickSort 可見:其中,Tpass(n)為對 n 個記錄進(jìn)行一趟快速排序 Partition(A,1,n)所需的時間,從一趟快速排序算法可見,其和記錄數(shù) n 成正比,可以用 cn 表示(c 為某個常數(shù));T(k-1)和 T(n-k)分別為對 A1.k-1和 Ak+1.n中記錄進(jìn)行快速排序 QuickSort(A,1,k-1)和QuickSort(A,k+1,n)所需

7、時間。假設(shè)待排序列中記錄是隨機(jī)排列的,則在一趟排序之后,k 取 1 至 n 之間任何一值的概率相同,快速排序所需時間的平均值則為Tavg(n)=knInn,其中 n 為待排序序列中記錄的個數(shù),k 為某個常數(shù)。 通常,快速排序被認(rèn)為是,在所有同數(shù)量級(O(nlogn))的排序方法中,其平均性能最好。但是,若初始記錄序列按關(guān)鍵字有序或基本有序時,快速排序?qū)⑼懟癁槠鹋菖判?,其時間復(fù)雜度為 O(n2)。3、 試驗分析1、 試驗環(huán)境WIN 32系統(tǒng),VC6.02、 程序的執(zhí)行1)由函數(shù) datagenetare()生成 20000 個在區(qū)間1,100000上的隨機(jī)整數(shù),并將隨機(jī)整數(shù)保存到數(shù)組 num,接

8、著調(diào)用函數(shù) WriteFile()將這些數(shù)輸出到外部文件 data.txt 中。2)調(diào)用函數(shù) ReadFile()從 data.txt 中讀取數(shù)據(jù),并將其保存到數(shù)組 num1中。接著對數(shù)組 num1 進(jìn)行直接插入排序,并計算和記錄其運行時間。最后,調(diào)用函數(shù) WriteFile()將直接插入排序的結(jié)果寫入 resultsIS.txt,并記錄運行時間為 TimeIS。3)調(diào)用函數(shù) ReadFile()從 data.txt 中讀取數(shù)據(jù),并將其保存到數(shù)組 num2中。接著對數(shù)組 num2 進(jìn)行快速排序,并計算和記錄其運行時間。最后,調(diào)用函數(shù) WriteFile()將快速排序的結(jié)果寫入 resultsQ

9、S.txt,并記錄運行時間為 TimeQS。3、 試驗數(shù)據(jù)當(dāng)N=20000時:當(dāng)N=30000時:當(dāng)N=40000時:當(dāng)N=50000時:當(dāng)N=60000時:當(dāng)N=70000時:當(dāng)N=80000時:4、 實驗結(jié)果分析20000300004000050000600007000080000插入排序0.3250.7191.3972.1993.054.5715.46快速排序0.0030.0050.0080.010.0120.0110.013做出折線統(tǒng)計圖4、 試驗心得通過本次試驗首先對在C+下的文件操作有了一定的深入認(rèn)識,對于快速排序和插入排序的時間有了相當(dāng)清晰且一目了然的認(rèn)識,并且從原理上明白了快速

10、排序的快的原因,對各種排序算法的優(yōu)劣性有了全局的認(rèn)識!5、 實驗代碼#include #include #include #include #include using namespace std;const int NumS = 80000;void datagenetare(int num,int n); /產(chǎn)生隨機(jī)數(shù),保存到數(shù)組numvoid WriteFile(int num,char name,int n); /輸出數(shù)組num到data.txt文件void ReadFile(int num,char name);/讀取名為name文件中的數(shù)據(jù),保存到數(shù)組numvoid QuickSo

11、rt(int arr, int n);/將數(shù)組arr中數(shù)據(jù)快速排序void InsertionSort(int arr,int n);/將數(shù)組arr中數(shù)據(jù)直接插入排序int main()int *num=(int *)malloc(sizeof(int)*NumS);int *num1=(int *)malloc(sizeof(int)*NumS);int *num2=(int *)malloc(sizeof(int)*NumS);clock_t start_time1,end_time1,start_time2,end_time2;double timeQS=0,timeIS=0;coutC

12、reate NumS random numbers from 1 to 100000endl;datagenetare(num,NumS); /產(chǎn)生隨機(jī)數(shù),保存到數(shù)組numWriteFile(num,data.txt,NumS); /輸出數(shù)組到data.txt文件cout.precision(6); /設(shè)置浮點數(shù)的顯示精度cout.setf(ios_base:showpoint); /輸出末尾的/直接插入排序的分析ReadFile(num1,data.txt);/讀取data.txt中的數(shù)據(jù),保存到數(shù)組num1coutnInsertionSort Start .n;start_time1=cl

13、ock(); /開始計時InsertionSort(num1,NumS); /直接插入排序數(shù)組num1中的數(shù)據(jù)end_time1=clock(); /結(jié)束計時timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;coutThe Time-comsuption in InsertionSort is timeIS seconds!nn; /輸出運行時間WriteFile(num1,resultsIS.txt,NumS); /排序后的數(shù)據(jù)輸出到resultQS.txt/輸出運行時間timeIS到resultsIS.txtofstream oco

14、ut;ocout.open(resultsIS.txt,ios:app);if(ocout.good() /打開resultsIS.txtocoutnThe Time-comsuption in InsertionSort is timeIS secondsn;ocout.close();elsecoutnCan not open resultsIS.txt!n;exit(1); /異常退出/快速排序的分析ReadFile(num2,data.txt); /讀取data.txt中的數(shù)據(jù),保存到數(shù)組num2coutQuickSort Start .n;start_time2=clock(); /

15、開始計時QuickSort(num2,NumS); /快速排序數(shù)組num中的數(shù)據(jù)end_time2=clock(); /結(jié)束計時timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC;coutThe Time-comsuption in QuickSort is timeQS seconds:n; /輸出運行時間WriteFile(num2,resultsQS.txt,NumS); /排序后的數(shù)據(jù)輸出到resultQS.txt/輸出運行時間timeQS到resultsQS.txtocout.open(resultsQS.txt,ios:app

16、);if(ocout.good() /打開resultsIS.txtocoutnThe Time-comsuption in QuickSort is timeQS secondsn;ocout.close();elsecoutnCan not open resultsQS.txt!n;exit(1); /異常退出return 0;void datagenetare(int *num,int n)int i;srand(unsigned)time(0); /srand()種子發(fā)生器函數(shù),還有rand()隨機(jī)數(shù)生成器函數(shù)for(i=0;in;i+) /產(chǎn)生個到之間的隨機(jī)數(shù)numi=rand()%

17、9999+1;printf(n);/將數(shù)組中的數(shù)據(jù)輸出到文件void WriteFile(int *num,char name,int n)ofstream ocout;ocout.open(name,ios:trunc);int i=0;if(ocout.fail()exit(1); /打開文件失敗,退出for(;in;i+)ocoutnumi ;if(i+1)%40=0|i=n-1) /每輸出40個數(shù),換一行ocoutn;ocout.close();/將文件中的數(shù)據(jù)輸入到數(shù)組void ReadFile(int *num,char name)string strLine;int i=0;ch

18、ar achLine300;const char* pchTok;ifstream icin;icin.open(name,ios:in); /打開名為name的文件while(icin.good()int i = 0;while(getline(icin,strLine)strLine.copy(achLine,strLine.size(),0);achLinestrLine.size()=0;/每行中的元素以空格為標(biāo)識斷開轉(zhuǎn)換為int類型后存入數(shù)組pchTok = strtok(achLine, );while(pchTok != NULL)numi = atoi(pchTok);i+;pchTok = strtok(NULL, );icin.close();/快速排序的實現(xiàn),從左向右遞增排序void QuickSort(int *arr, int n)int L = 0;int R = n-1;int t = arrL; /區(qū)間的第一個數(shù)作為基準(zhǔn)if(n=1) /數(shù)組中存在個或個數(shù)據(jù)時,函數(shù)返回return;/將數(shù)據(jù)分成兩個區(qū)間while(LR) /區(qū)間內(nèi)至少存在一個元素的情況while(LR&t=arrR) R-;/從右向左搜索,直到第一個小于t的數(shù)arrRarrL = arrR;while(LR&arrL=t) L+;/從左向右搜

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論