javascript - 如何改进选择排序？

Question

这更像是一个学术/家庭作业问题？

改变会不会更好

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;
};

Answer 1

我不认为这总是一个好主意。如果数组是部分/完全排序的，你会浪费对 $P.swap() 的调用。

至于改进选择排序，请尝试通过使用index_min和index_max同时从两端对数组进行排序。尽管比较次数保持不变，但通过次数会减少，从而减少总运行时间。