數(shù)組排序方法概述

摘 要： 數(shù)組排序是程序設(shè)計(jì)的重要內(nèi)容，本文主要對(duì)冒泡排序法、快速排序法、簡(jiǎn)單選擇排序法、直接插入法進(jìn)行簡(jiǎn)單討論，并從時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性方面加以論述。在這幾種方法分析、比較的基礎(chǔ)上，可以得知沒有一種方法是最優(yōu)的，應(yīng)根據(jù)實(shí)際情況進(jìn)行選擇。

關(guān)鍵詞： 數(shù)組排序 算法 時(shí)間復(fù)雜度

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

衡量算法的兩個(gè)重要指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度，本文主要從時(shí)間復(fù)雜度的角度對(duì)算法進(jìn)行分析。

一、交換法

1.冒泡排序法［１］

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

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

（2）用C語(yǔ)言實(shí)現(xiàn)算法

void fun(int a，int n)

{int i，j，t;

for(j=0;j＜n-1;j++)/*進(jìn)行n-1次循環(huán)，實(shí)現(xiàn)n-1趟比較*/

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

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

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

（3）算法分析

②空間復(fù)雜度。因?yàn)橹挥靡粋€(gè)輔助單元，所以為O(1)。

③穩(wěn)定性。從排序過程來看，要對(duì)相鄰元素交換，因此是穩(wěn)定的排序方法。

2.快速排序［２］

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

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

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

（2）用C語(yǔ)言實(shí)現(xiàn)算法

void fun(int a，int low，high)

{ int i=low，j=high;

int t=a［low］；/*取第一個(gè)元素為基準(zhǔn)元素*/

while(i＜j){

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

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

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

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）算法分析［３］

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

二、選擇排序

1.簡(jiǎn)單選擇排序方法［４］

（1）簡(jiǎn)單選擇排序的基本思想

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

例如：數(shù)組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］中，直到整個(gè)數(shù)組有序。

（2）算法實(shí)現(xiàn)

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）算法分析

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

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

三、插入法

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

順序地把待排序的元素按其關(guān)鍵字值的大小插入到已經(jīng)排列有序的子集合的合適的位置上，使子集合中的數(shù)據(jù)元素個(gè)數(shù)逐漸從只有一個(gè)不斷的增加。當(dāng)子集合等于集合時(shí)，算法結(jié)束。

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

2.算法實(shí)現(xiàn)

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)時(shí)間復(fù)雜度

(2)空間復(fù)雜度

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

(3)穩(wěn)定性

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

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

五、選擇排序方法的規(guī)則［６］

1.影響排序方法的因素

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

2.在選擇排序方法時(shí)

首先應(yīng)考慮排序的穩(wěn)定性，其次考慮待排序記錄數(shù)n的大小，從而選取合適的排序方法。

參考文獻(xiàn)：

［1］譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)（第三版）.清華大學(xué)出版社，P134，135.

［2］張伍榮，王軍武.全國(guó)計(jì)算機(jī)等級(jí)考試實(shí)用應(yīng)試教程—二級(jí)公共基礎(chǔ)知識(shí).電子工業(yè)出版社.

［3］朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)——使用C語(yǔ)言（第三版）.西安交通大學(xué)出版社，P249，250.

［4］李可清.數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言描述.華中科技大學(xué)出版社，P237，238.

［5］朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)——使用C語(yǔ)言（第三版）.西安交通大學(xué)出版社，P236-239.

［6］欺慶巴拉.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）.中國(guó)水利水電出版社，P214，215.