我做了一些关于Javascript 排序算法性能比较的研究,发现了意想不到的结果。冒泡排序提供了比 Shell 排序、快速排序和原生 Javascript 功能等其他方法更好的性能。为什么会这样?也许我的性能测试方法错了?
你可以在这里找到我的研究结果。
以下是一些算法实现示例:
/**
* Bubble sort(optimized)
*/
Array.prototype.bubbleSort = function ()
{
var n = this.length;
do {
var swapped = false;
for (var i = 1; i < n; i++ ) {
if (this[i - 1] > this[i]) {
var tmp = this[i-1];
this[i-1] = this[i];
this[i] = tmp;
swapped = true;
}
}
} while (swapped);
}
/**
* Quick sort
*/
Array.prototype.quickSort = function ()
{
if (this.length <= 1)
return this;
var pivot = this[Math.round(this.length / 2)];
return this.filter(function (x) { return x < pivot }).quickSort().concat(
this.filter(function (x) { return x == pivot })).concat(
this.filter(function (x) { return x > pivot }).quickSort());
}