《大话数据结构》冒泡排序错误修正

时间：2014-03-11 01:44:06 收藏：0 阅读：458

书中本意是想省略后端顺序表中无用的查找，但是忽略了一个问题。

原书中代码大意为：

void bubblesort(Graph *g,int len){
    int i,j;
    int flag = 1;
    for(i=0;        i < len && flag;    i++){
        flag = 0;
        //printf("len %d",len);
        for(j = len-1;    j>i;    j--){
            if(g->e[j].length < g->e[i].length){
                swap(g,i,j);
                printf("%d %d \n",i,j);
                flag = 1;
            }
        }
    }
    //printf("%d %d\n",i,j);
}

倘若数组此时为：

7 8 10 11 12 22 16 20 16 20 16 21 26 17 18 19

那么测试i=5时，flag并未被标记，排序终止，但是后端其实只有一个节点是顺序的，而后面还有未排序的点。因此此方法并不适用。

因此，最好还是去掉标记为，使用传统优化方法即可：

void bubblesort(Graph *g,int len){
    int i,j;
    for(i=0;        i < len;    i++){
        for(j = len-1;    j>i;    j--){
            if(g->e[j].length < g->e[i].length){
                swap(g,i,j);
            }
        }
    }
}

《大话数据结构》冒泡排序错误修正,布布扣,bubuko.com

原文：http://www.cnblogs.com/xing901022/p/3592296.html