(最新整理)10.1幾種基本排序算法的實(shí)現(xiàn)

1、(完整)10.1幾種基本排序算法的實(shí)現(xiàn)(完整)10.1幾種基本排序算法的實(shí)現(xiàn) 編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對(duì)文中內(nèi)容進(jìn)行仔細(xì)校對(duì)，但是難免會(huì)有疏漏的地方，但是任然希望（(完整)10.1幾種基本排序算法的實(shí)現(xiàn)）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來便利。同時(shí)也真誠的希望收到您的建議和反饋，這將是我們進(jìn)步的源泉，前進(jìn)的動(dòng)力。本文可編輯可修改，如果覺得對(duì)您有幫助請(qǐng)收藏以便隨時(shí)查閱，最后祝您生活愉快 業(yè)績進(jìn)步，以下為(完整)10.1幾種基本排序算法的實(shí)現(xiàn)的全部內(nèi)容。數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)題目:幾種基本排序算法的實(shí)現(xiàn)

2、姓名： 張耀班級(jí)： 計(jì)嵌151學(xué)號(hào)： 1513052017一、 實(shí)驗(yàn)?zāi)康膶?shí)現(xiàn)直接插入排序，冒泡排序，簡單選擇排序，快速排序，希爾排序，堆排序等6種常用內(nèi)部排序算法,比較各算法的比較次數(shù)和移動(dòng)次數(shù)。二、 數(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ù)可由鍵盤輸入，也可由程序生成偽隨機(jī)數(shù)，以菜單方式選擇上述排序方法中的一個(gè)，并指明輸出第幾趟排序的結(jié)果。（4)輸出:各趟排序結(jié)果或指定趟的排序結(jié)果，以及對(duì)應(yīng)的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。三、 算法設(shè)計(jì)與ns圖算法設(shè)計(jì)：編寫一個(gè)主函數(shù)main(），在主函數(shù)中設(shè)計(jì)一個(gè)簡單的菜單,分別調(diào)

3、用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ì)問題。數(shù)據(jù)的輸入也可以通過菜單選擇輸入方式：鍵盤輸入或由偽隨機(jī)數(shù)程序生成數(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ù)的典型性，如正序,逆序和不同程度等，以取得直觀的感受,從而對(duì)不同算法進(jìn)行比較。

4、四、 程序清單includeiostreamusing 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 建立順序表”

5、endl 請(qǐng)輸入順序表的長度” endl;cin n；sl。length = n；sl。key = new intsl.length + 1；cout 請(qǐng)輸入數(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;

6、 +j)cout l。keyj ”t”；cout endl；void insertsort(sqlist l)/對(duì)順序表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

7、+;l。keyj + 1 = l.keyj；/記錄后移move_time+;l.keyj + 1 = l.key0；/插入到正確位置k+;cout 第” 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_time = move_time = 0；for （int i = 1； il.length; i+）/用i

8、控制比較趟數(shù)共n1趟int 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 ”移動(dòng)次數(shù)為：” move_time endl;int selectminkey（sqlist& l， int n， int &compare_time)int min = n；int minkey；/最小值minkey = l.keyn；for (int

9、 i = n + 1; i = l。length； i+）if （l。keyiminkey）minkey = l。keyi；min = i；compare_time+;return min;void selectsort(sqlist l）/對(duì)順序表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中選擇最小的記錄并將其地址賦給ji

10、f （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 ”移動(dòng)次數(shù)為：” move_time endl；int partition(sqlist& l， int low, int high，int &compare_time,int &move_time）/交換順序表l中子表keylow-keyhigh中的記錄,樞軸記錄到位，并返回其所在位置，/此時(shí)在它之前（后）

11、的記錄均不大（?。┯谒黫nt pivotkey;l。key0 = l。keylow;/用子表的第一個(gè)記錄作樞軸記錄pivotkey = l.keylow;/關(guān)鍵字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；/返回樞軸位置void qsort（sqlist

12、 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）;/對(duì)低子表進(jìn)行排序qsort（l, mid + 1， high, k， compare_time， move_time);/對(duì)高子表進(jìn)行排序void quitso

13、rt（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， int compare_time, int &move_time)/對(duì)順序表進(jìn)行一趟希爾插入排序for （int i = dk + 1; i = l。length； i+）if

14、(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_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對(duì)順序表l作哈希排序for (int k = 0; k t; k+)she

15、llinsert(l, dltak， compare_time， move_time);cout ”第” k+1 ”趟排序結(jié)果：； output(l）;cout 比較次數(shù)為：” 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 （jm&l.keyj l.

16、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; i0； i）/把l。key1.l。length調(diào)整為大頂堆heapadjust（l, i， l。length, compare_time， move_time)；for (i = l。length；

17、i1; -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 ”第” k 趟排序結(jié)果：”; output(l）；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 choic

18、e；while （choice != 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); break;case 5:int p, n；cout 請(qǐng)輸入增量個(gè)數(shù)：” n;p = new intn；cout ”請(qǐng)輸入各個(gè)增量的值: endl；for (int i = 0; i pi;shellsort（sq, p， n); cout 最終結(jié)果:”;output(sq);