在Javascript中使用随机枢轴实现QuickSort

Question

我已经用JavaScript编写了quicksort，但我想尝试用随机的枢轴创建一个，而不是通过选择数组中的第一个或最后一个元素：

   function qsort(a) {
     //base case
     if (a.length === 0) return [];

     //setting the pivot as the last element. 
     var left = [],
         right = [],
         pivot = a[a.length - 1];

     //look before the pivot. everything less than it goes to its left, more than it, to its right.
     for (var i = a.length - 2; i >= 0; i--) {
         a[i] < pivot ? left.push(a[i]) : right.push(a[i]);
     }
     //you then do this recursively until the basecase, pivoting/sorting all sub arrays, then concatenating the left side with the pivot and the right side.
     return qsort(left).concat(pivot, qsort(right));
 }

 console.log(qsort([9, 8, 7, 6, 10, 5]));//[5, 6, 7, 8, 9, 10]

我以为我可以做类似的事情：

pivot = a[Math.floor(Math.random() * a.length)];

我被绊倒的地方是，一旦您将枢轴分配为数组中的随机值，我的for循环的参数将不再有效。解决此功能/ for循环中的随机枢轴并使它正确排序的最佳方法是什么？

Answer 1

显而易见的事情是制作一个数据透视数组，在其中填充与数据透视相等的元素。

Answer 2

Amadan提供的解决方案，不能处理包含非唯一值的数组。以下解决方案应该能够处理任何整数数组，包括具有非唯一值的整数数组。例如[4，6，6，3，4，4，2]