幾種基本排序算法的實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：幾種基本排序算法的實(shí)現(xiàn)姓名：張耀班級(jí)：計(jì)嵌151學(xué)號(hào):1513052017編輯版word1、 實(shí)驗(yàn)?zāi)康膶?shí)現(xiàn)直接插入排序，冒泡排序，簡(jiǎn)單選擇排序，快速排序，希爾排序，堆排序等6 種常用內(nèi)部排序算法，比較各算法的比較次數(shù)和移動(dòng)次數(shù)。2、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(1) 設(shè)計(jì)待排序記錄的存儲(chǔ)結(jié)構(gòu)。(2) 設(shè)計(jì)待排序數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。(3) 輸入： 待排序數(shù)據(jù)的數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)可由鍵盤(pán)輸入，也可由程序生成偽隨機(jī)數(shù)，以菜單方式選擇上述排序方法中的一個(gè)，并指明輸出第幾趟排序的結(jié)果。(4)輸出：各趟排序結(jié)果或指定趟的排序結(jié)果，以及對(duì)應(yīng)的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。三、算法設(shè)計(jì)與N-S圖算法設(shè)計(jì)：編寫(xiě)

2、一個(gè)主函數(shù)main(),在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)用6 種內(nèi)部排序算法。為了對(duì)各種排序算法的性能進(jìn)行比較，算法中的主要工作是在已知算法的適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)操作。為此， 可設(shè)立一個(gè)實(shí)現(xiàn)排序算法中的關(guān)鍵字比較的函數(shù)；設(shè)立一個(gè)實(shí)現(xiàn)排序算法中的關(guān)鍵字移動(dòng)的函數(shù)；設(shè)立一個(gè)實(shí)現(xiàn)排序算法中的關(guān)鍵字交換的函數(shù)，從而解決比較次數(shù)和移動(dòng)次數(shù)的統(tǒng)計(jì)問(wèn)題。鍵盤(pán)輸入或由偽隨機(jī)數(shù)程數(shù)據(jù)的輸入也可以通過(guò)菜單選擇輸入方式：序生成數(shù)據(jù)，以便隨時(shí)更換排序數(shù)據(jù)，并按照不同要求對(duì)排序數(shù)據(jù)進(jìn)行排序，輸出排序的結(jié)果以及對(duì)應(yīng)的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。對(duì)于測(cè)試數(shù)據(jù)，算法中可以考慮幾組數(shù)據(jù)的典型性，如正

3、序，逆序和 不同程度等，以取得直觀的感受，從而對(duì)不同算法進(jìn)行比較。四、 程序清單#include<iostream>using namespace std;void showMenu()cout << "* 菜單*" << endl;cout << "1.直接插入排序" << endl;cout << "2.冒泡排序" << endl;cout << "3.簡(jiǎn)單選擇排序" << endl;cout <&

4、lt; "4.快速排序" << endl;cout << "5.希爾排序" << endl;cout << "6.堆排序" << endl;cout << "7.退出程序" << endl;struct SqListint * key;編輯版 wordint length;int j;編輯版 word;void CreateSqList(SqList &sl)type 為 intint n;<< endl;cou

5、t << " 建立順序表" << endl << " 請(qǐng)輸入順序表的長(zhǎng)度cin >> n;1 l.length = n;51 .key = new intsl.length + 1;cout << " 請(qǐng)輸入數(shù)據(jù)：" << endl;for (int i = 1; i <= sl.length; i+)cin >> sl.keyi;void Copy(SqList &L1,SqList &L2)L2.length = L1.length;L

6、2.key = new intL1.length + 1;for (int i = 1; i <=L1.length; i+)L2.keyi = L1.keyi;void OutPut(SqList &L)for (int j = 1; j <= L.length; +j)cout << L.keyj << "t"cout << endl;void InsertSort(SqList & L)/對(duì)順序表L作直接插入排序int k = 0;int compare_Time, move_Time;compare_T

7、ime = move_Time = 0;for (int i = 2; i <= L.length; i+)if (L.keyi <= L.keyi - 1)/"<"需將 L.keyi插入有序子表L.key0 = L.keyi;/ 復(fù)制為哨兵L.keyi = L.keyi - 1;int t;for (j = i - 2; L.key0 <= L.keyj; -j)compare_Time+;L.keyj + 1 = L.keyj;/ 記錄后移move_Time+;L.keyj + 1 = L.key0;/ 插入到正確位置k+;cout <&l

8、t; " 第 " << k << " 趟排序結(jié)果：" OutPut(L);compare_Time+;cout << " 比較次數(shù)為：" << compare_Time << endl;cout << " 移動(dòng)次數(shù)為：" << move_Time << endl;void BubbleSort(SqList & L)int k = 0;int compare_Time, move_Time;compare_Tim

9、e = move_Time = 0;for (int i = 1; i<L.length; i+) 用 i控制比較趟數(shù)共 n-1 趟for (int j = 1; j <= L.length - i; j+)compare_Time+;if (L.keyj>L.keyj + 1)t = L.keyj;L.keyj = L.keyj + 1;L.keyj + 1 = t;move_Time+;k+;cout << " 第 " << k << " 趟排序結(jié)果：" OutPut(L);cout <&l

10、t; " 比較次數(shù)為：" << compare_Time << endl;cout << " 移動(dòng)次數(shù)為：" << move_Time << endl;int SelectMinKey(SqList& L, int n, int &compare_Time)int min = n;編輯版 wordint minkey;/ 最小值minkey = L.keyn;for (int i = n + 1; i <= L.length; i+)if (L.keyi<minkey

11、)minkey = L.keyi;min = i;compare_Time+;return min;void SelectSort(SqList & L)/對(duì)順序表L作簡(jiǎn)單選擇排序int j;int t;int k = 0;int move_Time = 0, compare_Time = 0;編輯版 wordfor (int i = 1; i <= L.length; i+)j = SelectMinKey(L, i, compare_Time);/ 在 L.keyi-L.keyL.length中選擇最小的記錄并將其地址賦給jif (i != j)/ 交換記錄t = L.key

12、i;L.keyi = L.keyj;L.keyj = t;move_Time+;compare_Time+;k+;cout << " 第 " << k << " 趟排序結(jié)果：" OutPut(L);cout << " 比較次數(shù)為：" << compare_Time << endl;cout << " 移動(dòng)次數(shù)為：" << move_Time << endl;int Partition(SqList&

13、L, int low, int high,int &compare_Time,int &move_Time)/交換順序表L中子表keylow-keyhigh中的記錄，樞軸記錄到位，并返回其所在位置，/ 此時(shí)在它之前(后)的記錄均不大(小)于它int pivotkey;L.key0 = L.keylow;/ 用子表的第一個(gè)記錄作樞軸記錄pivotkey = L.keylow;/ 關(guān)鍵字while (low<high)/ 從表的兩端交替向中間掃描compare_Time+;while (low<high&&L.keyhigh >= pivotkey

14、) -high;L.keylow = L.keyhigh;move_Time+;/ 將比樞軸小的記錄移至低端while (low<high&&L.keylow <= pivotkey) +low;L.keyhigh = L.keylow;/ 將比樞軸大的記錄移至高端move_Time+;L.keylow = L.key0;/ 樞軸記錄到位return low;/ 返回樞軸位置void QSort(SqList& L, int low, int high,int &k,int &compare_Time,int &move_Time)

15、int mid;/ 接收樞軸位置if (low<high)mid = Partition(L, low, high,compare_Time,move_Time);k+;cout << " 第 " << k << " 趟排序結(jié)果：" OutPut(L);QSort(L, low, mid - 1,k,compare_Time,move_Time);/ 對(duì)低子表進(jìn)行排序QSort(L, mid + 1, high, k, compare_Time, move_Time);/ 對(duì)高子表進(jìn)行排序void QuitSor

16、t(SqList & L)/ 對(duì)順序表進(jìn)行快速排序int k = 0;int compare_Time = 0, move_Time = 0;QSort(L, 1, L.length,k,compare_Time,move_Time);cout << " 比較次數(shù)為：" << compare_Time << endl;cout << " 移動(dòng)次數(shù)為：" << move_Time << endl;void ShellInsert(SqList &L, int dk, i

17、nt &compare_Time, int &move_Time)/ 對(duì)順序表進(jìn)行一趟希爾插入排序for (int i = dk + 1; i <= L.length; i+)if (L.keyi <= L.keyi - dk)編輯版 wordcompare_Time+;L.key0 = L.keyi;int j;for (j = i - dk; j > 0 && L.key0 <= L.keyj; j -= dk)compare_Time+;L.keyj + dk = L.keyj;move_Time+;L.keyj + dk = L.

18、key0;void ShellSort(SqList &L, int dlta, int t)int compare_Time = 0, move_Time = 0;/按增量序列dl-dlt-1對(duì)順序表L作哈希排序for (int k = 0; k < t; k+)ShellInsert(L, dltak, compare_Time, move_Time);cout << " 第 " << k+1 << " 趟排序結(jié)果：" OutPut(L);cout << " 比較次數(shù)為：&quo

19、t; << compare_Time << endl;cout << " 移動(dòng)次數(shù)為：" << move_Time << endl;void HeapAdjust(SqList& L, int s, int m, int &compare_Time, int &move_Time)/ 對(duì)順序表做查找，從值最大的孩子結(jié)點(diǎn)向下篩選，找到最大值int rc = L.keys;for (int j = 2 * s; j <= m; j *= 2)if (j<m&&L.ke

20、yj <= L.keyj + 1)/ 找到值相對(duì)較大的孩子結(jié)點(diǎn)，并依次向下篩選j+;compare_Time+;if (rc>L.keyj) break;/ 如果 rc最大則推出 while循環(huán)L.keys = L.keyj;/ 最大值賦值s = j;/ 交換位置move_Time+;L.keys = rc;void HeapSort(SqList & L)/對(duì)順序表L進(jìn)行堆排序int value,i;int k = 0;int compare_Time = 0, move_Time = 0;for (i = L.length / 2; i>0; i-)/ 把 L.k

21、ey1L.length調(diào)整為大頂堆 HeapAdjust(L, i, L.length, compare_Time, move_Time);for (i = L.length; i>1; -i) value = L.key1;L.key1 = L.keyi;L.keyi = value;HeapAdjust(L, 1, i - 1, compare_Time, move_Time);/將 L.key1i-1厘新調(diào)整為大 頂堆k+;cout << " 第 " << k << " 趟排序結(jié)果：" OutPut(L);

22、cout << " 比較次數(shù)為：" << compare_Time << endl;cout << " 移動(dòng)次數(shù)為：" << move_Time << endl;int main()int choice;SqList sq,sp;CreateSqList(sq);Copy(sq, sp);showMenu();cout << "Please enter your choice: "cin >> choice;while (choice !=

23、 0)switch (choice)case 1:InsertSort(sq); cout << " 最終結(jié)果："OutPut(sq); break;case 2:BubbleSort(sq); cout << "最終結(jié)果："OutPut(sq); break;case 3:SelectSort(sq); cout << "最終結(jié)果："OutPut(sq); break;case 4:QuitSort(sq); cout << " 最終結(jié)果："OutPut(sq);

24、break;case 5:int *p, n;cout << " 請(qǐng)輸入增量個(gè)數(shù)：" << endl;cin >> n;p = new intn;cout << " 請(qǐng)輸入各個(gè)增量的值：" << endl;for (int i = 0; i < n; i+)cin >> pi;ShellSort(sq, p, n); cout << "最終結(jié)果："OutPut(sq); break;case 6:HeapSort(sq); cout <&l

25、t; "最終結(jié)果："OutPut(sq); break;case 7:cout << " 程序運(yùn)行結(jié)束，退出程序。" << endl;return 0; break;Copy(sp, sq);showMenu();編輯版 wordcout << "Please enter your choice:" cin >> choice;return 0;五、運(yùn)行與測(cè)試建3%序立詰徐人崎序表的長(zhǎng)度隨物人數(shù)展« 2 5 7 1 8 3*菜單次1,直震插入排序3冒泡排療丸商單通謹(jǐn)排序4 .快速邨后5,希亦在序e.Off心退出程停please cnier your choioe： 1R- 8 7 8扁闡排序菇果242.靠建排序結(jié)果1 廉想排中站果 比較次數(shù)那K 廊柩數(shù)疝3 盤(pán)翼結(jié)盛11一直接而人排序2 一冒泡排存3而單送擇排序4.快避排序5個(gè)宇啡存6.儺排序L退出程疔ease enter ywr choice： 2第I超才比我次數(shù)為;21 移動(dòng)次數(shù)為 9 牌中皓臬一2 7 7 777 R32222222 3 心的序 序 C，琲.