1.基于桶的排序
- 桶排序
簡介：
- 判斷數(shù)據(jù)的范圍诈豌，將數(shù)據(jù)范圍劃分為桶
- 將數(shù)據(jù)放入桶中
- 桶內(nèi)進行任意排序
- 桶的個數(shù)最多時為計數(shù)排序
應(yīng)用：
- 計數(shù)排序
簡介：
- 選取數(shù)組中的最大值
max和最小值min - 使用一個大小為
max - min + 1的數(shù)組help购笆，遍歷原數(shù)組，某個值出現(xiàn)一次，便在數(shù)組中加1 - 根據(jù)
help中出現(xiàn)的個數(shù)歹垫，給出新數(shù)組的結(jié)果
應(yīng)用：
- 基數(shù)排序
- 可以用于任意進制，常用于10進制颠放，高位不足時補0
- 先根據(jù)個位進行穩(wěn)定的排序算法
- 依次到高位進行穩(wěn)定的排序算法
- 當(dāng)只有一位數(shù)時為計數(shù)排序
2.基于插入的排序排序
- 插入
- 希爾
簡介：
增量序列,如[len/2,len/4,……1]
當(dāng)序列為len/2時，假如有10個元素吭敢，那么共分為5個組（第1個元素和第6個元素是一組碰凶，第2個元素和第7個元素是一組……）將每個組進行插入排序；下一次增量變小鹿驼，每個組內(nèi)元素變多欲低，再進行插入排序，直到增量為1畜晰，進行一次所有元素的插入排序砾莱。復(fù)雜度為O(n^1.3)------O(n^2)
應(yīng)用：
5.基于選擇的排序
- 簡單選擇排序
- 桶排序
4.基于交換的排序
- 快排
- 冒泡
5.基于歸并的排序
- 二路歸并
- 多路歸并
6. 應(yīng)用場景
(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序凄鼻。
當(dāng)記錄規(guī)模較小時腊瑟，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人块蚌，應(yīng)選直接選擇排序為宜闰非。
(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人峭范、冒泡或隨機的快速排序為宜财松；
(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序纱控、堆排序或歸并排序辆毡。
快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時甜害，快速排序的平均時間最短舶掖；
堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況唾那。這兩種排序都是不穩(wěn)定的访锻。
若要求排序穩(wěn)定褪尝，則可選用歸并排序。但前面介紹的從單個記錄起進行兩兩歸并的排序算法并不值得提倡期犬，通澈友疲可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子序列龟虎，然后再兩兩歸并之璃谨。因為直接插入排序是穩(wěn)定 的，所以改進后的歸并排序仍是穩(wěn)定的鲤妥。
