廖志文

摘要：傳統(tǒng)的冒泡排序幾乎都是基于基本數(shù)據(jù)類型，通過比較相鄰的兩個(gè)元素的大小，如果發(fā)生逆序，則交換兩個(gè)元素的值。當(dāng)待排序元素是構(gòu)造類型時(shí)，通過交換兩個(gè)元素的值，時(shí)間復(fù)雜度必然會增加；另一方面，基本數(shù)據(jù)類型變量與構(gòu)造類型變量的賦值方式有很大的區(qū)別，因此傳統(tǒng)的冒泡排序算法復(fù)用性低。針對傳統(tǒng)冒泡排序的不足，該文提出了一種冒泡排序的改進(jìn)算法。改進(jìn)后的冒泡排序?qū)τ谠厥墙Y(jié)構(gòu)體等構(gòu)造類型時(shí)時(shí)間復(fù)雜度明顯降低，且函數(shù)復(fù)用性提高。

關(guān)鍵詞：冒泡排序；改進(jìn)算法；時(shí)間復(fù)雜度；函數(shù)復(fù)用性

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）18-4258-04

An Improved Algorithm of Bubble Sort

LIAO Zhi-wen

（Computer Science and Technology Department， Zhuhai College of Jilin University， Zhuhai 519041，China）

Abstract： The traditional bubble sort is almost based on basic data types. By comparing the size of two adjacent elements， if the reverse occurs， the values of the two elements are exchanged. When the elements to be sorted are of constructed type， through the exchange value of the two elements， the time complexity surely bounds to increase； On the other hand， because the assigned way of basic data type is different from that of constructed types， therefore， it will lower reusability of the traditional bubble sort algorithm. For the Shortcoming of the traditional bubble sort， this paper presents an improved bubble sort algorithm. The improved bubble sort algorithm significantly reduces the time complexity and improved reusability when the elements are of constructed data types.

Key words： bubble sort；improved algorithm；time complexity；function reusability

一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的時(shí)間和空間資源。設(shè)計(jì)出復(fù)雜性盡可能低的算法是在設(shè)計(jì)算法時(shí)追求的一個(gè)重要目標(biāo)[1]。算法是解決問題的一種方法或一個(gè)過程。在C語言中，算法都是通過函數(shù)實(shí)現(xiàn)的。函數(shù)是C語言源程序的基本構(gòu)成模塊，是一段可以重復(fù)調(diào)用的、功能相對獨(dú)立完整的程序段[2]。函數(shù)的復(fù)用性是判斷一個(gè)函數(shù)設(shè)計(jì)優(yōu)良的重要特征。

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的常用的較簡單的排序算法。如何設(shè)計(jì)出復(fù)雜度盡可能低且函數(shù)復(fù)用性高的算法是算法效率和通用性的關(guān)鍵內(nèi)容。

1 傳統(tǒng)的冒泡排序

1.1 排序思想

假設(shè)數(shù)組有n個(gè)數(shù)組元素，將這n個(gè)元素按升序進(jìn)行排序。從下標(biāo)為0的元素開始，比較相鄰的兩個(gè)元素的大小，如果前面的元素大于后面的元素，在交換這兩個(gè)元素的值。

第一趟，從下標(biāo)為0的元素到下標(biāo)為n-1的元素，依次比較相鄰的元素大小，如果前面元素比后面元素大，則交換元素值。一趟下來，最大的元素“沉底”。

第二趟，從下標(biāo)為0的元素到下標(biāo)為n-2的元素，依次比較相鄰的元素大小，如果前面元素比后面元素大，則交換元素值。一趟下來，第二大的元素“沉底”。

依此類推，有n個(gè)元素，每趟排序?qū)?dāng)前待排序元素（除了已經(jīng)“沉底”的元素）最大值“沉底”，則需要n-1趟排序。

1.2 算法實(shí)現(xiàn)

void bubble_sort（int b[]，int n）

{int i，j，t；

for （i = 1； i < 8； i++）

{for （j = 0； j < 8 - i； j++）

{if （b[j] > b[j+1]）

{t=b[j]；

b[j]=b[j+1]；

b[j+1]=t；

}}//for

}//for

}

1.3 時(shí)間復(fù)雜度

若待排序數(shù)組的元素初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵詞比較次數(shù)C和記錄移動次數(shù)M均達(dá)到最小值：Cmin=n1， Mmin=0。因此，冒泡排序最好情況下的時(shí)間復(fù)雜度為O（n）。

若待排序數(shù)組的元素初始狀態(tài)是正序的，需要n-1趟排序。每趟需要進(jìn)n-i次關(guān)鍵詞的比較（i為已“沉底”的元素個(gè)數(shù)），若發(fā)生逆序，必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值：Cmax=n（n-1）/2 ，Mmax=3n（n-1）/2=O（n2）。冒泡排序的最壞時(shí)間復(fù)雜度為O（n2）。綜上，因此冒泡排序總的平均時(shí)間復(fù)雜度為O（n2） 。endprint

2 冒泡排序存在的問題

2.1 問題提出

制作一份按學(xué)生成績排名次的表格。假如待排序的學(xué)生人數(shù)為30個(gè)，每個(gè)學(xué)生包括學(xué)號，姓名，性別，年齡，所屬班級及成績信息?，F(xiàn)在要求將10個(gè)學(xué)生記錄按成績的降序排序。

用傳統(tǒng)的冒泡排序算法實(shí)現(xiàn)按成績降序排序的思想是，定義一個(gè)學(xué)生的結(jié)構(gòu)體數(shù)據(jù)類型，定義一個(gè)學(xué)生結(jié)構(gòu)體類型的數(shù)組，用來存放學(xué)生信息。比較相鄰的兩個(gè)學(xué)生的成績，如果前一個(gè)學(xué)生的成績小于后面的成績，則交換兩個(gè)學(xué)生記錄。2.2 算法實(shí)現(xiàn)

#define NUM XXX // NUM表示學(xué)生人數(shù)

typedef struct

{char sno[8]；

char sname[20]；

char sex[3]；

unsigned int age；

unsigned int classno；

float grade；

}STU；

void bubble_sort（STU b[]，int c[]）

{int i，j，t；

STU temp；

for （i = 1； i < NUM； i++）

{flag=0；

for （j = 0； j < NUM - i； j++）

{if （b[j].grade > b[j+1].grade）

{//以下是結(jié)構(gòu)體內(nèi)部變量交換值

strcpy（temp.sno，b[j].sno）；

strcpy（b[j].sno，b[j+1].sno）；

strcpy（b[j+1].sno，temp.sno）；

strcpy（temp.sname，b[j].sname）；

strcpy（b[j].sname，b[j+1].sname）；

strcpy（b[j+1].sname，temp.sname）；

strcpy（temp.sex，b[j].sex）；

strcpy（b[j].sex，b[j+1].sex）；

strcpy（b[j+1].sex，temp.sex）；

temp.age=b[j].age；

b[j].age=b[j+1].age；

b[j+1].age=temp.age；

temp.classno=b[j].classno；

b[j].classno=b[j+1].classno；

b[j+1].classno=temp.classno；

temp.grade=b[j].grade；

b[j].grade=b[j+1].grade；

b[j+1].grade=temp.grade；

flag=1；

}}//for

}//for

}

2.3 時(shí)間復(fù)雜度增加

若待排序數(shù)組的元素初始狀態(tài)是正序，則構(gòu)造數(shù)據(jù)類型的數(shù)組元素比較次數(shù)和交換次數(shù)和基本數(shù)據(jù)類型相同。即，Cmin=n-1， Mmin=0。

若待排序數(shù)組元素初始狀態(tài)時(shí)逆序，則構(gòu)造數(shù)據(jù)類型的數(shù)組元素比較次數(shù)和基本數(shù)據(jù)類型相同，但交換次數(shù)和基本數(shù)據(jù)類型不同。

比如上述的實(shí)例，按成績的降序?qū)W(xué)生記錄重新排序。由于學(xué)生的信息是結(jié)構(gòu)體類型的，結(jié)構(gòu)體可以有多種不同數(shù)據(jù)類型的變量組合定義。在相鄰的兩個(gè)學(xué)生成績發(fā)生逆序時(shí)，交換的不僅僅是成績，而是整個(gè)學(xué)生記錄。學(xué)生記錄結(jié)構(gòu)體定義了學(xué)號，姓名，性別，年齡，所在班級和成績6個(gè)不同類型的內(nèi)部變量。則在學(xué)生記錄發(fā)生交換時(shí)，同時(shí)要交換這6個(gè)變量的值。交換一對變量的值用三個(gè)賦值語句，因此，交換兩個(gè)學(xué)生記錄的順序要發(fā)生18個(gè)賦值運(yùn)算。而且不同的數(shù)據(jù)類型賦值方式是不同的，比如對于字符數(shù)組型變量，它的賦值語句用strcpy函數(shù)實(shí)現(xiàn)交換，它的交換效率比數(shù)值交換要低，即時(shí)間復(fù)雜度增加。

通常地，設(shè)結(jié)構(gòu)體由r個(gè)內(nèi)部變量組合定義而成，則對于初始狀態(tài)是逆序的數(shù)組元素，需要交換的次數(shù)Mmax=3rn（n-1）/2。構(gòu)造數(shù)據(jù)類型的交換次數(shù)至少是基本數(shù)據(jù)類型的r倍。

2.4 算法復(fù)用性低

由于傳統(tǒng)的冒泡排序發(fā)生逆序時(shí)，交換的是兩個(gè)元素的值。數(shù)值數(shù)據(jù)交換值，直接用賦值語句；字符串元素交換值，調(diào)用庫函數(shù)strcpy；如果是結(jié)構(gòu)體等構(gòu)造數(shù)據(jù)類型，則交換每個(gè)結(jié)構(gòu)體內(nèi)部變量。因此，在算法實(shí)現(xiàn)交換功能時(shí)不同的數(shù)據(jù)類型元素實(shí)現(xiàn)方法不一致。這顯示了冒泡排序算法的函數(shù)復(fù)用程度低。

3 一種改進(jìn)的冒泡排序算法

3.1 冒泡排序算法的改進(jìn)思想

基于傳統(tǒng)的冒泡排序，針對不同的數(shù)據(jù)類型，會出現(xiàn)時(shí)間復(fù)雜度增加、算法復(fù)用性低的不足，提出了一種冒泡排序的改進(jìn)算法。

傳統(tǒng)冒泡排序之所以出現(xiàn)復(fù)雜度增加、算法復(fù)用性低的特點(diǎn)，是因?yàn)橄噜彽膬蓚€(gè)數(shù)組元素而發(fā)生逆序時(shí)，交換的是兩個(gè)元素的值，而不同的數(shù)據(jù)類型的數(shù)組交換值的方法不同。

因此，改進(jìn)的冒泡排序當(dāng)相鄰的兩個(gè)元素發(fā)生逆序時(shí)，不是交換兩個(gè)元素的值，而是交換這兩個(gè)元素在當(dāng)前數(shù)組中的下標(biāo)。其實(shí)，只需要記錄每個(gè)元素在當(dāng)前數(shù)組中的下標(biāo)，即根據(jù)元素大小確定其在數(shù)組中的位置。改進(jìn)的算法增加了一個(gè)和待排序數(shù)組長度一樣的輔助數(shù)組，，初始值為待排序各元素在數(shù)組中的下標(biāo)。當(dāng)相鄰的兩個(gè)元素發(fā)生逆序時(shí)，交換元素的下標(biāo)。最終，根據(jù)每個(gè)元素在數(shù)組中的下標(biāo)，打印排序后的元素序列。由于交換的是下標(biāo)，因此，不同的數(shù)據(jù)類型的元素交換方式不會發(fā)生改變，算法的復(fù)用性高。而且，交換下標(biāo)只需要常數(shù)級時(shí)間，時(shí)間復(fù)雜度不會因?yàn)閿?shù)據(jù)類型的復(fù)雜而增加。endprint

3.2 改進(jìn)的冒泡排序算法的實(shí)現(xiàn)

typedef struct

{char sno[8]；

char sname[20]；

char sex[3]；

unsigned int age；

unsigned int classno；

float grade；

}STU；

//c[]保存每個(gè)數(shù)組元素在正序序列中的下標(biāo)

void bubble_sort（STU b[]，int c[]）

{int flag；

int i，j，t；

for （i = 1； i < NUM； i++）

{flag=0；

for （j = 0； j < NUM - i； j++）

{if （b[c[j]].grade > b[c[j+1]].grade）

{//交換下標(biāo)的方式對于

//不同的數(shù)據(jù)類型是完全可復(fù)用的

t=c[j]；

c[j]=c[j+1]；

c[j+1]=t；

flag=1；

}}//for

if （flag==0）

{break；

}}//for

}

3.3 測試程序

void main（）

{// NUM為學(xué)生人數(shù)符號常量

STU students[NUM]；

// index為數(shù)據(jù)a中元素依次在數(shù)組中的下標(biāo)

int index[NUM]；

int i；

for （i=0；i

{index[i]=i；

}

for （i=0；i

{printf（"please input the %4d student information"，i）；

printf（"＼nsno："）；

scanf（"%s"，students[i].sno）；

printf（"＼nsname："）；

scanf（"%s"，students[i].sname）；

fflush（stdin）；

printf（"＼nsex："）；

scanf（"%s"，students[i].sex）；

printf（"＼nage："）；

scanf（"%d"，&（students[i].age））；

printf（"＼nclassno："）；

scanf（"%d"，&（students[i].classno））；

printf（"＼ngrade："）；

scanf（"%f"，&（students[i].grade））；

}

bubble_sort（students，index）；

printf（"the sorted students order by grade：＼n"）；

printf（"sno， sname， sex， age， classno， grade＼n"）；

for （i=0；i

{ // 根據(jù)元素在正序序列中的下標(biāo)打印出排序后的序列。

printf（"%s， "，students[index[i]].sno）；

printf（"%s， "，students[index[i]].sname）；

printf（"%s， "，students[index[i]].sex）；

printf（"%d， "，students[index[i]].age）；

printf（"%d， "，students[index[i]].classno）；

printf（"%4.1f＼n"，students[index[i]].grade）；

}}

4 結(jié)束語

本文提出的冒泡排序的改進(jìn)算法是對傳統(tǒng)的冒泡排序在算法通用性即基本數(shù)據(jù)類型向構(gòu)造類型上的擴(kuò)展，然后發(fā)現(xiàn)傳統(tǒng)冒泡排序在時(shí)間復(fù)雜度上會隨著待排序元素的數(shù)據(jù)類型不同而增加、算法的函數(shù)復(fù)用性低的不足。通過增加一個(gè)輔助數(shù)組，初始值為待排序各元素在數(shù)組中的下標(biāo)。當(dāng)相鄰的兩個(gè)元素發(fā)生逆序時(shí)，交換元素的下標(biāo)。排序完成后，輔助數(shù)組中各元素值即初始數(shù)組在有序序列中的位置。這種通過增加空間資源有效地提高了時(shí)間復(fù)雜度和算法的復(fù)用性。

參考文獻(xiàn)：

[1] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2001.

[2] 王敬華，林萍，張清國.C語言程序設(shè)計(jì)教程[M].北京：清華大學(xué)出版社，2009.