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

楊曉明

（西安翻譯學(xué)院,陜西西安,710105）

0 引言

排序(Sorting)是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。常用的內(nèi)部排序算法有選擇排序、直接插入排序、冒泡排序、快速排序等，其中冒泡排序是最基本最常用的排序算法之一。

1 冒泡排序

冒泡排序的基本思想是：總是對(duì)相鄰的兩個(gè)元素進(jìn)行比較，如果不滿足規(guī)定的順序（升序或降序），則二者進(jìn)行交換，直到所有的元素都滿足規(guī)定的順序?yàn)橹埂?/p>

執(zhí)行過程分析（以升序排序?yàn)槔菏紫葘⒌谝粋€(gè)關(guān)鍵字與第二個(gè)關(guān)鍵字進(jìn)行比較，若為逆序（即r[0].key＞ r[1].key），則將兩個(gè)記錄交換之，然后比較第二個(gè)關(guān)鍵字和第三個(gè)關(guān)鍵字。依次類推，直至第n-1個(gè)關(guān)鍵字和第n個(gè)關(guān)鍵字進(jìn)行比較為止，完成了冒泡排序第一趟，關(guān)鍵字最大的記錄被安置在最后一個(gè)位置上。然后進(jìn)行第二趟排序，對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，使關(guān)鍵字次大的記錄放在了倒數(shù)第二個(gè)位置上，一般地，若有n個(gè)記錄，則需要進(jìn)行n-1趟排序，其中第i趟冒泡排序需要相鄰元素（r[i].key與r[i+1].key）對(duì)比交換n-i次。

例如：

初始關(guān)鍵字：7 3 8 5 9 6

第一次：7 3 8 5 9 6

第二次：3 7 8 5 9 6

第三次：3 7 8 5 9 6

第四次：3 7 5 8 9 6

第五次：3 7 5 8 9 6

第一趟結(jié)果：3 7 5 8 6 (9)

第二趟結(jié)果：3 5 7 6 (8 9)

第三趟結(jié)果：3 5 6 (7 8 9)

第四趟結(jié)果：3 5 (6 7 8 9)

第五趟結(jié)果：3 (5 6 7 8 9)

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

void BubbleSort (Record r[ ],int n )

{ int i,j,t;

for(i=1;i＜=n;i++)

for(j=i,j＜=n-i;j++)

if(a[j]＞a[j+1])

{t=a[j]; a[j]=a[j+1];

a[j+1]=t; }

}

2 算法分析

分析上述冒泡排序過程，6個(gè)元素，進(jìn)行了5趟排序，其中第一趟對(duì)比交換5次，第二趟4次，第五趟1次，觀察排序結(jié)果不難看出，在第三趟排序后，序列已經(jīng)有序，第四、五趟排序中沒有數(shù)據(jù)交換操作，程序可以不用執(zhí)行，是個(gè)“空操作”。另外，每趟排序只能確定一個(gè)最大數(shù)，使其“沉底”，速度較慢，若能在找出最大數(shù)的同時(shí)也找出最小數(shù)，是否可以加快排序速度呢？

3 改進(jìn)思路

通過在程序中設(shè)置監(jiān)視哨，可以解決“空操作”的問題，能使循環(huán)在序列已有序時(shí)及時(shí)退出，再將每趟排序從只能確定一個(gè)最大數(shù)“下沉”，改進(jìn)為最大數(shù)“下沉”的同時(shí)，最小數(shù)“上浮”，這樣就可以同時(shí)確定最大、最小兩個(gè)數(shù)，即雙向的冒泡，從而減少了循環(huán)執(zhí)行的次數(shù)，降低了時(shí)間復(fù)雜度，達(dá)到優(yōu)化算法的目的。流程圖如下：

3.1 基本原理及排序過程

仍以初始關(guān)鍵字(7 3 8 5 9 6)為例，n=6。

首先第一個(gè)關(guān)鍵字(r[0].key)與第二個(gè)關(guān)鍵字(r[1].key)進(jìn)行比較的同時(shí)，倒數(shù)第一個(gè)關(guān)鍵字(r[n-1].key)與倒數(shù)第二個(gè)關(guān)鍵字(r[n-2].key)進(jìn)行比較，若為逆序(即L.r[0].key＞L.r[1].key) 或 (r[n-1].key＞ r[n-2].key)，則將兩個(gè)逆序記錄交換。依次比較(r[1].key，r[2].key)和(r[n-2].key＞r[n-3].key)，(r[2].key，r[3].key) 和 (r[n-3].key＞ r[n-4].key），(r[3].key，r[4].key） 和 (r[n-4].key＞ r[n-5].key），(r[4].key，r[5].key) 和 (r[n-5].key＞r[n-6].key)，采用從前后兩個(gè)方向同時(shí)進(jìn)行，經(jīng)過5次比較交換后，第一趟冒泡排序結(jié)束，關(guān)鍵字最大的記錄“下沉”到最后一個(gè)位置，關(guān)鍵字最小的記錄“上浮”到第一個(gè)位置，再對(duì)剩下的中間四個(gè)數(shù)進(jìn)行同樣的過程。如下例：

初始關(guān)鍵字：7 3 8 5 9 6

第一次：7 3 8 5 9 6

第二次：3 7 8 5 6 9

第三次：3 7 8 5 6 9

第四次：3 7 5 8 6 9

第五次：3 5 7 6 8 9

第一趟結(jié)果：(3) 5 7 6 8 (9)

第二趟結(jié)果：(3 5) 6 7 (8 9)

第三趟結(jié)果：(3 5 6 ) (7 8 9)

每趟排序能找到所在區(qū)域內(nèi)最大、最小兩個(gè)數(shù)，因此對(duì)于n個(gè)元素的關(guān)鍵字，最多需要n/2趟排序，在數(shù)據(jù)量較大時(shí)，可以減少循環(huán)次數(shù)，加快排序速度。

在算法中引入監(jiān)視哨flag，用來監(jiān)視每趟排序是否有數(shù)據(jù)交換。在每趟排序開始前，先將其置為0，若排序過程中出現(xiàn)逆序，則進(jìn)行數(shù)據(jù)交換，同時(shí)將flag值置為1。每趟排序結(jié)束時(shí)檢查flag，若flag=0，則說明在此趟排序過程中沒有發(fā)生數(shù)據(jù)交換，表明序列已經(jīng)有序，可以終止排序。避免了“空操作”的問題，因此，用改進(jìn)的冒泡排序算法對(duì)記錄進(jìn)行排序，由于每趟循環(huán)均能確定2個(gè)元素，又能在記錄已經(jīng)基本有序的時(shí)候及時(shí)終止循環(huán)，因此所需的循環(huán)趟數(shù)，最多是傳統(tǒng)冒泡排序算法的一半。下面給出具體的算法。

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

void improveBubbleSort (Record r[ ],int n )

{ int i,j,k,flag,t ;

for(i=1;i＜=n/2;i++)

{ flag=0 ;

for(j=i,k=n-i;j＜=n-i;j++,k--)

{if(a[j]＞a[j+1])

{t=a[j]; a[j]=a[j+1];

a[j+1]=t; flag =1;}

if(a[k]＜a[k-1])

{t=a[k]; a[k]=a[k-1];

a[k-1]=t; flag =1;}

}

printf("*");

表1 參數(shù)的辨識(shí)結(jié)果和誤差

通過結(jié)果可以看出，參數(shù)誤差較小，從而說明粒子群算法的有效性和精度性。

4 結(jié)論

本文將粒子群算法應(yīng)用于風(fēng)電場(chǎng)模型的參數(shù)辨識(shí)中，并用Digsilent軟件搭建仿真模型進(jìn)行仿真分析，得到最終的參數(shù)辨識(shí)結(jié)果。結(jié)果表明，粒子群算法對(duì)于風(fēng)電場(chǎng)模型參數(shù)的辨識(shí)性能優(yōu)良。

[1]雷亞洲，Gordon Lightbody.國(guó)外風(fēng)力發(fā)電導(dǎo)則及動(dòng)態(tài)模型簡(jiǎn)介[J].電網(wǎng)技術(shù),2005,25(12):27-32.

[2]何東升，劉永強(qiáng)，王亞.并網(wǎng)型風(fēng)力發(fā)電系統(tǒng)的研究[J].高電壓技術(shù),2008,34(1):142-147.

[3]Dusonchet L,Massaro F,Telaretti E.Transient stability simulation of a fixed speed wind turbine by Matlab/Simulink[C]//ICCEP’2007//International Conference.Capri,Italy:[s.n.],2007.

[4]Pablo Ledesma,Julio Usaola.Doubly fed induction Generator model for transient stability analysis[J].IEEE Transactions on Energy Conversion,2005,20(2):388-397.