資料結構學習筆記 - 排序

排序

簡介

排序算法有很多, 最經典最常用的有

冒泡排序, 插入排序, 選擇排序, 時間複雜度 O(n平方)

快速排序, 歸并排序, 時間複雜度O(nlogn)

桶排序, 計數排序, 基數排序, 時間複雜度O(n)

分析排序算法

• 執行效率

1. 最好情況, 最壞情況, 平時情況時間複雜度
2. 時間複雜度的系數, 常數, 低階
3. 元素比較次數和移動次數

• 記憶體消耗

  可以通過空間複雜度來衡量

• 穩定性

  穩定排序算法可以保持數值相同的兩個對象, 在排序之後的前後順序不變

  真實開發中排序場景往往比較複雜, 有些問題借助穩定排序算法可以非常簡潔的解決

冒泡排序

冒泡過程隻涉及相鄰資料的交換操作, 是以空間複雜度為O(1), 是一個原地排序算法

且當相鄰的兩個元素大小相等時不交換, 相同大小的資料在排序前後不會改變順序, 是以冒泡排序是穩定的排序算法

最好的情況資料有序, 時間複雜度O(n), 最壞的情況資料倒序, 時間複雜度O(n平方), 平均時間複雜度為O(n平方)

插入排序

将數組中的元素分為已排序區和未排序區, 取未排序區元素在已排序區找到合适的位置插入, 并保證已排序區資料一直有序, 直至未排序區為空

插入排序運作也不需要額外的存儲空間, 是以空間複雜度是O(1), 是一個原地排序算法

排序時, 對于值相同的元素可以選擇将後面出現的元素插入到前面出現的元素的後面, 是以是穩定的排序算法

最好的情況資料有序, 時間複雜度O(n), 最壞的情況資料倒序, 時間複雜度O(n平方), 平均時間複雜度為O(n平方)

選擇排序 (todo)

選擇排序類似插入排序, 分已排序區和未排序區, 但每次會從未排序區找到最小元素, 交換位置放到已排序區末尾

選擇排序一樣空間複雜度為O(1), 是一種原地排序算法

最好最壞和平均時間複雜度都是O(n平方)

因為存在交換位置, 是以選擇排序不是一種穩定的排序算法,

以上三種時間複雜度較高, 适合小規模資料排序

選擇排序不是穩定排序算法, 是以稍遜色于冒泡排序和插入排序, 而冒泡排序的資料交換要比插入排序的資料移動複雜, 是以這三種排序, 插入排序更為常用

歸并排序 (todo)

核心思想, 先把數組從中間分成兩部分, 然後對前後兩部分排序, 再将排好序的兩部分合并, 就得到有序的完整數組

歸并排序使用的分治思想, 分治是一種解決問題的處理思想, 遞歸是一種程式設計技巧

用遞歸代碼來實作歸并排序

歸并排序合并過程中, 值相同的元素可以自己掌握順序, 是以是一個穩定的排序算法

時間複雜度為O(nlogn), 且執行效率與原始數組有序度無關, 最好最壞平均情況都是O(nlogn)

但不是原地排序算法, 空間複雜度為O(n)

快速排序 (todo)

也采用分治思想

假如要排序的數組, 最左下标為’左’, 最右下标為’右’, 選中間任意一個點為分區點, 下标’中’

周遊從左到右, 将小于’中’的放到左邊, 大于’中’的放到右邊, 數組就被分成了三部分, '左’到’中-1’的都是小于’中’下标的元素的, ‘中+1’到’右’都是大于’中’下标元素的

根據分治思想, 用遞歸繼續排序’左’到’中-1’和’中+1’到’右’, 直到區間縮小為1, 則所有資料有序, 具體實作方法看源碼

原地, 不穩定排序算法, 分區過程中有交換操作, 是以相同元素順序會變

時間複雜度O(nlogn), 但分區極其不均勻的情況會退化為O(n平方), 平均O(nlogn)

常用選取分區點的算法

1. 三數取中法, 從頭尾中取三個數, 對比大小取中間值作為分區點
2. 随機法, 随機選擇一個元素做為分區點

以上, 快排和歸并很相似, 差別是歸并排序是從下向上處理, 先處理子問題再合并, 快排是由上到下, 先分區, 再處理子問題

歸并時間複雜度穩定但空間複雜度高, 快排空間複雜度低, 且通過合理選擇分區點可以避免時間複雜度退化為O(n平方), 是以快排應用更廣泛

桶排序 (todo)

核心思想把要排序的資料分到幾個有序的桶裡, 每個桶裡的資料再單獨排序, 之後按順序依次取出

桶排序對排序資料要求苛刻, 要能很容易劃分成m個桶, 且桶之間有大小順序, 其次各個桶之間的資料分布均勻

桶排序比較适合用在外部排序中, 即資料存儲在外部磁盤, 資料量大, 記憶體有限

比如10G訂單資料, 記憶體100MB排序問題, 可用桶排序劃分訂單資料, 每個桶生成一個檔案, 如果桶間資料不均勻, 找到較大的檔案, 繼續分桶, 直到所有檔案都能讀入記憶體

計數排序 (todo)

計數排序是桶排序的一種特殊情況

當資料範圍不大時, 最大值為k, 就分k個桶, 省去桶内排序時間, 如果k要比排序的元素個數大得多, 則不适合用計數排序

和桶排序非常相似, 隻是桶的大小粒度不一樣

實作細節稍微複雜, 見代碼

計數排序隻能給非負整數排序, 如有其它類型, 則想辦法在不改變相對大小前提下轉化為非負整數

基數排序 (todo)

基數排序對資料有要求, 需要可以分割出獨立的位來比較, 且位之間有遞進的關系, 從後向前一位一位進行線性排序

另外, 每一位的資料範圍不能太大, 要可以用線性排序算法來排序, 否則時間複雜度就大于O(n)了

針對長度不一樣的, 可以在前面或後面補0

比較兩個數隻需要比較高位, 高位相同再比較低位

以上三種都是線性時間複雜度的排序算法, 它們對要排序的資料有要求, 是以應用不是很廣泛, 但如果資料特征比對, 會非常高效, 時間複雜度可達O(n), 都是穩定非原地排序

總結

以上都是理論知識, 生産環境中使用的排序函數通常都不是基于一種排序算法, 比如資料量小用歸并排序, 資料量大用快排, 快排到區間内元素較少時改用插入排序

為了盡可能提高性能, 通常會做很多優化