數據結構篇_知識點板塊_第八章內部排序

  • 數據結構篇為本人考研時所寫筆記，包括知識點和編程思想兩大板塊，筆記內容依據王道數據結構考研書所寫，但比書本上知識更加生動形象，願本篇章能對您有所幫助

八、內部排序

（一）排序基本概念

  1. 考試常考：看到某特定序列選擇最優演算法（一般用排除法寫，且一般進行極端情況的對比，只要優於就選）

  4. 堆排序題目問數組狀態時答是畫圖

  5. 名詞概念：

①　文件：由一組記錄組成，記錄有若干數據項組成

②　關鍵字：唯一標識記錄的數據項

  1. 穩定性：

①　經過排序後，能使關鍵字形態的元素保持原順序中的相對位置不變

②　不穩定性：反之

③　注意：演算法是否具有穩定性並不能衡量一個演算法的優劣，它主要是對演算法的性質描述

④　答題時說明不穩定性只需舉出一組關鍵字序列即可

⑤　兩個穩定的演算法一起用程式還是穩定的

  1. 排序分類：

①　內部排序：數據元素是否完全在記憶體中（一般要演算法執行過程中都進行比較和移動操作，但比如基數排序就不基於比較）

②　外部排序：反之

  1. 內部排序演算法性能取絕與演算法的時間複雜度（時間性能，時間效率）和空間複雜度（空間性能，空間效率）

  2. 對同一線性表使用不同的排序演算法排序，得到的排序結果可能不同

  3. 對任意n個關鍵字排序的次數至少為向上取整（log_2(n!)）

  4. 進行基數排序時記得從個位數開始比，不要習慣性的比較數字的第一個數字

  5. 篩選法建堆，它可以在線性時間複雜度下完成建堆。以最大堆為例介紹具體操作過程：

①　首先將N個數據元素存入一個一維數組，並把這個數組視作一棵完全二叉樹。

②　從二叉樹的最後一個非葉結點（數組n/2開始）開始用從上向下過濾的方法調整以該非葉結點為根節點的二叉樹為最大堆。

③　對前面的結點依次執行2）的操作直到根結點執行完成為止。此時這棵二叉樹就調整為了一個最大堆

④　構建堆是邊插邊排

⑤　建堆時比較次數不超過4n次

  1. 從小根堆調整到大根堆是從最下面最右邊的一棵子樹開始調整，反之亦然

（二）各排序演算法的比較

  1. 一般基於三個因素進行比較：

①　時空複雜度

②　演算法穩定性

③　演算法的過程特徵（演算法的複雜程度）

1）效率比較

  1. 歸併排序可視為本章演算法中佔用輔助空間最多的排序演算法

2）應用比較

  1. 選取排序方法需要考慮的因素：

①　待排序的元素數目n

②　元素本身資訊量的大小

③　關鍵字的結構及其分布情況

④　穩定性的要求

⑤　語言工具的條件

⑥　存儲結構

⑦　輔助空間的大小

  1. 應用比較：

①　若n較小(<1000)，可採用直接插入排序或簡單選擇排序或冒泡。由於直接插入排序所需的記錄移動次數較簡單選擇排序的多，因而當記錄本身資訊量較大時，用簡單選擇排序較好

（1) 通常情況下，直接插入排序每趟插入都需要依次向後挪位，而簡單選擇排序只需與找到的最小位置交換位置，後者移動次數少很多

②　若文件的初始狀態已按關鍵字基本有序，則選用直接插入或冒泡排序為宜

③　若n中等大小（<=1000）,希爾排序是很好的選擇

④　若n較大（>1000）,則應採用時間複雜度為O(nlog_2(n))的排序方法:快速排序、堆排序，歸併排序

（1) 若要求排序穩定且時間複雜度為O(nlog_2(n))，則可選用歸併排序。但本章介紹的從單個記錄起進行兩兩歸併的排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後兩兩歸併

（2) 若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好（只適用於有明顯結構特徵的關鍵字，且基數排序不能對float等類型實數進行排序，故若題目要求關鍵字為實數則不能選擇基數排序）

⑤　在基於比較的排序方法中,每次比較兩個關鍵字的大小之後，僅出現兩種可能的轉移因此可以用一棵二叉樹來描述比較判定過程，由此可以證明:當文件的n個關鍵字隨機分布時，任何藉助於「比較」的排序演算法，至少需要O(nlogn)的時間

⑥　當記錄本身資訊量較大時，為避免耗費大量時間移動記錄，可用鏈表作為存儲結構，如插入、歸併、基數排序，但快排和堆排序在鏈表上難實現，可提取關鍵字建立索引表後對索引表排序

⑦　有的語言沒有提供指針及遞歸，這時歸併、快速、基數排序演算法複雜

⑧　只需得到前k小元素的順序排列可採用的排序演算法有冒泡排序，堆排序和簡單選擇排序

  1. 混合使用不同排序演算法是一種普遍的演算法改進方法
Tags:

VirMach 便宜 VPS