首页 > 代码库 > 冒泡排序及尝试改进
冒泡排序及尝试改进
冒泡排序是一种交换排序思想，既两两比较待排序记录的关键字（值），发现两个记录的次序（大小）相反时进行交换，直到所有记录都满足排序要求。
该算法的平均时间复杂度为O(n2)，冒泡排序算法时有几个可以缩短操作的方法：
如果一次排序比较过程中没有发生记录位置交换，即可停止排序操作；
如果一次排序比较过程中发生了记录位置交换，则最后一次记录交换的位置，可作为下一次排序比较遍历的停止位置，因为该位置之前的数据都是有序的；
冒泡排序具有不对称性，比如进行从小到大排序，当原序列最大数排在首位，尽管剩余数已经按照从小到大排序了，比如10,1,2,3,4,6,7,8,9。则排序时从底往前扫描冒泡最小值时，该序列还需要进行9次排序比较，但从前往后进行最大值冒泡时，只需1次排序比较。对数列进行冒泡排序时，分别轮流从前、后分别进行排序比较时，能有效规避不对称性。
基于以上3点分析，下面是优化的冒泡排序算法：
void BubbleSort(int R[],int n)
{ //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
int i,j,lastchghd,lastchghdpos,lastchgtail,lastchgtailpos;
int bswap;
lastchghdpos = 1;
lastchgtailpos = n-1;
for(i= 1; i< n; i++){
bswap=0;
lastchghd = lastchghdpos;
lastchgtail = lastchgtailpos;
if (i & 1){ //奇数时,小值冒泡到头部
for(j= lastchgtail; j>= lastchghd; j--) {
if(R[j+1] < R[j]){//交换记录
R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元
R[j+1]=R[j];
R[j]=R[0];
bswap= 1;//发生了交换，故将交换标志置为
lastchghdpos = j;
}
}
}
else{ //偶数时,大值冒泡到底部
for(j= lastchghd; j <= lastchgtail; j++) {
if(R[j+1] < R[j]){//交换记录
R[0]=R[j+1]; //R[0]做暂存单元
R[j+1]=R[j];
R[j]=R[0];
bswap= 1;//发生了交换，故将交换标志置为
lastchgtailpos = j;
}
}
}
if(!bswap) //本趟排序未发生交换，提前终止算法
return;
}
}
本文出自 “daydreamer” 博客，谢绝转载！
冒泡排序及尝试改进