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

Question

我在 javascript 中编写了快速排序，但我想尝试创建一个具有随机主元的快速排序，而不是通过选择数组中的第一个或最后一个元素：

   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 循环的参数将不再有效。考虑此 function/for 循环中的随机枢轴并使其正确排序的最佳方法是什么？

Answer 1

最明显的做法是创建一个主元数组，在其中填充等于主元的元素。

另一种方法是记住枢轴的索引和值，并在循环的顶部跳过它（这将遍历整个数组）：

if (i == pivotIndex) continue;

另一种通常在 C 中使用以避免分配的方法是在一个数组中执行所有操作。

function qsort(array, start, end) {
  if (start === undefined) {
    start = 0;
    end = array.length - 1;
  } else if (start >= end) {
    return array;
  }
  var rStart = start, rEnd = end;
  var pivot = array[Math.floor(Math.random() * (end - start + 1) + start)];
  while (start < end) {
    while (array[start] <= pivot) start++;
    while (array[end] > pivot) end--;
    if (start < end) {
      var temp = array[start];
      array[start] = array[end];
      array[end] = temp;
    }
  }
  qsort(array, rStart, start - 1);
  qsort(array, start, rEnd);
  return array;
}

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

Answer 2

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

function quickSort (arr, left = 0, right = arr.length - 1) {
  if (arr.length > 1) {
    const position = partition(arr, left, right)
    if (left < position - 1) quickSort(arr, left, position - 1)
    if (position < right) quickSort(arr, position, right)
  }
  return arr
}

function partition (arr, left, right) {
  const pivot = arr[Math.floor(Math.random() * (right - left + 1) + left)]

  while (left <= right) {
    while (arr[left] < pivot) {
      left++
    }
    while (arr[right] > pivot) {
      right--
    }
    if (left <= right) {
      swap(arr, left, right)
      left++
      right--
    }
  }
  return left
}

function swap (arr, left, right) {
  const temp = arr[left]
  arr[left] = arr[right]
  arr[right] = temp
}

module.exports = { quickSort }

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

Implementing QuickSort in Javascript with a random pivot

javascript

algorithm

quicksort