陳舜青

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

關(guān)鍵詞：排序算法；提高效率；復(fù)雜度

一、幾種排序算法的比較

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

交換排序：兩兩比較待排序的關(guān)鍵字，如果次序是反序的就交換，直到?jīng)]有反序的記錄為止。主要有冒泡排序和快速排序。

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

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

二、排序的穩(wěn)定性分析

如果排序前兩個相同的數(shù)字間的位置關(guān)系與排序后的位置相同，那么這種排序算法是穩(wěn)定的，反之是不穩(wěn)定的。冒泡排序和直接插入排序?qū)儆诜€(wěn)定排序；直接選擇排序、快速排序和希爾排序?qū)儆诓环€(wěn)定排序。

若排序碼是關(guān)鍵碼，則對任意待排序序列經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼不是主關(guān)鍵碼，可能具有相同關(guān)鍵碼的多個記錄。

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

三、時間復(fù)雜度和空間復(fù)雜度

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

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

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

四、排序方法的選擇

從算法實現(xiàn)來看，各種排序算法各有優(yōu)缺點，沒有絕對最優(yōu)的。使用時要根據(jù)不同情況選用，還可以將多種方法結(jié)合使用。需要考慮的因素有：待排序的記錄個數(shù)、每個記錄的大小、關(guān)鍵字的結(jié)構(gòu)和初始狀態(tài)、對排序穩(wěn)定性的要求、存儲結(jié)構(gòu)。

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

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

第二，當(dāng)排序按記錄的主關(guān)鍵字進行時，排序方法是否穩(wěn)定無關(guān)緊要；若排序按記錄的次關(guān)鍵字進行，則必須采用穩(wěn)定的排序方法。

第三，大多數(shù)排序方法采用順序表來實現(xiàn)，若記錄本身信息量較大，為避免移動記錄耗費大量時間，可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

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

五、結(jié)語

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

參考文獻：

[1]張小莉，等.數(shù)據(jù)結(jié)構(gòu)與算法（第3版）[M].北京：機械工業(yè)出版社，2014.

[2]嚴(yán)蔚敏，等.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2011.

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

[4]陳琳琳，等.數(shù)據(jù)結(jié)構(gòu)與算法（C語言版）（第3版）[M].北京：清華大學(xué)出版社，2015.