目錄
1.排序的穩定性
2.直接插入排序的特性總結
3.希爾排序的特性總結
4.直接選擇排序的特性總結
5.堆排序的特性總結
6.冒泡排序的特性總結?
7.快速排序的特性總結
8.歸并排序的特性總結
9.計數排序的特性總結
10.總結
1.排序的穩定性
排序的穩定性是說 相同大小的元素在排序后的相對位置不發生改變
例如，
一種排序只要能保證數據穩定性，我們就說它是穩定的?
排序穩定性在多字段排序、數據去重、數據庫查詢等場景中，能確保結果符合預期且可預測?
2.直接插入排序的特性總結
1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩定的排序算法
4. 穩定性：穩定
當元素等于前一個元素時，可選擇將該元素放置到前一個元素后，此時可保證排序穩定
3.希爾排序的特性總結
1. 希爾排序是對直接插入排序的優化
2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定
所以只記結論，時間復雜度為O(N*logN)，約為 (n^1.25) 到 (1.6*n^1.25)
4. 穩定性：不穩
希爾排序是通過分組排序和縮小增量的操作實現數組有序的，那么相同大小的數組難免被分到不同的組中，排序后難以保證相對位置的穩定
4.直接選擇排序的特性總結
1. 直接選擇排序思考非常好理解，但是效率不是很好，實際中很少使用
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：不穩定
如上，2的相對位置發生了改變，直接選擇排序不能保證穩定
5.堆排序的特性總結
1. 堆排序使用堆來選數，效率就高了很多
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(1)
4. 穩定性：不穩定
這個大堆排升序后，9的相對位置發生改變，不穩定
6.冒泡排序的特性總結?
1. 冒泡排序是一種非常容易理解的排序
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：穩定
當某元素等于后一元素時，不交換，就可以保證排序的穩定性
7.快速排序的特性總結
hoare版本
前后指針版本?
挖坑法?
1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(logN)
4. 穩定性：不穩定
如上，快排是不穩定的，與關鍵值相同的元素可能有多個
8.歸并排序的特性總結
1. 歸并的缺點在于需要O(N)的空間復雜度
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(N)
4. 穩定性：穩定
只需要讓相對位置在前的相等大小的元素先歸并，即可達到排序穩定
9.計數排序的特性總結
1. 計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限
2. 時間復雜度：O(MAX(N,范圍))
3. 空間復雜度：O(范圍)
4. 穩定性：穩定
順序計數，反向填充寫(覆蓋寫)就可以實現穩定排序
10.總結
快排： 初始順序影響較大，有序是性能最差
插入: 接近有序，性能最好
希爾：希爾是對插入排序的優化，這種優化是在無序的序列中才有明顯的效果，如果序列接近有序，反而是插入最優。
堆排，歸并，選擇對初始順序不敏感
次序列接近有序，所以如果是插入排序，時間復雜度逼近O(n)
快排： 逼近O(n^2)
歸并和堆排仍然是nlogn
