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

《10.1幾種基本排序算法的實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗題目：幾種基本排序算法的實現(xiàn)姓名：張耀班級：計嵌151學(xué)號：1513052017一、實驗?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ù)和移

2、動次數(shù)。三、算法設(shè)計與N-S圖算法設(shè)計：編寫一個主函數(shù)main()，在主函數(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ù)

3、據(jù)進行排序，輸出排序的結(jié)果以及對應(yīng)的關(guān)鍵字比較次數(shù)和移動次數(shù)。對于測試數(shù)據(jù)，算法中可以考慮幾組數(shù)據(jù)的典型性，如正序，逆序和不同程度等，以取得直觀的感受，從而對不同算法進行比較。一、程序清單#includeusingnamespacestd;voidshowMenu(){cout<<"*菜單*"<

4、序"<>n;sl.length=n;sl.key=newint[sl.length+1];cout<<"請輸入數(shù)據(jù)："<

5、n>>sl.key[i];}}voidCopy(SqList&L1,SqList&L2){L2.length=L1.length;L2.key=newint[L1.length+1];for(inti=1;i<=L1.length;i++){L2.key[i]=L1.key[i];}}voidOutPut(SqList&L){for(intj=1;j<=L.length;++j)cout<

6、ntk=0;intcompare_Time,move_Time;compare_Time=move_Time=0;for(inti=2;i<=L.length;i++){if(L.key[i]<=L.key[i-1])//"<"需將L.key[i]插入有序子表{L.key[0]=L.key[i];//復(fù)制為哨兵L.key[i]=L.key[i-1];intj;for(j=i-2;L.key[0]<=L.key[j];--j){compare_Time++;L.key[j+1]=L.key[j];//記錄后移move_Tim

7、e++;}L.key[j+1]=L.key[0];//插入到正確位置k++;cout<<"第"<

8、)//用i控制比較趟數(shù)共n-1趟{intt;for(intj=1;j<=L.length-i;j++){compare_Time++;if(L.key[j]>L.key[j+1]){t=L.key[j];L.key[j]=L.key[j+1];L.key[j+1]=t;move_Time++;}}k++