一種冒泡排序的改進算法

廖志文

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

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

中圖分類號：TP301 文獻標識碼：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

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

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

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

1.1 排序思想

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

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

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

依此類推，有n個元素，每趟排序?qū)斍按判蛟兀ǔ艘呀?jīng)“沉底”的元素）最大值“沉底”，則需要n-1趟排序。

1.2 算法實現(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 時間復(fù)雜度

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

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

2 冒泡排序存在的問題

2.1 問題提出

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

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

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

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

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

通常地，設(shè)結(jié)構(gòu)體由r個內(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ù)值數(shù)據(jù)交換值，直接用賦值語句；字符串元素交換值，調(diào)用庫函數(shù)strcpy；如果是結(jié)構(gòu)體等構(gòu)造數(shù)據(jù)類型，則交換每個結(jié)構(gòu)體內(nèi)部變量。因此，在算法實現(xiàn)交換功能時不同的數(shù)據(jù)類型元素實現(xiàn)方法不一致。這顯示了冒泡排序算法的函數(shù)復(fù)用程度低。

3 一種改進的冒泡排序算法

3.1 冒泡排序算法的改進思想

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

傳統(tǒng)冒泡排序之所以出現(xiàn)復(fù)雜度增加、算法復(fù)用性低的特點，是因為相鄰的兩個數(shù)組元素而發(fā)生逆序時，交換的是兩個元素的值，而不同的數(shù)據(jù)類型的數(shù)組交換值的方法不同。

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

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

typedef struct

{char sno[8]；

char sname[20]；

char sex[3]；

unsigned int age；

unsigned int classno；

float grade；

}STU；

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

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）

{//交換下標的方式對于

//不同的數(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ù)組中的下標

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ù)元素在正序序列中的下標打印出排序后的序列。

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é)束語

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

參考文獻：

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

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