7-7各種排序方法的比較v第七章排序技術(shù)學(xué)什么？各種排序方法的使用范例各種排序方法的綜合比較使用范例#include<iostream>#include<cmath>usingnamespacestd;//將排序類定義和各個(gè)排序算法的成員函數(shù)定義放到這里

intmain(){intselect,r[10]={2,5,1,7,9,4,3,6,5,8};SortL{r,10};cout<<"1.直接插入排序2.希爾排序"<<endl;cout<<"3.起泡排序4.快速排序"<<endl;cout<<"5.簡(jiǎn)單選擇排序6.堆排序"<<endl;cout<<"7.二路歸并遞歸排序8.二路歸并非遞歸排序"<<endl;cout<<"請(qǐng)輸入使用的排序技術(shù)編號(hào)：";cin>>select;switch(select){case1:L.InsertSort();break;case2:L.ShellSort();break;case3:L.BubbleSort();break;case4:L.QuickSort(0,9);break;case5:L.SelectSort();break;case6:L.HeapSort();break;case7:L.MergeSortRecusion(0,9);break;case8:L.MergeSort();break;default:cout<<"輸入排序編號(hào)錯(cuò)誤"<<endl;break;}L.Print();return0;}排序方法平均情況直接插入排序O(n2)希爾排序O(nlog2n)~O(n2)起泡排序O(n2)快速排序O(nlog2n)簡(jiǎn)單選擇排序O(n2)堆排序O(nlog2n)歸并排序O(nlog2n)（1）直接插入排序、簡(jiǎn)單選擇排序和起泡排序?qū)儆谝活悾瑫r(shí)間復(fù)雜度為O(n2)；從平均情況看快速排序是目前最快的一種排序方法（3）希爾排序的時(shí)間性能取決于增量序列，介于O(n2)和O(nlog2n)之間。（2）堆排序、快速排序和歸并排序?qū)儆谝活?，時(shí)間復(fù)雜度為O(nlog2n)；比較時(shí)間性能排序方法最好情況直接插入排序O(n)希爾排序O(n1.3)起泡排序O(n)快速排序O(nlog2n)簡(jiǎn)單選擇排序O(n2)堆排序O(nlog2n)歸并排序O(nlog2n)從最好情況看（1）直接插入排序和起泡排序最好，O(n)；（2）其他排序算法的最好情況與平均情況相同。如果待排序序列接近正序，首選直接插入排序和起泡排序比較時(shí)間性能排序方法最壞情況直接插入排序O(n2)希爾排序O(n2)起泡排序O(n2)快速排序O(n2)簡(jiǎn)單選擇排序O(n2)堆排序O(nlog2n)歸并排序O(nlog2n)（1）快速排序的時(shí)間復(fù)雜度為O(n2)；從最壞情況看（3）最壞情況對(duì)直接選擇排序、堆排序和歸并排序影響不大。（2）直接插入排序和起泡排序雖然與平均情況相同，但系數(shù)大約增加一倍，所以運(yùn)行速度將降低一半；如果待排序序列接近正序或逆序，不推薦使用快速排序比較時(shí)間性能從空間性能看排序方法輔助空間直接插入排序O(1)希爾排序O(1)起泡排序O(1)快速排序O(log2n)~O(n)簡(jiǎn)單選擇排序O(1)堆排序O(1)歸并排序O(n)（1）歸并排序的空間復(fù)雜度為O(n)；（2）快速排序的空間復(fù)雜度為O(log2n)~O(n)；（3）其它排序方法的空間復(fù)雜度為O(1)。比較空間性能穩(wěn)定性與簡(jiǎn)單性（1）穩(wěn)定：包括直接插入排序、起泡排序和歸并排序；（1）簡(jiǎn)單算法：包括直接插入排序、簡(jiǎn)單選擇排序和起泡排序，從算法簡(jiǎn)單性看（2）不穩(wěn)定：包括希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序。從穩(wěn)定性看（2）改進(jìn)算法，較復(fù)雜：包括希爾排序、堆排序、快速排序和歸并排序。記錄本身信息量從記錄本身信息量的大小看記錄本身信息量越大，占用的存儲(chǔ)空間就越多，移動(dòng)記錄所花費(fèi)的時(shí)間就越多，所以對(duì)記錄的移動(dòng)次數(shù)較多的算法不利。記錄個(gè)數(shù)不多且記錄本身的信息量較大時(shí)，首選簡(jiǎn)單選擇排序算法排序方法最好情況最壞情況平均情況直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)簡(jiǎn)單選擇排序0O(n)O(n)關(guān)鍵碼的分布從關(guān)鍵碼的分布看（1）當(dāng)待排序記錄按關(guān)鍵碼有序時(shí)，插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度；對(duì)于快速排序而言，這是最壞情況，時(shí)間性能蛻化為O(n2)；（2）簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵碼的分布而改變。各種排序算法各有優(yōu)缺點(diǎn)，應(yīng)該根據(jù)實(shí)際情況選擇合適的排序算法更深入的比較對(duì)于一般的內(nèi)部排序應(yīng)用插入排序、希爾排序、歸并排序和快速排序是經(jīng)常選用的方法，究竟使用哪個(gè)方法依賴于輸入規(guī)模和底層環(huán)境?？焖倥判虿蝗绮迦肱判蚝谩Ｒ?yàn)榭焖倥判蚴沁f歸執(zhí)行的，所以這種情況會(huì)經(jīng)常發(fā)生。解決方法是對(duì)于小數(shù)組不使用遞歸快速排序，而使用插入排序等對(duì)小數(shù)組高效的排序算法，相對(duì)于自始至終使用快速排序節(jié)省大約15%的運(yùn)行時(shí)間。對(duì)于字符串排序?qū)τ谏倭康妮斎肴绻址械淖址∽暂^小字母表，并且字符串或者相對(duì)較短或者非常相似，對(duì)字符串進(jìn)行基數(shù)排序的效率會(huì)特別好。更深入的比較Java標(biāo)準(zhǔn)庫使用歸并排序算法在Java中執(zhí)行泛型排序，由于不容易使用內(nèi)聯(lián)，動(dòng)態(tài)調(diào)度的開銷會(huì)減慢執(zhí)行速度，因此比較元素非常費(fèi)時(shí)。但是移動(dòng)元素相對(duì)省時(shí)，可以采用引用賦值，而不是龐大的對(duì)象拷貝。歸并排序的比較次數(shù)是所有常