計算機(jī)程序設(shè)計中的排序問題探討

摘 要：計算機(jī)程序設(shè)計中，排序是一項非常重要的操作，其主要功能是將某一個數(shù)據(jù)元素或者是某一相關(guān)記錄的無規(guī)則序列進(jìn)行重新排列，使之成為一個參考某一關(guān)鍵字而排列的有序序列。本文首先分析計算機(jī)程序設(shè)計中排序問題之特點，其次就不同的方法展開探討，以期拋磚引玉。

關(guān)鍵詞：計算機(jī)；程序設(shè)計；排序問題

中圖分類號：TP311.1

計算機(jī)程序設(shè)計中的排序方法分類涉及到很多方面的因素，依照不同的類別可以將排序方法進(jìn)行劃分，繼而做出細(xì)致的分析探討，本文結(jié)合算法的復(fù)雜度做出具體分析，旨在了解并能夠?qū)崿F(xiàn)不同的排序算法。

1 計算機(jī)程序設(shè)計中排序問題的特點

計算機(jī)程序中排序問題具有的幾種特點分別是復(fù)雜性、不確定性、多約束性以及多目標(biāo)性。復(fù)雜性通常體現(xiàn)在計算機(jī)程序設(shè)計中需要進(jìn)行排列操作的數(shù)據(jù)或者是記錄繁雜不一，縱使會有最佳方案，但其排序方法總體而言還是比較復(fù)雜的；不確定性即排序操作進(jìn)行過程中，可能有某一數(shù)據(jù)或者是記錄需要插入，總體內(nèi)容難以確定下來，總之其中存在的種種不確定因素，決定了計算機(jī)程序設(shè)計中的排序問題具有不確定性；多約束性是指進(jìn)行排序時，會有一部分?jǐn)?shù)據(jù)資源之間可能會存在著相互制約的相互影響的關(guān)系；多目標(biāo)性即某一組雜亂無序的數(shù)據(jù)資源或者是記錄可能要同時滿足幾種不同的目標(biāo)，這就使得進(jìn)行排序時要根據(jù)不同的標(biāo)準(zhǔn)進(jìn)行操作，難免多項指標(biāo)之間出現(xiàn)沖突。

2 計算機(jī)程序設(shè)計的排序方法

2.1 冒泡排序法。冒泡排序法在計算機(jī)程序設(shè)計中進(jìn)行排序的基本思想即對相鄰的兩個元素進(jìn)行比較，比較之后將較小的那一個數(shù)據(jù)調(diào)至前面，較大的那個數(shù)據(jù)調(diào)至后面，依照這樣的思想規(guī)則對數(shù)據(jù)元素依次兩兩相比，一般情況下都會在數(shù)趟比較之后才會結(jié)束，得出想要的結(jié)果。譬如關(guān)鍵字為9 8 5 14 2的一組數(shù)據(jù)，對其進(jìn)行冒泡排序：

對冒泡法排序進(jìn)新算法分析不難發(fā)現(xiàn)，冒泡法排序只是用到了一個輔助單元，換句話說，冒泡法排序的空間復(fù)雜度為O（1），它的時間效率自然與數(shù)據(jù)的n有關(guān)，若數(shù)據(jù)元素的狀態(tài)維持不變，那么正序冒泡法的比較次數(shù)為n-1，移動的次數(shù)為0，逆序冒泡法的比較次數(shù)為n（n-1）/2，移動的次數(shù)為3n（n-1）/2，所以不難分析可知，若是保證所有待排的數(shù)據(jù)元素處在一個隨機(jī)的狀態(tài)，那么冒泡排序法的平均時間復(fù)雜度即為O（n^2）。

2.2 選擇法排序。計算機(jī)程序設(shè)計中的選擇法排序，其基本思想是在需要排序的一組數(shù)據(jù)元素之中，選取其中最小的哪一個數(shù)據(jù)元素同這組數(shù)據(jù)中最小的那個數(shù)據(jù)進(jìn)行位置交換，之后在剩下的數(shù)據(jù)元素之中選擇最小的那一個數(shù)據(jù)同這列中的第二個位置處的元素來進(jìn)行位置交換，接著再從剩下的元素中選擇最小值同第三個位置處的元素調(diào)換位置，以此類推做循環(huán)操作，直至最后的一個數(shù)據(jù)元素做出比較并調(diào)換位置為止。

對計算機(jī)程序設(shè)計中選擇排序法做出算法分析不難得知，這一排序方法的空間效率雷同于冒泡法排序，整個過程中只用到了一個輔助單元，即其空間復(fù)雜度為O（1），這一排序方法的時間效率同樣與n有關(guān)，若是正序進(jìn)行選擇法排序，那么比較的次數(shù)為n（n-1）/2，移動的次數(shù)為0，若是逆序進(jìn)行選擇法排序，則比較的次數(shù)為n（n-1）/2，移動的次數(shù)為3（n-1），同樣若是需要進(jìn)行排序操作的數(shù)據(jù)元素處在一個隨機(jī)狀態(tài)，那么其排序的平均時間復(fù)雜度是O（n^2）。

2.3 快速排序法?？焖倥判蚍ǖ恼w排序過程是首先設(shè)置出兩個指針，并且分別賦予適當(dāng)?shù)某跏贾?，根?jù)快速排序法的基本思想進(jìn)行有規(guī)則的掃描，之中還會進(jìn)行多次交替掃描方向的操作，最終若使得兩個指針相等，則表示基準(zhǔn)的最終位置得到確定，這就說明完成了一次劃分。不妨距離來說明快速排序法的排序過程，需要排序的數(shù)據(jù)分別為50、38、62、94、73、14、24、50’，那么進(jìn)行劃分排序之后的數(shù)趟排列結(jié)果則如下所示：

第一趟排序得出[24 38 14] 50 [73 94 62 50]

第二趟排序得出[14] 24 [38] 50 [50’ 62] 73 [94]

第三趟排序得出14 24 38 50 50’[62] 73 94

最后結(jié)果是 14 24 38 50 50’ 62 73 94

快速排序法最壞的情況即進(jìn)行至第n次劃分所選取的基準(zhǔn)值仍然是無序區(qū)中的最大記錄或者是最小記錄，所以不難總結(jié)出，計算機(jī)程序設(shè)計的快速排序法需要做的比較趟數(shù)是n-1趟，總的比較次數(shù)達(dá)到了一個最大值O（n^2）?；诳焖倥判蚍ㄖ兴涗浀囊苿涌偞螖?shù)小于或等于進(jìn)行比較的總次數(shù)，因此可以得出最好的時間復(fù)雜度是O（log2n）。

3 計算機(jī)程序設(shè)計中排序方法的選擇

在計算機(jī)程序設(shè)計中，對排序方法的選擇是有一定的依據(jù)的。冒泡排序法、選擇排序法和快速排序法等多種排序方法的平均時間復(fù)雜度都是同n相關(guān)聯(lián)的，因此，排序方法的選擇與n有一定的關(guān)系。當(dāng)n較小時，最佳的排序方法選擇方案是直接插入法或者是直接選擇法，主要是因為這兩種排序方法的移動的次數(shù)比較多，在記錄信息量大的時候，直接選擇法排序比較適宜。當(dāng)n比較大的時候，選用移動次數(shù)較多的排序方法自然不妥，這時應(yīng)當(dāng)采用時間復(fù)雜度較小即為O（n）的排序法，譬如快速排序法、歸并排序法或堆排序等，這三種排序方法也是稍有不同，各有利弊，當(dāng)前基于內(nèi)部排序而言，通常認(rèn)為快速排序法是最佳排序方法，因為對任意分布的關(guān)鍵字進(jìn)行排序時，快速排序法需要的平均時間最小。

除此之外的排序方法選擇根據(jù)與所給定的數(shù)值文件的初始狀態(tài)有關(guān)，若是給定關(guān)鍵字初始狀態(tài)基本呈現(xiàn)正序排列，則選擇冒泡排序法和直接插入法的排序方法最為適宜；在計算機(jī)程序設(shè)計中進(jìn)行排序方法的選擇時，有時所要排序的關(guān)鍵字是需要做出比較的，即對每兩個關(guān)鍵字做出比較后做出兩種可能的轉(zhuǎn)移，這時最恰當(dāng)?shù)呐判蚍椒槎鏄溥M(jìn)行描述的過程；在n較小的前提之下，若是所記錄的關(guān)鍵字比較少并且可以做分解時，比較排序法更容易解決問題。

4 結(jié)束語

計算機(jī)程序設(shè)計中排序問題的探討是當(dāng)今計算機(jī)領(lǐng)域中相當(dāng)重要的一個課題，不同的排序方法所能解決的問題類型自然而然不同，各有利弊，結(jié)合時間復(fù)雜度，分析排序問題的排序思想、排序方法、排序效率，總之探討出最具優(yōu)勢的排序方法是探討排序問題的最終目的。實時對計算機(jī)程序設(shè)計做出優(yōu)化，以使得計算機(jī)操作更大程度上避免無謂操作，從而降低時間復(fù)雜度，提高計算機(jī)程序運行的效率，實現(xiàn)算法設(shè)計，為我們的工作生活提供便利。

參考文獻(xiàn)：

[1]戴啟迪.關(guān)于編程排序的新方法[J].計算機(jī)光盤軟件與應(yīng)用，2011（19）：181-182.

[2]譚浩強(qiáng).C程序設(shè)計[M].北京：清華大學(xué)出版社，2004（03）：35-40.

[3]代西武.快速排序與遞歸[J].北京建筑工程學(xué)院學(xué)報，2012（11）：70.

作者簡介：張?。?975-），男，江蘇人，碩士，實驗師，研究方向：計算機(jī)應(yīng)用。

作者單位：三江學(xué)院 計算機(jī)科學(xué)與工程學(xué)院，南京 210012