常用排序算法的研究

陳舜青

摘要：現實生活中常常需要從大量信息中查找需要的信息。為使查找更加有效和便捷，需要按特定次序對信息預先排序后存儲，如按字母排列、分門別類存放圖書文獻。排序廣泛應用于數據處理、情報檢索、商業金融等領域。排序是程序設計中處理數據最基本的算法之一。本文就常用排序方法討論其基本思想、實現過程，對排序的穩定性以及時間復雜度和空間復雜度進行了分析。

關鍵詞：排序算法；提高效率；復雜度

一、幾種排序算法的比較

插入排序：每次把一個待排序的記錄插入到已排序的序列中，直到所有的記錄都插入為止。主要有直接插入排序和希爾排序，希爾排序的執行時間取決于增量序列。

交換排序：兩兩比較待排序的關鍵字，如果次序是反序的就交換，直到沒有反序的記錄為止。主要有冒泡排序和快速排序。

選擇排序：每一次從待排序的記錄中找出一個最小值放最前面，直到所有的記錄都排好。

通過實例操作驗證，在大數據下，排序時間從多到少的次序依次為：冒泡排序、選擇排序、插入排序、希爾排序、堆排序、快速排序。

二、排序的穩定性分析

如果排序前兩個相同的數字間的位置關系與排序后的位置相同，那么這種排序算法是穩定的，反之是不穩定的。冒泡排序和直接插入排序屬于穩定排序；直接選擇排序、快速排序和希爾排序屬于不穩定排序。

若排序碼是關鍵碼，則對任意待排序序列經排序后得到的結果是唯一的；若關鍵碼不是主關鍵碼，可能具有相同關鍵碼的多個記錄。

排序一般希望算法比較簡單，占用輔助空間較小，運行時間短。每一種算法都有自己的優缺點，適合在某些特定的環境下使用。

三、時間復雜度和空間復雜度

評價一種排序方法的好壞，主要通過時間代價和空間代價衡量。排序過程中基本操作是關鍵碼和記錄的移動，所以時間代價是以關鍵碼的比較次數和記錄的移動次數衡量的，記錄的數量和大小、排序表的大小、原始序列的排序狀態都會影響排序時間。

直接插入排序，空間復雜度為O（1），時間復雜度為O（n2）；折半插入排序空間復雜度為O（1），定位一個關鍵碼的位置需要比較次數至多為log2（n+1）次，時間復雜度為O（nlog2n）。折半插入排序只能減少關鍵字間的比較次數，而移動記錄的次數和直接插入排序相同，故時間復雜度仍為O（n2）。這也是一種穩定排序方法，只適合順序存儲的排序表。交換排序的基本思想：通過排序表中兩個記錄關鍵碼的比較，若與排序要求相逆，則將兩者交換，直到沒有反序的記錄為止。

盡管快速排序的最壞時間為O（n2），但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快的，也因此稱為快速排序，它的平均時間復雜度為O（nlgn）。

四、排序方法的選擇

從算法實現來看，各種排序算法各有優缺點，沒有絕對最優的。使用時要根據不同情況選用，還可以將多種方法結合使用。需要考慮的因素有：待排序的記錄個數、每個記錄的大小、關鍵字的結構和初始狀態、對排序穩定性的要求、存儲結構。

待排序記錄個數n較小時，n2和nlog2n區別不大，可選用簡單的排序方法。排序方法的選擇主要根據以下情況來考慮：

第一，最適用于n值很大而關鍵字較小的序列，使用條件比較嚴格，需要知道各級關鍵字的取值范圍，只適合整數和字符這類有明顯特征的關鍵字。

第二，當排序按記錄的主關鍵字進行時，排序方法是否穩定無關緊要；若排序按記錄的次關鍵字進行，則必須采用穩定的排序方法。

第三，大多數排序方法采用順序表來實現，若記錄本身信息量較大，為避免移動記錄耗費大量時間，可采用鏈式存儲結構。

對常規排序方法適當改進可以提高效率，比如：雞尾酒排序，是對冒泡排序的改進，效率有所提高，也叫定向冒泡排序。此算法與冒泡排序的不同處是先從低到高，再從高到低，最差時間復雜度O（n2），最優時間復雜度O（n），平均時間復雜度O（n2），所需輔助空間O（1），屬于穩定排序。而冒泡排序僅從低到高逐個比較序列中的元素。

五、結語

排序主要是用來檢索、選擇、評估數據，把無序的數據或記錄序列重新組織成按關鍵字排列的有序序列。影響排序速度的因素有多種，待排元素的應用領域、初始狀態、數據的多少和大小等。根據不同情況靈活選擇排序算法，才能提高排序速度、程序執行效率。隨著對排序算法研究的深入，一定會有更多的優秀算法及理論被應用于實際工作中。

參考文獻：

[1]張小莉，等.數據結構與算法（第3版）[M].北京：機械工業出版社，2014.

[2]嚴蔚敏，等.數據結構（C語言版）[M].北京：清華大學出版社，2011.

[3]連順金.快速排序的一種改進算法[J].三明學院學報，2009，26（4）.

[4]陳琳琳，等.數據結構與算法（C語言版）（第3版）[M].北京：清華大學出版社，2015.