算法和數據結構~排序算法 - lori－IT工程師數位筆記本

文章出處

排序算法種類

排序是指將元素集合按照規定的順序排列。通常有兩種排序方法，升序排列和降序排列。例如，對整數集{5,2,7,1}進行升序排列，結果為{1,2,5,7}，對其進行降序排列結果為{7,5,2,1}。總的來說，排序的目的是使數據能夠以更有意義的形式表現出來。雖然排序最顯著的應用是排列數據以顯示它，但它往往可以用來解決其他的問題，特別是作為某些已成型算法的一部分。

總的來說，排序算法分為兩大類：比較排序和線性時間排序。比較排序依賴于比較和交換來將元素移動到正確的位置上。令人驚訝的是，并不是所有的排序算法都依賴于比較。對于那些確實依賴于比較來進行排序的算法來說，它們的運行時間往往不可能小于O(nlgn)。對于線性時間排序，從它的名字就可以看出，它的運行時間往往與它處理的數據元素個數成正比，即為O(n)。遺憾的是，線性時間排序依賴于數據集合中的某些特征，所以我們并不是在所有的場合都能夠使用它。某些排序算法只使用數據本身的存儲空間來處理和輸出數據（這些稱為就地排序），而有一些則需要額外的空間來處理和輸出數據（雖然可能最終結果還是會拷貝到原始的內存空間中）。
搜索就是在一個數據集中找到一個元素的位置，它可用于任何任務中。一種最簡單的、不需要費任何腦筋的搜索方法是：簡單地從數據集的一端查找到另一端。這就是所謂的線性搜索。通常，線性搜索用在那些對隨機訪問支持得不太好的數據結構中，例如：鏈表（見第5章）。另一種方法是使用二分查找，這會在本章中介紹。還有一些搜索方法專門用于特定的數據結構，例如哈希表。

插入排序

插入排序雖然不是最有效的排序方法，但它簡單，并且不需要額外的存儲空間。其最佳應用場景是對一個小的數據集合進行遞增排序。

描述　利用插入排序將數組data中的元素進行排序。data中元素的個數由size決定。而每個元素的大小由esize決定。函數指針compare會指向一個用戶定義的函數來比較元素大小。在遞增排序中，如果key1＞key2，函數返回1；如果key1=key2，函數返回0；如果 key1＜key2，函數返回-1。在遞減排序中，返回值相反。當issort返回時，data包含已排序的元素。
復雜度　O（n2），n為要排序的元素的個數。

快速排序

在一般情況下，一致認為快速排序是最好的一種排序算法，而且不需要額外的存儲空間。其最佳應用場合是應用于大型數據集。

描述　利用快速排序將數組data中的元素進行排序。數組中的元素個數由size決定。而每個元素的大小由esize決定。參數i和k定義當前進行排序的兩個部分，其值分別初始化為0和size-1。函數指針compare會指向一個用戶定義的函數來比較元素大小。其函數功能與issort中描述的一樣。當qksort返回時，data包含已排序的元素。
復雜度　O（nlg n），n為要被排序的元素的個數。

歸并排序

歸并排序基本上與快速排序算法的性能相同，但它需要使用兩倍于快速排序的存儲空間。而具有諷刺意味的是，其最佳應用場合是在超大數據集中，因為歸并排序的原理就是對原始的亂序數據不斷進行對半分割。

描述　利用歸并排序將數組data中的元素進行排序。數組中的元素個數由size決定。而每個元素的大小由esize決定。參數i和k定義當前進行排序的兩個部分，其值分別初始化為0和size-1。函數指針compare會指向一個用戶定義的函數來比較元素大小。其函數功能與issort中描述的一樣。當mgsort返回時，data中包含已排序的元素。
復雜度　O（nlg n），n為要排序的元素的個數。