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

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

原书中代码大意为：

代码语言：javascript复制

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 %dn",i,j);
}

倘若数组此时为：

代码语言：javascript复制

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

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

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

代码语言：javascript复制

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);
            }
        }
    }
}

测试 后端 排序 数组 优化

0 人点赞