javascript - 还有另一种方法可以优化这种冒泡排序吗？

Question

我有这段代码，它使用冒泡排序算法对数值数组进行排序。

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];

function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] < a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}

bubbleSort(a);
alert(a);

你可以在这里看到:http://jsfiddle.net/x7VpJ/

好吧，正如您所检查的那样，它工作完美，但我想知道是否有另一种方法可以优化它以使用实际方法进行更少的循环。我的意思是，使用 swapped 变量。也许省略了排序的项目......一些想法？

提前致谢。

Answer 1

这里列出了 JS 中不同的排序算法。我制作了一个比较排序时间的页面，据我观察，“快速”似乎是最佳选择。

冒泡排序:

var arrBubble= new Array();
var tmpBubble;
function srtBubble(){
    tmpDate=new Date();
    timBegin=tmpDate.getTime();

    var blnBubbleSwitch;
    do {
        blnBubbleSwitch=false;
        for(var i=0;i<arrBubble.length-1;i++){
            if(arrBubble[i]>arrBubble[i+1])
            {
                tmpBubble=arrBubble[i];
                arrBubble[i]=arrBubble[i+1];
                arrBubble[i+1]=tmpBubble;
                blnBubbleSwitch=true;
            }
        }
    } while(blnBubbleSwitch);
}

插入:

var arrinsertion= new Array();
var tmpinsertion;
function srtinsertionion(){
    var j;
    blninsertionSwitch=false;
    for(var i=0;i<arrinsertion.length;i++){
        tmpinsertion=arrinsertion[i];
        j=i;
        while((j>=0)&&arrinsertion[j-1]>tmpinsertion)
        {
            arrinsertion[j]=arrinsertion[j-1];
            j--;
            //blninsertionSwitch=true;
        }
        arrinsertion[j]=tmpinsertion;
    }
}

外壳:

function srtShell(){
var arrShell= new Array();
    for (var h = arrShell.length; h = parseInt(h / 2);) {
        for (var i = h; i < arrShell.length; i++) {
            var k = arrShell[i];
            for (var j = i; j >= h && k < arrShell[j - h]; j -= h)
                arrShell[j] = arrShell[j - h];
            arrShell[j] = k;
        }
    }
}

快速:

function srtQuick()
{
    var arrQuick= new Array();
    qsort(arrQuick, 0, arrQuick.length);
}
function qsort(array, begin, end)
{
    if(end-1>begin) {
        var pivot=begin+Math.floor(Math.random()*(end-begin));

        pivot=partition(array, begin, end, pivot);

        qsort(array, begin, pivot);
        qsort(array, pivot+1, end);
    }
}
Array.prototype.swap=function(a, b)
{
    var tmp=this[a];
    this[a]=this[b];
    this[b]=tmp;
}
function partition(array, begin, end, pivot)
{
    var piv=array[pivot];
    array.swap(pivot, end-1);
    var store=begin;
    var ix;
    for(ix=begin; ix<end-1; ++ix) {
        if(array[ix]<=piv) {
            array.swap(store, ix);
            ++store;
        }
    }
    array.swap(end-1, store);

    return store;
}

合并:

function merge_inplace(array, begin, begin_right, end)
{
    var arrMerge= new Array();
    for(;begin<begin_right; ++begin) {
        if(array[begin]>array[begin_right]) {
            var v=array[begin];
            array[begin]=array[begin_right];
            insertion(array, begin_right, end, v);
        }
    }
}

function insertion(array, begin, end, v)
{
    while(begin+1<end && array[begin+1]<v) {
        array.swap(begin, begin+1);
        ++begin;
    }
    array[begin]=v;
}

function msort(array, begin, end)
{
    var size=end-begin;
    if(size<2) return;

    var begin_right=begin+Math.floor(size/2);

    msort(array, begin, begin_right);
    msort(array, begin_right, end);
    merge_inplace(array, begin, begin_right, end);
}

function srtMerge()
{
    msort(arrMerge, 0, arrMerge.length);
}

内置 JS 排序:

function srtJSSort()
{
    var arrJSSort= new Array();
    arrJSSort.sort(function(a,b){return a-b});
}

当然，我会建议在函数之外使用您的数组，以便您可以在数据排序后继续使用它。