大话数据结构-9.3 冒泡排序 - 高飞网

9.3 冒泡排序

2017-01-23 10:11:36.0

9.3.1 最简单排序实现

    冒泡排序(Bubble Sort)一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

    最简单的冒泡排序

/* 对顺序表L作冒泡排序i,初级版 */
void BubbleSort0(SqList *L)
{
    for(int i=1;i<L->length;i++)
    {
        for(int j=i+1;j<=L->length;j++)
        {
            if(L->r[i]>L->r[j])//比较
            {
                swap(L,i,j);//交换
            }   
        }   
    }   
}

    这段代码严格意义上说,不算是标准的冒泡排序算法,因这它不满足“两两比较相邻记录”的冒泡排序思想,它更应该是最简单的交换排序而已。它的思路就是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在一次循环后一定变成最小值。

    它应该是最容易的排序代码了,不过这个简单易懂的代码,却是有缺陷的。观察发现,在排序好1和2的位置后,对其余关键字的排序没有什么帮助(数字3反而被换到最后一位)。也即这个算法的效率非常低。

9.3.2 冒泡排序

/* 对顺序表L作冒泡排序 */                                             
void BubbleSort(SqList *L)                                            
{                                                                     
    for(int i=1;i<L->length;i++)                                      
    {                                        
        for(int j=L->length-1;j>=i;j--)//遍历一趟,至少将一个最小值移动至最前
        {                                                             
            if(L->r[j]>L->r[j+1])                                     
            {                                                         
                swap(L,j,j+1);
            }                                                         
        }
    }                                                                 
}                                                  


    通过一趟比较,把最小的1放到了最开始位置,同时把2交换到第三位置;当第二趟时,关键字2交换到第二位置,关键字3、4也有所提升。

9.3.3 冒泡排序的优化

    试想一下,如果除了第一和第二的关键字需要排序外,别的都已经正常的顺序。当i=1时。交换了2和1,此时序列已经有序了,但是算法仍然不依不饶地将i=2到9以及每个循环中的j循环都执行一遍,尽管没有交换数据,但之后的大师比较还是大大地多余了。


    为此可以设计一个标识位flag,或者设计一个计数器,如果交换次数为0,说明已经有序,就可以退出排序了:

/* 对顺序表L作冒泡排序 */                                             
void BubbleSort(SqList *L)                                            
{                                                                     
    for(int i=1;i<L->length;i++)                                      
    {                                                                 
        int count = 0;                                                
        for(int j=L->length-1;j>=i;j--)//遍历一趟,至少将一个最小值移动至最前
        {                                                             
            if(L->r[j]>L->r[j+1])                                     
            {                                                         
                swap(L,j,j+1);                                        
                count++;                                              
            }                                                         
        }                                                             
        if(count==0)break;//趟数为0时即没有交换,完成排序             
    }                                                                 
}                                                        

9.3.4 冒泡排序复杂度分析

    最好的情况是序列本身是有序的,只需要比较一趟,即n-1次(n为序列长度),为O(n),最坏的情况,需要比较n-1趟,每趟交比较个数递减(越往后比较次数越少)。,时间复杂度为O(n2)。