冒泡排序

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

这里是普通的冒泡排序：

/**
 * 普通的冒泡排序
 * @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;
    }
}

《冒泡排序》有13个想法

  1. lite3 文章作者

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

  2. as3

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

  9. lite3 文章作者

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

  10. test

    /**
    * 普通的冒泡排序 应该是这样的
    * @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？

  11. lite3 文章作者

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

评论已关闭。