Home » 算法 » 冒泡排序

冒泡排序

发表评论 阅读评论

冒泡排序大家都知道,但是基本的冒泡排序还是有优化的空间的。请看两个不同版本的比较。

这里是普通的冒泡排序:

/**
 * 普通的冒泡排序
 * @param   arr
 */
function bubbleSort(arr:Array):void
{
    var len:int = arr.length;
    for (var i:int = 0; i < len; i++)
    {
        for (var j:int = i + 1; j < len; j++)
        {
            if (arr[i] < arr[j])
            {
                var t:* = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
    }
}

这里是优化后的冒泡排序:

/**
 * 冒泡排序优化
 * @param   arr
 */
function bubblesSortPlus(arr:Array):void
{
    var end:int = arr.length -1;
    while (end > 0)
    {
        var k:int = 0;
        for (var i:int = 0; i < end; i++)
        {
            if (arr[i] < arr[i + 1])
            {
                var t:* = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
                k = i;
            }
        }
        end = k;
    }
}
标签: ,

  1. |

    好像第二个优化的例子,里面的变量j没有定义?就是(i + 1)?

  2. | |

    @lynx
    抱歉了,粘贴的时候忘记了,更正了,就是 i + 1 :roll:

  3. | |

    排序不仅仅对于数值数组的,也可以为对象数组进行排序,只要能够判断两个元素的在数组里的前后位置就可以了, :razz:

  4. |

    /**
    * 普通的冒泡排序 应该是这样的
    * @param arr
    */
    function bubbleSort(arr:Array):void
    {
    var len:int = arr.length;
    for (var i:int = 0; i < len; i++)
    {
    for (var j:int = i + 1; j < len-1; j++)
    {
    if (arr[i] < arr[j])
    {
    var t:* = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    }
    }
    }
    }

    没看到你优化后的 优势啊! 就是把第一重的for 换成 while?

  5. | |

    @test
    如果for循环里没有变过位置,那么就表示剩下的都是正确的顺序了,
    然后 end = k; end < ==> 0,
    while就会跳出来,不必再对剩下的排序了
    当然在最坏的情况下,并不会减少循环次数.

  6. |

    如果数组是纯数字数字的话, 这段代码是写加数字从大到小排列吗?

  7. | |

    @yejianwei
    恩,是的,呵呵

  8. | |

    @yejianwei
    恩,是的,不过也可以用对象

  9. |

    我试了下,貌似优化过的更慢 :idea:

  10. |

    技术的东西往往是向往不可及

  11. | |

    :grin: 上次人家说的优化后变慢了,还没弄呢, :mrgreen:

  12. |

    其实你可以定义个布尔值变量。如果一个循环里都没有执行if语句,那就直接return;因为有的时候没必要等end == 0;

  13. | |

    @as3
    其实这个优化的思路是从后向前排, 然后如果没有要排了就利用while的条件退出,
    while里只有排序的的条件判断,如果再做个boolean变量,那么每次循环就会增加一次条件判断,理论上讲会增加运行时间的

回到顶部