javascript - 如何改进选择排序？

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

已关闭 9 年前。

Improve this 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 同时从两端对数组进行排序。尽管比较次数保持不变，但传递次数会减少，从而减少总运行时间。