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

關鍵詞：計算機；程序設計；排序問題

中圖分類號：TP311.1

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

1 計算機程序設計中排序問題的特點

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

2 計算機程序設計的排序方法

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

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

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

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

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

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

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

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

最后結果是 14 24 38 50 50’ 62 73 94

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

3 計算機程序設計中排序方法的選擇

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

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

4 結束語

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

參考文獻：

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

[2]譚浩強.C程序設計[M].北京：清華大學出版社，2004（03）：35-40.

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

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

作者單位：三江學院 計算機科學與工程學院，南京 210012