算法排序問題實(shí)驗(yàn)報(bào)告參考模板

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

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

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

4、描while low<high && Ahigh>=privotkey do highhigh-1AlowAhigh /將比樞軸記錄小的記錄移到低端while low<high && Alow<=pivotkey) do lowlow+11 / 12AhighAlow /將比樞軸記錄大的記錄移到高端AlowA0 /樞軸記錄到位return low /返回樞軸位置2、 算法的理論分析1. 直接插入排序算法理論分析從空間來看，直接插入排序只需要一個(gè)數(shù)的輔助空間；從時(shí)間來看，直接插入排序的基本操作為：比較兩個(gè)關(guān)鍵字的大小和移動(dòng)記錄。先分析一趟直

5、接插入排序的情況。偽代碼InsertionSort 中 while 循環(huán)的次數(shù)取決于待插入的數(shù)與前 i-1 個(gè)數(shù)之間的關(guān)系。若 Ai<A0,則在 while 循環(huán)中，待插入數(shù)需與有序數(shù)組 A1.i-1中 i-1 個(gè)數(shù)進(jìn)行比較，并將 Ai-1中 i-1 個(gè)數(shù)后移。則在整個(gè)排序過程（進(jìn)行 n-1 趟插入排序）中，當(dāng)待排序數(shù)組中數(shù)按非遞減有序排列時(shí)，則需進(jìn)行數(shù)間比較次數(shù)達(dá)最小值 n-1,數(shù)不需要移動(dòng)；反之，當(dāng)待排序數(shù)組中數(shù)按非遞增有序排列時(shí)，總的比較次數(shù)達(dá)最大值(n+2)(n-1)/2，數(shù)移動(dòng)的次數(shù)也達(dá)到最大值(n+4)(n-1)/2。若待排序數(shù)組是隨機(jī)的，即待排序數(shù)組中的數(shù)可能出現(xiàn)的各種排序

6、的概率相同，則我們可取上述最小值和最大值的平均值，作為直接插入排序時(shí)所需進(jìn)行數(shù)間的比較次數(shù)和數(shù)的移動(dòng)次數(shù)，約為 n2/4。因此直接插入排序算法，在最佳情況下的時(shí)間復(fù)雜度是 O(n)，在最壞情況下的時(shí)間復(fù)雜度為 O(n2)。2. 快速排序算法理論分析下面我們來分析快速排序的平均時(shí)間性能。 假設(shè) T(n)為對(duì) n 個(gè)記錄 A1.n進(jìn)行快速排序所需時(shí)間，則由算法 QuickSort 可見：其中，Tpass(n)為對(duì) n 個(gè)記錄進(jìn)行一趟快速排序 Partition（A,1,n）所需的時(shí)間，從一趟快速排序算法可見，其和記錄數(shù) n 成正比，可以用 cn 表示（c 為某個(gè)常數(shù)）；T(k-1)和 T（n-k）

7、分別為對(duì) A1.k-1和 Ak+1.n中記錄進(jìn)行快速排序 QuickSort（A,1,k-1）和QuickSort（A,k+1,n）所需時(shí)間。假設(shè)待排序列中記錄是隨機(jī)排列的，則在一趟排序之后，k 取 1 至 n 之間任何一值的概率相同，快速排序所需時(shí)間的平均值則為Tavg(n)=knInn，其中 n 為待排序序列中記錄的個(gè)數(shù)，k 為某個(gè)常數(shù)。 通常，快速排序被認(rèn)為是，在所有同數(shù)量級(jí)（O(nlogn)）的排序方法中，其平均性能最好。但是，若初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間復(fù)雜度為 O(n2)。3、 試驗(yàn)分析1、 試驗(yàn)環(huán)境WIN 32系統(tǒng)，VC6.02、 程序

8、的執(zhí)行1)由函數(shù) datagenetare()生成 20000 個(gè)在區(qū)間1,100000上的隨機(jī)整數(shù)，并將隨機(jī)整數(shù)保存到數(shù)組 num，接著調(diào)用函數(shù) WriteFile()將這些數(shù)輸出到外部文件 data.txt 中。2)調(diào)用函數(shù) ReadFile()從 data.txt 中讀取數(shù)據(jù)，并將其保存到數(shù)組 num1中。接著對(duì)數(shù)組 num1 進(jìn)行直接插入排序，并計(jì)算和記錄其運(yùn)行時(shí)間。最后，調(diào)用函數(shù) WriteFile()將直接插入排序的結(jié)果寫入 resultsIS.txt，并記錄運(yùn)行時(shí)間為 TimeIS。3)調(diào)用函數(shù) ReadFile()從 data.txt 中讀取數(shù)據(jù)，并將其保存到數(shù)組 num2中。

9、接著對(duì)數(shù)組 num2 進(jìn)行快速排序，并計(jì)算和記錄其運(yùn)行時(shí)間。最后，調(diào)用函數(shù) WriteFile()將快速排序的結(jié)果寫入 resultsQS.txt，并記錄運(yùn)行時(shí)間為 TimeQS。3、 試驗(yàn)數(shù)據(jù)當(dāng)N=20000時(shí)：當(dāng)N=30000時(shí)：當(dāng)N=40000時(shí)：當(dāng)N=50000時(shí)：當(dāng)N=60000時(shí)：當(dāng)N=70000時(shí)：當(dāng)N=80000時(shí)：4、 實(shí)驗(yàn)結(jié)果分析20000300004000050000600007000080000插入排序0.3250.7191.3972.1993.054.5715.46快速排序0.0030.0050.0080.010.0120.0110.013做出折線統(tǒng)計(jì)圖4、 試驗(yàn)心得

10、通過本次試驗(yàn)首先對(duì)在C+下的文件操作有了一定的深入認(rèn)識(shí)，對(duì)于快速排序和插入排序的時(shí)間有了相當(dāng)清晰且一目了然的認(rèn)識(shí)，并且從原理上明白了快速排序的快的原因，對(duì)各種排序算法的優(yōu)劣性有了全局的認(rèn)識(shí)！5、 實(shí)驗(yàn)代碼#include <iostream>#include <ctime>#include <cstdlib>#include <fstream>#include <string>using namespace std;const int NumS = 80000;void datagenetare(int num,int n); /產(chǎn)生

11、隨機(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 QuickSort(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(s

12、izeof(int)*NumS);int *num2=(int *)malloc(sizeof(int)*NumS);clock_t start_time1,end_time1,start_time2,end_time2;double timeQS=0,timeIS=0;cout<<"Create "<<NumS<<" random numbers from 1 to 100000"<<endl;datagenetare(num,NumS); /產(chǎn)生隨機(jī)數(shù)，保存到數(shù)組numWriteFile(num,&qu

13、ot;data.txt",NumS); /輸出數(shù)組到data.txt文件cout.precision(6); /設(shè)置浮點(diǎn)數(shù)的顯示精度cout.setf(ios_base:showpoint); /輸出末尾的/直接插入排序的分析ReadFile(num1,"data.txt");/讀取data.txt中的數(shù)據(jù)，保存到數(shù)組num1cout<<"nInsertionSort Start .n"start_time1=clock(); /開始計(jì)時(shí)InsertionSort(num1,NumS); /直接插入排序數(shù)組num1中的數(shù)據(jù)end_t

14、ime1=clock(); /結(jié)束計(jì)時(shí)timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;cout<<"The Time-comsuption in InsertionSort is "<<timeIS<<" seconds!nn" /輸出運(yùn)行時(shí)間WriteFile(num1,"resultsIS.txt",NumS); /排序后的數(shù)據(jù)輸出到resultQS.txt/輸出運(yùn)行時(shí)間timeIS到resultsIS.txtofstream ocou

15、t;ocout.open("resultsIS.txt",ios:app);if(ocout.good() /打開resultsIS.txtocout<<"nThe Time-comsuption in InsertionSort is "<<timeIS<<" secondsn"ocout.close();elsecout<<"nCan not open resultsIS.txt!n"exit(1); /異常退出/快速排序的分析ReadFile(num2,&quo

16、t;data.txt"); /讀取data.txt中的數(shù)據(jù)，保存到數(shù)組num2cout<<"QuickSort Start .n"start_time2=clock(); /開始計(jì)時(shí)QuickSort(num2,NumS); /快速排序數(shù)組num中的數(shù)據(jù)end_time2=clock(); /結(jié)束計(jì)時(shí)timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC;cout<<"The Time-comsuption in QuickSort is "<<timeQS

17、<<" seconds:n" /輸出運(yùn)行時(shí)間WriteFile(num2,"resultsQS.txt",NumS); /排序后的數(shù)據(jù)輸出到resultQS.txt/輸出運(yùn)行時(shí)間timeQS到resultsQS.txtocout.open("resultsQS.txt",ios:app);if(ocout.good() /打開resultsIS.txtocout<<"nThe Time-comsuption in QuickSort is "<<timeQS<<&qu

18、ot; secondsn"ocout.close();elsecout<<"nCan 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;i<n;i+) /產(chǎn)生個(gè)到之間的隨機(jī)數(shù)numi=rand()%9999+1;printf("n");/將數(shù)組中的數(shù)據(jù)輸出到文件void Writ

19、eFile(int *num,char name,int n)ofstream ocout;ocout.open(name,ios:trunc);int i=0;if(ocout.fail()exit(1); /打開文件失敗，退出for(;i<n;i+)ocout<<numi<<" "if(i+1)%40=0|i=n-1) /每輸出40個(gè)數(shù)，換一行ocout<<"n"ocout.close();/將文件中的數(shù)據(jù)輸入到數(shù)組void ReadFile(int *num,char name)string strLine

20、;int i=0;char 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)識(shí)斷開轉(zhuǎn)換為int類型后存入數(shù)組pchTok = strtok(achLine, " ");while(pchTok != NULL)numi = atoi(pchTok);i+;pchTok = strtok(NULL, " ");i