【C#】【數(shù)據(jù)結(jié)構(gòu)】排序算法總結(jié)
動(dòng)態(tài)可視化排序算法網(wǎng)站——SORTING
時(shí)間復(fù)雜度：
(1)平方階(O(n2))排序
各類簡單排序:直接插入挥唠、直接選擇和冒泡排序；
(2)線性對數(shù)階(O(nlogn))排序
快速排序碳默、堆排序和歸并排序；
(3)O(n1+§))排序,§是介于0和1之間的常數(shù)缘眶。
希爾排序
(4)線性階(O(n))排序
基數(shù)排序腻窒，此外還有桶、箱排序磅崭。
說明：
當(dāng)原表有序或基本有序時(shí)儿子，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)，時(shí)間復(fù)雜度可降至O（n）砸喻；
而快速排序則相反柔逼，當(dāng)原表基本有序時(shí)蒋譬，將蛻化為冒泡排序，時(shí)間復(fù)雜度提高為O（n2）愉适；
原表是否有序犯助，對簡單選擇排序、堆排序维咸、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大剂买。
穩(wěn)定性：
排序算法的穩(wěn)定性:若待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄癌蓖，經(jīng)過排序瞬哼， 這些記錄的相對次序保持不變，則稱該算法是穩(wěn)定的租副；若經(jīng)排序后坐慰，記錄的相對 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的用僧。
穩(wěn)定性的好處：排序算法如果是穩(wěn)定的结胀，那么從一個(gè)鍵上排序，然后再從另一個(gè)鍵上排序责循，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用糟港。基數(shù)排序就是這樣院仿，先按低位排序着逐，逐次按高位排序，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的意蛀。另外，如果排序算法穩(wěn)定健芭，可以避免多余的比較县钥；
穩(wěn)定的排序算法：冒泡排序、插入排序慈迈、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法：選擇排序若贮、快速排序、希爾排序痒留、堆排序
選擇排序算法準(zhǔn)則：
每種排序算法都各有優(yōu)缺點(diǎn)谴麦。因此，在實(shí)用時(shí)需根據(jù)不同情況適當(dāng)選用伸头，甚至可以將多種方法結(jié)合起來使用匾效。
選擇排序算法的依據(jù)
影響排序的因素有很多，平均時(shí)間復(fù)雜度低的算法并不一定就是最優(yōu)的恤磷。相反面哼，有時(shí)平均時(shí)間復(fù)雜度高的算法可能更適合某些特殊情況野宜。同時(shí)，選擇算法時(shí)還得考慮它的可讀性魔策，以利于軟件的維護(hù)匈子。一般而言，需要考慮的因素有以下四點(diǎn)：
1．待排序的記錄數(shù)目n的大写程弧虎敦；
2．記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大姓摇其徙；
3．關(guān)鍵字的結(jié)構(gòu)及其分布情況；
4．對排序穩(wěn)定性的要求堕仔。
設(shè)待排序元素的個(gè)數(shù)為n.
1）當(dāng)n較大擂橘，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序摩骨。
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法通贞，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短恼五；
堆排序： 如果內(nèi)存空間允許且要求穩(wěn)定性的昌罩，
歸并排序：它有一定數(shù)量的數(shù)據(jù)移動(dòng)，所以我們可能過與插入排序組合灾馒，先獲得一定長度的序列茎用，然后再合并，在效率上將有所提高睬罗。
2） 當(dāng)n較大轨功，內(nèi)存空間允許，且要求穩(wěn)定性 : 歸并排序
3）當(dāng)n較小容达，可采用直接插入或直接選擇排序古涧。
直接插入排序：當(dāng)元素分布有序，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)花盐。
直接選擇排序 ：元素分布有序羡滑，如果不要求穩(wěn)定性，選擇直接選擇排序
5）一般不使用或不直接使用傳統(tǒng)的冒泡排序算芯。
6）基數(shù)排序
它是一種穩(wěn)定的排序算法柒昏，但有一定的局限性：
1、關(guān)鍵字可分解熙揍。
2职祷、記錄的關(guān)鍵字位數(shù)較少，如果密集更好
3、如果是數(shù)字時(shí)堪旧，最好是無符號(hào)的削葱，否則將增加相應(yīng)的映射復(fù)雜度，可先將其正負(fù)分開排序淳梦。
總結(jié)：
一析砸、穩(wěn)定性:
穩(wěn)定：冒泡排序、插入排序爆袍、歸并排序和基數(shù)排序
不穩(wěn)定：選擇排序首繁、快速排序、希爾排序陨囊、堆排序
二弦疮、平均時(shí)間復(fù)雜度
O(n^2):直接插入排序，簡單選擇排序蜘醋，冒泡排序胁塞。
在數(shù)據(jù)規(guī)模較小時(shí)（9W內(nèi)），直接插入排序压语，簡單選擇排序差不多啸罢。當(dāng)數(shù)據(jù)較大時(shí)，冒泡排序算法的時(shí)間代價(jià)最高胎食。性能為O(n^2)的算法基本上是相鄰元素進(jìn)行比較扰才，基本上都是穩(wěn)定的。
O(nlogn):快速排序厕怜，歸并排序衩匣，希爾排序，堆排序粥航。
其中琅捏，快排是最好的， 其次是歸并和希爾递雀，堆排序在數(shù)據(jù)量很大時(shí)效果明顯柄延。
三、排序算法的選擇
1.數(shù)據(jù)規(guī)模較小
（1）待排序列基本序的情況下映之，可以選擇直接插入排序；
（2）對穩(wěn)定性不作要求宜用簡單選擇排序蜡坊，對穩(wěn)定性有要求宜用插入或冒泡
2.數(shù)據(jù)規(guī)模不是很大
「苁洹（1）完全可以用內(nèi)存空間，序列雜亂無序秕衙，對穩(wěn)定性沒有要求蠢甲，快速排序，此時(shí)要付出log（N）的額外空間据忘。
○信！（2）序列本身可能有序搞糕，對穩(wěn)定性有要求杠步，空間允許下延蟹，宜用歸并排序
3.數(shù)據(jù)規(guī)模很大
（1）對穩(wěn)定性有求导匣，則可考慮歸并排序礼殊。
【运薄（2）對穩(wěn)定性沒要求，宜用堆排序
4.序列初始基本有序（正序）晶伦，宜用直接插入碟狞，冒泡
