數組排序方法概述

摘 要： 數組排序是程序設計的重要內容，本文主要對冒泡排序法、快速排序法、簡單選擇排序法、直接插入法進行簡單討論，并從時間復雜度、空間復雜度、穩定性方面加以論述。在這幾種方法分析、比較的基礎上，可以得知沒有一種方法是最優的，應根據實際情況進行選擇。

關鍵詞： 數組排序 算法 時間復雜度

數組排序是C語言中的一項重要內容，所謂排序就是將一組雜亂無章的數據按照大小順序排列，包括整型、實型、字符型及字符串的排序。排序的方法有很多種，常用的有交換法、選擇法、插入法。其中交換法包括冒泡排序法和快速排序法。

衡量算法的兩個重要指標是時間復雜度和空間復雜度，本文主要從時間復雜度的角度對算法進行分析。

一、交換法

1.冒泡排序法［１］

（1）冒泡排序法的基本思想

將相鄰兩個數進行比較，若滿足條件升序（或降序）時，就不需要交換，反之，就要交換。例如：對于一個數組a［n］進行降序排列運用冒泡法分析如下：首先把a與a進行比較，若a＜a則交換，反之不交換；其中i=1，2，…n-1。進行第一回比較后就把最大的數放在a的位置；第二回比較就從a開始比較，比較的結果就把次最大的數放在a的位置上。如此進行下去，可以推知，對n個數要比較n-1回，才能使這n個數按大小順序排列。在第一回要進行兩個數之間的比較，共比較n-1次，第二回比較n-2次……第n-1回比較1次。

（2）用C語言實現算法

void fun(int a，int n)

{int i，j，t;

for(j=0;j＜n-1;j++)/*進行n-1次循環，實現n-1趟比較*/

for(i=0;i＜n-j;i++)/*在每一趟中進行n-j次比較*/

if(a［i］＜a［i+1］) /*相鄰兩元素比較*/

{t=a［i］; a［i］=a［i+1］; a［i+1］=t;} }

（3）算法分析

②空間復雜度。因為只用一個輔助單元，所以為O(1)。

③穩定性。從排序過程來看，要對相鄰元素交換，因此是穩定的排序方法。

2.快速排序［２］

（1）快速排序的基本思想

任取待排序列中的元素作為基準(一般取第一個元素)，通過一趟排序，將待排序元素分為左右兩個序列，左子序列元素的關鍵字均小于或等于基準元素的關鍵字，右子序列的關鍵字都大于基準元素的關鍵字，然后分別對兩個子序列繼續進行排序，直至整個序列有序。

例如數組a有n元素要對它進行排序，low為數組的低端下標，high為數組的高端下標，取a［low］為基準元素i的初值為low，j的初值為high。為了實現一次劃分，首先讓j從它的初值開始一次向前取值，并將每一元素a［j］的關鍵字同a［i］進行比較，直到a［j］的關鍵字小于a［i］的關鍵字時交換a［j］與a［i］的值，使得關鍵字較小交換到左區間中。然后讓i從i+1開始，依次向后取值，并使每一元素a［i］的關鍵字同a［j］的關鍵字進行比較，當a［i］的關鍵字大于a［j］的關鍵字時，交換a［i］與a［j］的值，使得關鍵字較大的元素交換到右區間中。接著讓i從j-1開始，依次向前取值，重復此過程，直到i等于j為止，此位置就是基準元素存放的位置，完成一次規劃過程。劃分后，待排序列被分為兩個子序列，左子序列的元素的關鍵字均小于基準元素的關鍵字，右子序列元素的關鍵字均大于等于基準元素的關鍵字。重復以上過程，直到整個序列有序。

（2）用C語言實現算法

void fun(int a，int low，high)

{ int i=low，j=high;

int t=a［low］；/*取第一個元素為基準元素*/

while(i＜j){

while(i＜jt＜＝a［j］)j--；/*在數組右端掃描*/

if(i＜j) {a［i］=a［j］； i++；}

while(i＜ja［i］＜t)i++；/*在數組的左端掃描*/

if(i＜j) { a［j］=a［i］；j--；} }

a［i］=t；

if(low＜i) fun(a，low，i-1)；

if(i＜high) fun(a，j+1，high)；}

（3）算法分析［３］

③穩定性。從排序結果可以看出：在排序過程中涉及不相鄰元素間的交換，所以快速排序是一種不穩定的排序方法。

二、選擇排序

1.簡單選擇排序方法［４］

（1）簡單選擇排序的基本思想

對n個待排序的數列a，a，…，a［n-1］；進行n-1回掃描，第i回掃描數組a［n］中的n-i-1個元素，并從中選出最小關鍵字的元素與第i個元素交換位置(1≤i≤n-1)。重復這樣n-1回掃描，最后得到的序列就是有序的。

例如：數組a［n］要按升序排列，第一回是a與a，a，…，a［n-1］相比較，找出最小的元素放在a的位置，第二回就是a與a，a…，a［n-1］比較，把最小的元素放在a的位置，在第i回就是a［i-1］與a［i］，a［i+1］，…，a［n-1-i］相比較，把最小的元素放在a［i-1］中，直到整個數組有序。

（2）算法實現

void fun(int a，int n)

{int i，j，k，t；

for (i=0；i＜n-1；i++) { k=i；

for(j=i+1；j＜n；j++)

if(a［j］＜a［k］)k=j； t=a［k］；a［k］=a［i］；a［i］=t；}

（3）算法分析

②空間復雜度。在排列過程中需要一個輔助空間，所以空間復雜度為O(1)。

③穩定性。相同的關鍵字的元素在排序后其前后順序有改變的可能性，所以簡單選擇排序是不穩定的排序方法。

三、插入法

1.直接插入排序［５］的基本思想

順序地把待排序的元素按其關鍵字值的大小插入到已經排列有序的子集合的合適的位置上，使子集合中的數據元素個數逐漸從只有一個不斷的增加。當子集合等于集合時，算法結束。

例如：設n個元素的數組a，初始時子集合a有序，第一次循環只要比較a和a，若a＜a，說明有序直接把a插到a后面，否則把a插到a前面這樣子集合就增大為2，然后把a在插入前面的子集合中，使子集合也有序，這時子集合增大為3，重復上述過程，直到把a［n-1］插入到前面的子集合中，這時子集合等于集合，算法結束。

2.算法實現

void fun (int a，int n)

{int i， j，t；for (i=0；i＜n-1；i++)

{ t=a［i+1］；j=i；

while (j＞－1t＜a［j］)

{ a［j+1］=a［j］；j--； }

a［j+1］=t；} }

3.算法分析

(1)時間復雜度

(2)空間復雜度

在排序的過程中要用到一個輔助空間，所以空間復雜度為O(1)。

(3)穩定性

在排序過程中相同的關鍵字的元素在排序后順序保持不變，所以直接插入排序是一種穩定的排序方法。

四、各種排序方法的性能比較

五、選擇排序方法的規則［６］

1.影響排序方法的因素

待排序的元素的數目、記錄本身信息量的大小、排序方法的穩定性、輔助空間的大小。

2.在選擇排序方法時

首先應考慮排序的穩定性，其次考慮待排序記錄數n的大小，從而選取合適的排序方法。

參考文獻：

［1］譚浩強.C語言程序設計（第三版）.清華大學出版社，P134，135.

［2］張伍榮，王軍武.全國計算機等級考試實用應試教程—二級公共基礎知識.電子工業出版社.

［3］朱戰立.數據結構——使用C語言（第三版）.西安交通大學出版社，P249，250.

［4］李可清.數據結構——C語言描述.華中科技大學出版社，P237，238.

［5］朱戰立.數據結構——使用C語言（第三版）.西安交通大學出版社，P236-239.

［6］欺慶巴拉.數據結構（C語言描述）.中國水利水電出版社，P214，215.