JavaScript 快速排序

JavaScript quicksort

提问by flavour404

I have been looking around the web for a while and I am wondering if there is a 'stable' defacto implementation of quicksort that is generally used? I can write my own but why reinvent the wheel...

我已经在网上浏览了一段时间，我想知道是否有通常使用的快速排序的“稳定”事实上的实现？我可以自己写，但为什么要重新发明轮子...

采纳答案by 6502

You can easily "stabilize" an unstable sort using a decorate-sort-undecorate pattern

您可以使用装饰-排序-取消装饰模式轻松“稳定”不稳定的排序

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

the idea is to add the index as last sorting term so that no two elements are now "the same" and if everything else is the same the original index will be the discriminating factor.

这个想法是将索引添加为最后一个排序项，这样现在没有两个元素是“相同的”，如果其他所有元素都相同，则原始索引将成为区分因素。

回答by Benny Neugebauer

Quicksort (recursive)

快速排序（递归）

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

回答by Matt Ball

1. Put your objects into an array.

2. Call Array.sort(). It's very fast.

   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]
   

1. 将您的对象放入一个数组中。

2. 打电话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]
   

Why does that print in lexicographic order? That's how array.sort()works by default, e.g. if you don't provide a comparator function.Let's fix this.

为什么按字典顺序打印？这就是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]

回答by Faktor 10

A Functional equivalent

功能等价物

In celebration of Functional Javascript, which appears to be the in thing

庆祝功能性 Javascript，这似乎是最重要的

at the moment, especially given ES6+ wonderful syntactic sugar additions. Arrow functions and destructuring I propose a very clean, short functional equivalent of the quicksort function. I have not tested it for performance or compared it to the built-in quicksort function but it might help those who are struggling to understand the practical use of a quicksort. Given its declarative nature it is very easy to see whatis happening as oppose to howit works.

目前，特别是考虑到 ES6+ 美妙的语法糖添加。箭头函数和解构 我提出了一个非常简洁、简短的快速排序函数等价物。我没有测试它的性能，也没有将它与内置的快速排序功能进行比较，但它可能会帮助那些正在努力理解快速排序的实际用途的人。鉴于其声明性特性是很容易看到什么正在发生的反对是如何它的工作原理。

Here is a JSBin version without comments https://jsbin.com/zenajud/edit?js,console

这是一个没有评论的 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)

The comments should provide enough if it is already not clear what is happening. The actual code is very short without comments, and you may have noticed I am nota fan of the semicolon. :)

如果尚不清楚发生了什么，评论应该提供足够的信息。实际代码很短，没有注释，你可能已经注意到我不喜欢分号。:)

回答by jinwei

In this blog http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/which has pointed out that Array.sort is implemented in quicksort or merge sort internaly.

在这个博客http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/中指出 Array.sort 是在快速排序或合并排序中实现的。

Quicksort is generally considered to be efficient and fast and so is used by V8 as the implementation for Array.prototype.sort() on arrays with more than 23 items. For less than 23 items, V8 uses insertion sort[2]. Merge sort is a competitor of quicksort as it is also efficient and fast but has the added benefit of being stable. This is why Mozilla and Safari use it for their implementation of Array.prototype.sort().

Quicksort 通常被认为是高效且快速的，因此 V8 使用它作为 Array.prototype.sort() 对超过 23 个项目的数组的实现。对于少于 23 个项目，V8 使用插入排序[2]。归并排序是快速排序的竞争对手，因为它也高效、快速，但还有一个额外的好处是稳定。这就是 Mozilla 和 Safari 使用它来实现 Array.prototype.sort() 的原因。

and when using Array.sort,you should return -1 0 1 instead of true or false in Chrome.

并且在使用 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]

回答by Andriy

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

回答by GChamon

Using ES6 rest, spread:

使用 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))]
    : []

回答by Lior Elrom

Quick Sort (ES6)

快速排序 (ES6)

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

Few notes:

几点注意事项：

• A random pivot keeps the algorithm efficient even when the data is sorted.
• As much as it nice to use Array.filterinstead of using for ofloop, like some of the answers here, it will increase time complexity (Array.reducecan be used instead though).

• 即使对数据进行排序，随机枢轴也能保持算法高效。
• 尽管使用Array.filter而不是使用for of循环很好，就像这里的一些答案一样，它会增加时间复杂度（Array.reduce尽管可以使用）。

回答by Teoman shipahi

Yet another quick sort demonstration, which takes middle of the array as pivot for no specific reason.

另一个快速排序演示，它以数组的中间作为支点，没有特定原因。

const QuickSort = function (A, start, end) {
    // 
    if (start >= end) {
        return;
    }
    // return index of the pivot
    var pIndex = Partition(A, start, end);
    // partition left side
    QuickSort(A, start, pIndex - 1);
    // partition right side
    QuickSort(A, pIndex + 1, end);
}

const Partition = function (A, start, end) {
    if (A.length > 1 == false) {
        return 0;
    }
    let pivotIndex = Math.ceil((start + end) / 2);
    let pivotValue = A[pivotIndex];
    for (var i = 0; i < A.length; i++) {
        var leftValue = A[i];
        // 
        if (i < pivotIndex) {
            if (leftValue > pivotValue) {
                A[pivotIndex] = leftValue;
                A[i] = pivotValue;
                pivotIndex = i;
            }
        }
        else if (i > pivotIndex) {
            if (leftValue < pivotValue) {
                A[pivotIndex] = leftValue;
                A[i] = pivotValue;
                pivotIndex = i;
            }
        }
    }
    return pivotIndex;

}

const QuickSortTest = function () {
    const arrTest = [3, 5, 6, 22, 7, 1, 8, 9];
    QuickSort(arrTest, 0, arrTest.length - 1);
    console.log("arrTest", arrTest);
}
// 
QuickSortTest();

回答by user3870075

This algorithm work almost as fast as the default implementation of Array.prototype.sort in chrome.

该算法的运行速度几乎与 Chrome 中 Array.prototype.sort 的默认实现一样快。

function quickSort(t){
    _quickSort(t,0,t.length-1,0,t.length-1);
}

function _quickSort(t, s, e, sp, ep){   
    if( s>=e )  return;
    while( sp<ep && t[sp]<t[e] ) sp++;  
    if( sp==e )
        _quickSort(t,s,e-1,s,e-1);  
    else{
        while(t[ep]>=t[e] && sp<ep ) ep--;      
        if( sp==ep ){
            var temp = t[sp];
            t[sp] = t[e];
            t[e] = temp;
            if( s!=sp ){
                _quickSort(t,s,sp-1,s,sp-1);
            }
            _quickSort(t,sp+1,e,sp+1,e);            
        }else{
            var temp = t[sp];
            t[sp] = t[ep];
            t[ep] = temp;
            _quickSort(t,s,e,sp+1,ep);
        }
    }
}

quickSort time (ms): 738
javaScriptSort time (ms): 603

快速排序时间（毫秒）：738
javaScriptSort 时间（毫秒）：603

var m = randTxT(5000,500,-1000,1000);
VS(m);

function VS(M){
    var t;
    t = Date.now();
    for(var i=0;i<M.length;i++){
        quickSort(M[i].slice());
    }console.log("quickSort time (ms): "+(Date.now()-t));

    t = Date.now();
    for(var i=0;i<M.length;i++){
        M[i].slice().sort(compare);
    }console.log("javaScriptSort time (ms): "+(Date.now()-t));
}

function compare(a, b) {
    if( a<b )
        return -1;
    if( a==b )
        return 0;
    return 1;
}

function randT(n,min,max){
    var res = [], i=0;
    while( i<n ){
        res.push( Math.floor(Math.random()*(max-min+1)+min) );
        i++;
    }
    return res; 
}
function randTxT(n,m,min,max){
    var res = [], i=0;
    while( i<n ){
        res.push( randT(m,min,max) );
        i++;
    }
    return res; 
}