0

これは学業/宿題の質問ですか?

変えたほうがいいかな

if (index_outer !== index_min) {
    $P.swap(arr, index_outer, index_min);
}

に

$P.swap(arr, index_outer, index_min);

index_outerこれはが最小値を持つ特別なケースであるため、常にスワップしますか? それは何もしないスワップになりますが、同時に何も壊れません。ifこれはめったに起こらないので、小切手の使用回数が減ると思います。

$P.swap = function (arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

$P.selectionSort = function (arr) {
    var index_outer,
        index_inner,
        index_min,
        length = arr.length;
    for (index_outer = 0; index_outer < length; index_outer++) {
        index_min = index_outer;
        for (index_inner = index_outer + 1; index_inner < length; index_inner++) {
            if (arr[index_inner] < arr[index_min]) {
                index_min = index_inner;
            }
        }
        if (index_outer !== index_min) {
            $P.swap(arr, index_outer, index_min);
        }
    }
    return arr;
};
4

1 に答える 1

2

それが常に良い考えだとは思いません。配列が部分的または完全にソートされている場合、$P.swap() への呼び出しが無駄になります。

選択ソートの改善については、index_minとindex_maxを使用して、配列を両端から同時にソートしてみてください。比較の数は同じままですが、パスの数が減少するため、合計実行時間が減少します。

于 2013-08-17T22:49:13.183 に答える