0

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

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/

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

提前致谢。

4

3 回答 3

2

如果我坚持原来的问题（我不会建议完全不同的算法......）。

是的，还有另一个改进——双向冒泡排序，称为振动器排序。它消除了乌龟和兔子的问题。在单向冒泡排序中，轻气泡向阵列末端（兔子）快速移动，而重气泡向阵列起点移动非常缓慢。但是如果你以双向方式排序，这两种类型的气泡排序都非常快（仍然在 O(n^2) 中，但通常比传统的冒泡排序更快）。

于 2013-04-11T21:04:59.683 回答
2

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

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

于 2013-04-11T18:34:42.763 回答
1

这是我一直在寻找的解决方案：

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9, 1, 32423, 3455, 23, 4234,23];

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

bubbleSort(a);
alert(a);

http://jsfiddle.net/x7VpJ/1/

感谢所有回复。

于 2013-04-13T23:09:35.330 回答