我正在学习技术面试，并编写不同种类的快速javascript实现 . 大多数基本排序的随机数组基准测试结果是有意义的，但选择排序非常快 . 我不知道为什么 .
这是我对Selection Sort的实现：
Array.prototype.selectionSort = function () {
for (var target = 0; target < this.length - 1; target++) {
var min = target;
for (var j = target + 1; j < this.length - 1; j++) {
if (this[min] > this[j]) {
min = j;
}
}
if (min !== target) {
this.swap(min, target);
}
}
}
以下是具有10000个元素的相同随机生成数组的结果：
BubbleSort => 148ms
InsertionSort => 94ms
SelectionSort => 91ms
MergeSort => 45ms
所有排序都使用相同的交换方法 . 那么为什么选择排序更快？我唯一的猜测是Javascript在数组遍历时非常快，但在值突变方面很慢，因为SelectionSort使用最少的值突变，它更快 .
** 以供参考 **
这是我的冒泡排序实现
Array.prototype.bubbleSort = function () {
for (var i = this.length - 1; i > 1; i--) {
var swapped = false;
for (var j = 0; j < i; j++) {
if (this[j + 1] < this[j]) {
this.swap(j, j+1);
swapped = true;
}
}
if ( ! swapped ) {
return;
}
}
}
这是交换实施
Array.prototype.swap = function (index1, index2) {
var val1 = this[index1],
val2 = this[index2];
this[index1] = val2;
this[index2] = val1;
};
1 回答
首先让我指出两个缺点：
否则永远不会选择最后一个元素 .
幸运的是，你的测试数组非常大，以至于jsperf只会立即运行其测试循环的一次迭代，调用在每次运行之前初始化数组的设置代码 . 不过，这会困扰你的小阵列 . 您需要在“定时代码”本身内对数组进行洗牌 .
是 . 写入总是比读取慢，并且对缓存值也有负面影响 .
是的，这非常重要 . 选择和冒泡排序都有
O(n²)运行时，这意味着它们都执行大约100000000循环条件检查，索引增量和两个数组元素的比较 .但是，虽然选择排序只进行
O(n)交换，但冒泡排序确实是O(n²). 这意味着不仅要改变数组，还要调整方法调用的开销 . 而且比选择排序更常见 . 这里有一些example logs：糟糕！