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

1、數(shù) 據(jù) 結(jié) 構(gòu) 實 驗 報 告實驗題目：幾種基本排序算法的實現(xiàn)姓名： 張耀班級： 計嵌151學(xué)號： 一、 實驗?zāi)康膶崿F(xiàn)直接插入排序，冒泡排序，簡單選擇排序，快速排序，希爾排序，堆排序等6種常用內(nèi)部排序算法，比較各算法的比較次數(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圖算法設(shè)計：編寫一個主函數(shù)mai

2、n()，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)用6種內(nèi)部排序算法。為了對各種排序算法的性能進行比較，算法中的主要工作是在已知算法的適當(dāng)位置插入對關(guān)鍵字的比較次數(shù)和移動次數(shù)的計數(shù)操作。為此，可設(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ù)。對于測試數(shù)據(jù)，算法中可以考慮幾組數(shù)據(jù)的典型性，如正序，逆序和不同程度等

3、，以取得直觀的感受，從而對不同算法進行比較。四、 程序清單#includeusing namespace std;void showMenu()cout * 菜單 * endl;cout 1.直接插入排序 endl;cout 2.冒泡排序 endl;cout 3.簡單選擇排序 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 建立順序表

4、endl 請輸入順序表的長度 n;sl.length = n;sl.key = new intsl.length + 1;cout 請輸入數(shù)據(jù)： endl;for (int i = 1; i sl.keyi;void Copy(SqList &L1,SqList &L2)L2.length = 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

5、.keyj t;cout endl;void InsertSort(SqList & L)/對順序表L作直接插入排序int k = 0;int compare_Time, 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.key

6、j + 1 = L.keyj;/記錄后移move_Time+;L.keyj + 1 = 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 compare_Time, move_Time;compare_Time = move_Time = 0;for (int i = 1; iL.length; i+)/用i控制比較趟數(shù)共n-1趟i

7、nt t;for (int j = 1; j L.keyj + 1)t = L.keyj;L.keyj = L.keyj + 1;L.keyj + 1 = t;move_Time+;k+;cout 第 k 趟排序結(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;/最小值minkey = L.keyn;for (int i = n + 1; i = L.

8、length; i+)if (L.keyiminkey)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中選擇最小的記錄并將其地址賦給jif (i != j)/交換記錄t

9、 = 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 endl;int Partition(SqList& L, int low, int high,int &compare_Time,int &move_Time)/交換順序表L中子表keylow-keyhigh中的記錄，樞軸記錄到位，并返回其所在位置，/此時在它之前（后）的記錄均不大（?。┯谒黫nt pivot

10、key;L.key0 = L.keylow;/用子表的第一個記錄作樞軸記錄pivotkey = L.keylow;/關(guān)鍵字while (lowhigh)/從表的兩端交替向中間掃描compare_Time+;while (low= pivotkey) -high;L.keylow = L.keyhigh;move_Time+;/將比樞軸小的記錄移至低端while (lowhigh&L.keylow = pivotkey) +low;L.keyhigh = L.keylow;/將比樞軸大的記錄移至高端move_Time+;L.keylow = L.key0;/樞軸記錄到位return low;/返

11、回樞軸位置void QSort(SqList& L, int low, int high,int &k,int &compare_Time,int &move_Time)int mid;/接收樞軸位置if (lowhigh)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, compare_Time, move_Ti

12、me);/對高子表進行排序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;cout 移動次數(shù)為： move_Time endl;void ShellInsert(SqList &L, int dk, int &compare_Time, int &move_Time)/對順序表進行一趟希爾插入排序for (int i = dk

13、+ 1; i = L.length; i+)if (L.keyi 0 & L.key0 = L.keyj; j -= dk)compare_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_Tim

14、e);cout 第 k+1 趟排序結(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;for (int j = 2 * s; j = m; j *= 2)if (jm&L.keyj L.keyj) break;/如果rc最大則推出while循環(huán)L.keys = L.ke

15、yj;/最大值賦值s = j;/交換位置move_Time+;L.keys = rc;void HeapSort(SqList & L)/對順序表L進行堆排序int value,i;int k = 0;int compare_Time = 0, move_Time = 0;for (i = L.length / 2; i0; i-)/把L.key1.L.length調(diào)整為大頂堆HeapAdjust(L, i, L.length, compare_Time, move_Time);for (i = L.length; i1; -i)value = L.key1;L.key1 = L.keyi;L

16、.keyi = value;HeapAdjust(L, 1, i - 1, compare_Time, move_Time);/將L.key1.i-1重新調(diào)整為大頂堆k+;cout 第 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 choice;while (choice != 0)switch (choice)case 1:In

17、sertSort(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); break;case 5:int *p, n;cout 請輸入增量個數(shù)： n;p = new intn;cout 請輸入各個增量的值： endl;for (int i = 0; i pi;ShellSort(sq, p, n); cout 最終結(jié)果：;OutPut(sq); break;case 6:H