一种基于冒泡排序法的改进算法

杨晓明

（西安翻译学院,陕西西安,710105）

0 引言

排序(Sorting)是计算机程序设计中的一种重要操作，功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。常用的内部排序算法有选择排序、直接插入排序、冒泡排序、快速排序等，其中冒泡排序是最基本最常用的排序算法之一。

1 冒泡排序

冒泡排序的基本思想是：总是对相邻的两个元素进行比较，如果不满足规定的顺序（升序或降序），则二者进行交换，直到所有的元素都满足规定的顺序为止。

执行过程分析（以升序排序为例）：首先将第一个关键字与第二个关键字进行比较，若为逆序（即r[0].key＞ r[1].key），则将两个记录交换之，然后比较第二个关键字和第三个关键字。依次类推，直至第n-1个关键字和第n个关键字进行比较为止，完成了冒泡排序第一趟，关键字最大的记录被安置在最后一个位置上。然后进行第二趟排序，对前n-1个记录进行同样的操作，使关键字次大的记录放在了倒数第二个位置上，一般地，若有n个记录，则需要进行n-1趟排序，其中第i趟冒泡排序需要相邻元素（r[i].key与r[i+1].key）对比交换n-i次。

例如：

初始关键字：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

第一趟结果：3 7 5 8 6 (9)

第二趟结果：3 5 7 6 (8 9)

第三趟结果：3 5 6 (7 8 9)

第四趟结果：3 5 (6 7 8 9)

第五趟结果：3 (5 6 7 8 9)

算法实现：

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个元素，进行了5趟排序，其中第一趟对比交换5次，第二趟4次，第五趟1次，观察排序结果不难看出，在第三趟排序后，序列已经有序，第四、五趟排序中没有数据交换操作，程序可以不用执行，是个“空操作”。另外，每趟排序只能确定一个最大数，使其“沉底”，速度较慢，若能在找出最大数的同时也找出最小数，是否可以加快排序速度呢？

3 改进思路

通过在程序中设置监视哨，可以解决“空操作”的问题，能使循环在序列已有序时及时退出，再将每趟排序从只能确定一个最大数“下沉”，改进为最大数“下沉”的同时，最小数“上浮”，这样就可以同时确定最大、最小两个数，即双向的冒泡，从而减少了循环执行的次数，降低了时间复杂度，达到优化算法的目的。流程图如下：

3.1 基本原理及排序过程

仍以初始关键字(7 3 8 5 9 6)为例，n=6。

首先第一个关键字(r[0].key)与第二个关键字(r[1].key)进行比较的同时，倒数第一个关键字(r[n-1].key)与倒数第二个关键字(r[n-2].key)进行比较，若为逆序(即L.r[0].key＞L.r[1].key) 或 (r[n-1].key＞ r[n-2].key)，则将两个逆序记录交换。依次比较(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)，采用从前后两个方向同时进行，经过5次比较交换后，第一趟冒泡排序结束，关键字最大的记录“下沉”到最后一个位置，关键字最小的记录“上浮”到第一个位置，再对剩下的中间四个数进行同样的过程。如下例：

初始关键字：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

第一趟结果：(3) 5 7 6 8 (9)

第二趟结果：(3 5) 6 7 (8 9)

第三趟结果：(3 5 6 ) (7 8 9)

每趟排序能找到所在区域内最大、最小两个数，因此对于n个元素的关键字，最多需要n/2趟排序，在数据量较大时，可以减少循环次数，加快排序速度。

在算法中引入监视哨flag，用来监视每趟排序是否有数据交换。在每趟排序开始前，先将其置为0，若排序过程中出现逆序，则进行数据交换，同时将flag值置为1。每趟排序结束时检查flag，若flag=0，则说明在此趟排序过程中没有发生数据交换，表明序列已经有序，可以终止排序。避免了“空操作”的问题，因此，用改进的冒泡排序算法对记录进行排序，由于每趟循环均能确定2个元素，又能在记录已经基本有序的时候及时终止循环，因此所需的循环趟数，最多是传统冒泡排序算法的一半。下面给出具体的算法。

3.2 算法实现

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 参数的辨识结果和误差

通过结果可以看出，参数误差较小，从而说明粒子群算法的有效性和精度性。

4 结论

本文将粒子群算法应用于风电场模型的参数辨识中，并用Digsilent软件搭建仿真模型进行仿真分析，得到最终的参数辨识结果。结果表明，粒子群算法对于风电场模型参数的辨识性能优良。

[1]雷亚洲，Gordon Lightbody.国外风力发电导则及动态模型简介[J].电网技术,2005,25(12):27-32.

[2]何东升，刘永强，王亚.并网型风力发电系统的研究[J].高电压技术,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.