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

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

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

3、對于測試數(shù)據(jù)，算法中可以考慮幾組數(shù)據(jù)的典型性，如正序，逆序和不同程度等，以取得直觀的感受，從而對不同算法進行比較。四、程序清單#include<iostream>using namespace std;void showMenu()cout << "*菜單*" << endl;cout << "1.直接插入排序" << endl;cout << "2.冒泡排序" << endl;cout << "3.簡單選擇排序" &l

4、t;< endl;cout << "4.快速排序" << endl;cout << "5.希爾排序" << endl;cout << "6.堆排序" << endl;cout << "7.退出程序" << endl;struct SqListint * key;int length;void CreateSqList(SqList &sl)/type 為intint n;cout << &quo

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

6、ength = L1.length;L2.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)/ 對順序表 L作直接插入排序int k = 0;int compare_Time

7、, move_Time;compare_Time = 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 j;for (j = i - 2; L.key0 <= L.keyj; -j)compare_Time+;L.keyj + 1 = L.keyj;/記錄后移Word 資料·move_Time+;L.keyj + 1

8、 = L.key0;/插入到正確位置k+;cout << " 第 " << k << "趟排序結(jié)果： " OutPut(L);compare_Time+;cout << " 比較次數(shù)為： " << compare_Time << endl;cout << " 移動次數(shù)為： " << move_Time << endl;void BubbleSort(SqList & L)int k = 0;int c

9、ompare_Time, move_Time;compare_Time = move_Time = 0;for (int i = 1; i<L.length; i+)/用i控制比較趟數(shù)共 n-1 趟int t;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 << &qu

10、ot;趟排序結(jié)果： " OutPut(L);cout << " 比較次數(shù)為： " << compare_Time << endl;cout << " 移動次數(shù)為： " << move_Time << endl;int SelectMinKey(SqList& L, int n, int &compare_Time)int min = n;int minkey;/ 最小值Word 資料·minkey = L.keyn;for (int i = n +

11、 1; i <= L.length; i+)if (L.keyi<minkey)minkey = L.keyi;min = i;compare_Time+;return min;void SelectSort(SqList & L)/ 對順序表 L作簡單選擇排序int j;int t;int k = 0;int move_Time = 0, compare_Time = 0;for (int i = 1; i <= L.length; i+)j = SelectMinKey(L, i, compare_Time);/在 L.keyi-L.keyL.length中選擇最

12、小的記錄并將其地址賦給jif (i != j)/ 交換記錄t = L.keyi;L.keyi = L.keyj;L.keyj = t;move_Time+;compare_Time+;k+;cout << " 第" << k << "趟排序結(jié)果： " OutPut(L);cout << " 比較次數(shù)為： " << compare_Time << endl;cout << " 移動次數(shù)為： " << move_Time &

13、lt;< endl;int Partition(SqList& L, int low, int high,int &compare_Time,int &move_Time)Word 資料·/ 交換順序表 L中子表 keylow-keyhigh中的記錄，樞軸記錄到位， 并返回其所在位置，/ 此時在它之前（后）的記錄均不大（?。┯谒黫nt pivotkey;L.key0 = L.keylow;/用子表的第一個記錄作樞軸記錄pivotkey = L.keylow;/關(guān)鍵字while (low<high)/從表的兩端交替向中間掃描compare_Time+

14、;while (low<high&&L.keyhigh >= pivotkey) -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

15、 &k,int &compare_Time,int &move_Time)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);/ 對低子表進行排序 QSort(L, mid + 1, high, k

16、, compare_Time, move_Time);/ 對高子表進行排序void QuitSort(SqList & L)/對順序表進行快速排序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;Word 資料·cout << " 移動次數(shù)為： " << mo

17、ve_Time << endl;void ShellInsert(SqList &L, int dk, int &compare_Time, int &move_Time)/ 對順序表進行一趟希爾插入排序for (int i = dk + 1; i <= L.length; i+)if (L.keyi <= L.keyi - dk)compare_Time+;L.key0 = L.keyi;int j;for (j = i - dk; j > 0 && L.key0 <= L.keyj; j -= dk)compare

18、_Time+;L.keyj + dk = L.keyj;move_Time+;L.keyj + dk = L.key0;void ShellSort(SqList &L, int dlta, int t)int compare_Time = 0, move_Time = 0;/ 按增量序列 dl0-dlt-1對順序表 L作哈希排序for (int k = 0; k < t; k+)ShellInsert(L, dltak, compare_Time, move_Time);cout << " 第" << k+1 << &qu

19、ot;趟排序結(jié)果： " OutPut(L);cout << " 比較次數(shù)為： " << compare_Time << endl;cout << " 移動次數(shù)為： " << move_Time << endl;void HeapAdjust(SqList& L, int s, int m, int &compare_Time, int &move_Time)/ 對順序表做查找，從值最大的孩子結(jié)點向下篩選，找到最大值int rc = L.keys;fo

20、r (int j = 2 * s; j <= m; j *= 2)if (j<m&&L.keyj <= L.keyj + 1)/找到值相對較大的孩子結(jié)點，并依次向下篩選j+;Word 資料·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)/ 對順序表 L進行堆排序int value,i;int k = 0;int

21、 compare_Time = 0, move_Time = 0;for (i = L.length / 2; i>0; i-)/ 把 L.key1.L.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.key1.i-1 重新調(diào)整為大頂堆k+;cout

22、 << " 第" << k << "趟排序結(jié)果： " OutPut(L);cout << " 比較次數(shù)為： " << compare_Time << endl;cout << " 移動次數(shù)為： " << move_Time << endl;int main()int choice;SqList sq,sp;CreateSqList(sq);Copy(sq, sp);showMenu();cout <&l

23、t; "Please enter your choice: "cin >> choice;while (choice != 0)switch (choice)Word 資料·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;