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

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 に答える