4 排序與查找

課程內容#

排序#

四象限原則：穩定 / 非穩定、內部 / 外部
- 穩定：相同元素在排序前後的相對位置不變
- 內部：需要將數據整個加載到內存中進行排序

【考慮從小到大排序】

穩定排序#

插入（內部）
- 前：已排序區；後：待排序區
- 後面的數在前面找位置插空
  - 一個一個比較、交換，實現【插入】的效果
  - 不是直接和插入位置交換，這樣會打亂已排序區的順序
- 平均時間複雜度：O (N^2)
冒泡（內部）
- 前：待排序區；後：已排序區
- 從第一個元素向後駛進，找到一個最大元素放在已排序區最前、待排序區最後
- 進行 N - 1 輪冒泡，每輪在已排序中增加一個元素
  - 【優化】當某一輪冒泡過程沒有進行交換操作，可以直接結束
- 平均時間複雜度：O (N^2)
  - 最優時間複雜度：O (N)←已排序
  - 最壞時間複雜度：O (N^2)←完全逆序
- 插入排序可理解為反向冒泡
歸併（外部）
- 前言：兩個有序的數組（長度分別為 m、n）合併成一個有序的數組
  - 時間複雜度：O (m + n)
- 先分治到兩兩可以比較大小，再把有序的數組兩兩合併
- 時間複雜度（最優、最壞、平均都是）：O (NlogN)
  - 共 logN 層，每層的合併時間為 O (N)
- 【外部排序】2 路歸併 (上述)、k 路歸併 (多路歸併，利用堆)
  - 參考外歸併排序- 維基百科，每路的排序方法可以任意，最終歸併
  - 其實這個外部排序與否取決於你想不想、需不需要，但它可以

不穩定排序#

選擇（內部）
- 前：已排序區；後：待排序區
- 每輪從待排序區中選擇一個最小的元素與待排序區的第一個元素交換
  - 可能會有自身與自身交換的情況，所以交換函數不能用異或了
- 不穩定：例如 22'1，在第一次交換後，2 就跑到了 2' 的後面，即 12'2
- 時間複雜度（最優、最壞、平均都是）：O (N^2)
- 一般情況下優於冒泡，兩者比較次數差不多，但冒泡的交換太頻繁
快排（內部）
- 【基準值、partition】
  - 拿出第一個元素作為基準值
  - 【尾指針】先從後往前找小於基準值的元素，放到第一個元素位置 (已為空)，【頭指針】再從前往後找大於基準值的值，放到剛剛空出的位置，循環
  - 最後頭尾指針重合，指向一個空位置，放入基準值
  - 再對基準值左右兩部分分別進行以上操作
- 時間複雜度：O (NlogN)
  - 逆序數列選第一個元素為基準值時，退化為選擇排序，O (N^2)
- 【優化】
  - 基準值隨機選
  - 減少遞歸的使用，用循環做
  - 左右都找到一個要交換的值後，再交換

查找#

樸素二分
- 前提：單調序列
- 如果要查找的值在序列中重複存在，二分查找分辨不出找到的是哪一個
特殊二分
- 11110000
  - 引入虛擬頭指針，索引為 - 1
  - mid 計算需要 + 1，避免死循環，比如 10 情況
- 00001111
  - 引入虛擬尾指針，索引為 n [數組範圍為 0 ~ n - 1]
- 參考《面試筆試算法上》——2. 二分專題
- 這裡比參考內容還增加一個虛擬指針的概念，通過更改查找的邊界 [-1 ~ n -1 或 0 ~ n]，可以反映找不到值時的情況
三分查找
- 解決【求凹凸函數極值點】問題
- 將原問題的規模分成三分之一
- 更新策略：保留值小的元素與另一端的區間；停止條件：|m1 - m2|< ESPL
- 時間複雜度：O (log [3] N)，比二分查找 O (log [2] N) 稍慢

哈希表#

用於查找的【數據結構】
結構定義
- 需要一片連續的空間，存儲元素
- 與順序表一致，元素類型可變
結構操作
- 哈希函數：可以把任意類型元素映射成整型值 [數組下標]
  - 然後可以存儲某值到對應的數組下標中
  - 數組下標只能是整型
- 衝突處理方法
  - 開放定值【常用】：往後看看有沒有空位，如二次探測法... 但容易產生數據堆聚問題
  - 再哈希：又名散列法，使用多種哈希函數
  - 拉鏈法【常用】：用鏈表結構存儲每個位置的元素
  - 建立公共溢出區：把衝突的元素統一放到一個特定區域
查找的時間複雜度：趨近於 O (1)
- 其他耗時：哈希函數轉換、拉鏈法 [查找鏈表元素] 或其他衝突處理方法導致的耗時
- 只有數組、順序表是 O (1) 的
哈希表的空間利用率一般是 50~90%
- 哈希函數一定會存在衝突情況，開辟空間時需要預留
- 當利用率可以達到 70% 時，它就可以在工業上使用了，衝突越少，利用率越高，哈希函數越優秀

代碼演示#

穩定排序#

詳見註釋和紅框標記
要保證穩定排序的穩定性，注意 == 的情況，不能交換 [或保證原有的順序]！
【注意】調用 TEST 宏時，後一個數組是 num，它是在宏定義裡拷貝 arr 得到的一個數組！

不穩定排序#

V1.0 版：選擇排序 & 快速排序普通版#

重點關注快排算法，有很多可優化點
- 【自行優化】46、48 行的 num []> z 或 num [] < z 可以加上 == 條件，這樣在遇到相等的元素不會交換，也沒必要交換，還能儘量保證算法穩定 [雖然快排不穩定]
- 【待優化點】基準值選擇、遞歸→循環、交換方式

V2.0 版：快速排序優化版#

實現上述所提到的 3 個待優化點
注意幾個邊界的 ==：x <= y、num [] < z、num [] > z
- ❓== 的判斷怎麼理解？詳見下面思考點 2
第 39、40 行：排序右區間，排好後縮小右邊界

2 個版本快速排序的速度比較#

分別測試隨機序列和逆序序列
- 20 萬大小的隨機序列：兩者差距甚微
- 10 萬大小的逆序序列：差別明顯
  - 對於 20 萬的逆序序列，原始版快排會爆栈

二分查找#

虛擬指針的使用，可以避免沒有答案時 [000000] 返回假答案 [0 或 n - 1] 的情況
11110000 的情況，在計算 mid 時要 + 1，避免陷入死循環，如 10
詳細可見《面試筆試算法上》——2. 二分專題

建立字符串的哈希表#

哈希函數：BKDR-Hash，衝突處理方法：拉鏈法
插入值時使用的是頭插法
哈希表結構的利用率不可能達到 100%，所以開辟的空間需要擴大，一倍
calloc 開辟哈希表空間，可以讓每個位置的鏈表首地址置空，安全
哈希函數可以自己設計

思考點#

【自己的理解】要保證穩定排序的穩定性，注意 == 的情況，不能交換 [或保證原有的順序]！
❓關於快速排序優化版中邊界的思考
- 同樣按照普通版快排優化邊界判斷，下面優化的思路有問題，而在普通版均可實現
  - 32 - 33 行：num [] < z 和 num [] > z 分別改稱 <= 和 >=，會出現【段錯誤或死循環】
    - 對於 num [] <= z 【死循環】
      - 舉例：2 1 ，基準值為 2，左指針 x 一直走到右端，出界，而右指針 y 不變，第 27 行 while (l < r) 成立，x 又回到 l，變成了死循環
    - 對於 num []>= z 【段錯誤 —— 爆栈】
      - 舉例：1 2，基準值為 1，右指針 y 一直走到左端，變 - 1，而左指針 x 和 r 不變，第 39 行 quick_sort (num, x, r) 不斷遞歸調用，最終爆栈
    - 分析原因：普通版把基準值拿出來了，優化版基準值還在裡面，需要考慮這個區別
  - 32 - 34 行：x <= y 改成 x < y，也會出現【段錯誤】
    - 舉例：2 3，基準值為 2，此時 x、y 分別指向 2、3，經過循環，x、y 都指向 2，而 x 和 r 都不變，第 39 行 quick_sort (num, x, r) 不斷遞歸調用，最終爆栈
    - 分析原因：x、y 要錯開，不然有點像特殊二分 111000 不 + 1 的情況
  - 小結：x、y 都得動起來，x 不動導致爆栈，y 不動導致死循環
  - 【個人理解，考慮不周，歡迎探討】
三分查找 —— 練習題
- 先確定邊界：INT32_MIN ~ INT32_MAX
- 後面按三分查找的步驟來即可
- 邊界思考
  - 根據公式 - b / 2a 估計，但有些作弊嫌疑
  - 根據二次函數 = 0 的兩個解確定範圍，但弄複雜了
  - 三分查找效率是 logN 級別，邊界範圍大小影響不大

Tips#

十大經典排序算法 (動圖演示)-cnblogs
十大經典排序算法動畫與解析，看我就夠了- 五分鐘學算法

課程速記#

提前預習堆與優先隊列，還有並查集的內容