算法排序問題實驗報告

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+;/從左向右搜