fla*_*404 16 javascript quicksort
我一直在网上寻找一段时间,我想知道是否存在通常使用的快速排序的"稳定"事实实现？我可以写自己的,但为什么重新发明轮子......
Mat*_*all 16
打电话Array.sort().它非常快.
var array = [3,7,2,8,2,782,7,29,1,3,0,34];
array.sort();
console.log(array); // prints [0, 1, 2, 2, 29, 3, 3, 34, 7, 7, 782, 8]
为什么按字典顺序打印？这是array.sort()默认情况下的工作原理,例如,如果您不提供比较器功能.我们来解决这个问题.
var array = [3,7,2,8,2,782,7,29,1,3,0,34];
array.sort(function (a, b)
{
return a-b;
});
console.log(array); // prints [0, 1, 2, 2, 3, 3, 7, 7, 8, 29, 34, 782]
Ben*_*uer 16
Quicksort(递归)
function quicksort(array) {
if (array.length <= 1) {
return array;
}
var pivot = array[0];
var left = [];
var right = [];
for (var i = 1; i < array.length; i++) {
array[i] < pivot ? left.push(array[i]) : right.push(array[i]);
}
return quicksort(left).concat(pivot, quicksort(right));
};
var unsorted = [23, 45, 16, 37, 3, 99, 22];
var sorted = quicksort(unsorted);
console.log('Sorted array', sorted);650*_*502 13
您可以使用decorate-sort-undecorate模式轻松"稳定"不稳定的排序
function stableSort(v, f)
{
if (f === undefined) {
f = function(a, b) {
a = ""+a; b = ""+b;
return a < b ? -1 : (a > b ? 1 : 0);
}
}
var dv = [];
for (var i=0; i<v.length; i++) {
dv[i] = [v[i], i];
}
dv.sort(function(a, b){
return f(a[0], b[0]) || (a[1] - b[1]);
});
for (var i=0; i<v.length; i++) {
v[i] = dv[i][0];
}
}
我们的想法是将索引添加为最后一个排序项,以便现在没有两个元素"相同",如果其他所有内容相同,则原始索引将成为区别因素.
为了庆祝功能性Javascript,这似乎是事物
目前,特别是考虑到ES6 +精彩的糖类添加剂.箭头函数和解构我提出了一个非常干净,简短的功能等同于quicksort函数.我没有对其性能进行测试或将其与内置的快速排序功能进行比较,但它可能会帮助那些努力理解快速排序实际使用的人.鉴于其声明性特性是很容易看到什么是反对正在发生的事情是如何它的工作原理.
这是一个没有评论的JSBin版本https://jsbin.com/zenajud/edit?js,console
function quickSortF(arr) {
// Base case
if (!arr.length) return []
// This is a ES6 addition, it uses destructuring to pull out the
// first value and the rest, similar to how other functional languages
// such as Haskell, Scala do it. You can then use the variables as
// normal below
const [head, ...tail] = arr,
// here we are using the arrow functions, and taking full
// advantage of the concise syntax, the verbose version of
// function(e) => { return e < head } is the same thing
// so we end up with the partition part, two arrays,
// one smaller than the pivot and one bigger than the
// pivot, in this case is the head variable
left = tail.filter( e => e < head),
right = tail.filter( e => e >= head)
// this is the conquer bit of divide-and-conquer
// recursively run through each left and right array
// until we hit the if condition which returns an empty
// array. These results are all connected using concat,
// and we get our sorted array.
return quickSortF(left).concat(head, quickSortF(right))
}
const q7 = quickSortF([11,8,14,3,6,2,7])
//[2, 3, 6, 7, 8, 11, 14]
const q8 = quickSortF([11,8,14,3,6,2,1, 7])
//[1, 2, 3, 6, 7, 8, 11, 14]
const q9 = quickSortF([16,11,9,7,6,5,3, 2])
//[2, 3, 5, 6, 7, 9, 11, 16]
console.log(q7,q8,q9)
如果已经不清楚发生了什么,那么评论应该足够了.没有评论的实际代码很短,你可能已经注意到我不是分号的粉丝.:)
function quickSort(arr) {
if (arr.length < 2) {
return arr;
}
const pivot = arr[Math.floor(Math.random() * arr.length)];
let left = [];
let right = [];
let equal = [];
for (let val of arr) {
if (val < pivot) {
left.push(val);
} else if (val > pivot) {
right.push(val);
} else {
equal.push(val);
}
}
return [
...quickSort(left),
...equal,
...quickSort(right)
];
}
几点注意事项：
Array.filter而不是使用for of循环很好，就像这里的一些答案一样，它会增加时间复杂度（Array.reduce尽管可以使用）。在这篇博客中,http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/指出,Array.sort是在quicksort中实现的,或者是在internaly中合并排序.
Quicksort通常被认为是高效和快速的,因此被V8用作具有超过23项的数组上的Array.prototype.sort()的实现.对于少于23个项目,V8使用插入排序[2].合并排序是quicksort的竞争对手,因为它既高效又快速,但具有稳定的附加好处.这就是Mozilla和Safari使用它来实现Array.prototype.sort()的原因.
当使用Array.sort时,你应该在Chrome中返回-1 0 1而不是true或false.
arr.sort(function(a,b){
return a<b;
});
// maybe--> [21, 0, 3, 11, 4, 5, 6, 7, 8, 9, 10, 1, 2, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22]
arr.sort(function(a,b){
return a > b ? -1 : a < b ? 1 : 0;
});
// --> [22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
小智 7
var array = [8, 2, 5, 7, 4, 3, 12, 6, 19, 11, 10, 13, 9];
quickSort(array, 0, array.length -1);
document.write(array);
function quickSort(arr, left, right)
{
var i = left;
var j = right;
var tmp;
pivotidx = (left + right) / 2;
var pivot = parseInt(arr[pivotidx.toFixed()]);
/* partition */
while (i <= j)
{
while (parseInt(arr[i]) < pivot)
i++;
while (parseInt(arr[j]) > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
return arr;
}使用 ES6 休息，传播：
smaller = (a, list) => list.filter(x => x <= a)
larger = (a, list) => list.filter(x => x > a)
qsort = ([x, ...list]) => (!isNaN(x))
? [...qsort(smaller(x, list)), x, ...qsort(larger(x, list))]
: []