快速选择 JavaScript

Question

我在互联网上搜索了所有不同版本的快速排序实现，以将其翻译成 Java脚本，其中许多没有成功移植。

我无法弄清楚这是否是因为我不了解 Java 或 C++ 的细微差别，或者人们发布的示例已损坏。

我不是在优化性能，而是在优化可读性和逻辑性。

我已经完成了这个实现，但我发现它不起作用。

输出是随机的（可能是由于 Math.random()），但是当我遵循算法时，我对以下测试用例感到沮丧。

输出范围为 999、3、100、2 和 1000。我无法遵循逻辑，非常感谢有人解释是什么原因导致出现如此不稳定的结果。

function swap(array, idxA, idxB) {
    var temp = array[idxA] 
    array[idxA] = array[idxB]
    array[idxB] = temp
}

function partitionStart(arr, left, right, pivotIdx) {
  var storeIdx = left, pivotVal = arr[pivotIdx];  
  swap(arr, pivotIdx, right)
  for (var i = left; i <right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, storeIdx, i)
      storeIdx++
    }
  }
  swap(arr, pivotIdx, right);
  return storeIdx;
}

function quickSelectLoop(arr, k) {
  var pivotIndex, pivotNewIdx, pivotDist, 
  left = 0, right = arr.length-1 

  while(true) {
    pivotIndex = Math.floor(Math.random()*arr.length)
    pivotNewIdx = partitionStart(arr, left, right, pivotIndex)
    pivotDist = pivotNewIdx - left

    if (pivotDist === k) {
      return arr[pivotNewIdx-1]
    } else if (k < pivotDist) {
      right = pivotNewIdx -1
    } else {
      k -= pivotDist+1
      left = pivotNewIdx + 1
    }
  }  
}

var test2 = [1000,999,1,2,3,100,105]
console.log(quickSelectLoop(test2, 4))

quickSelect(test2, 4) 的预期输出 => 100，因为 100 是集合中第四小的元素

Answer 1

您当前的实施有多个缺陷。我不太明白你现在的代码是什么意思，所以我会试着解释一下我是如何理解你的代码的，然后提供一个更正的代码。

partitionStart - 使用 pivotIdx 处的项目作为部分分隔符，将数组的一部分从 left 分区到 right 索引。 Returns 分离索引 sepIdx，这样 sepIdx 之前的每一项都小于主元项，而它之后的每一项都大于或等于它。

quickSelectLoop - 从给定数组中选择第 k 个最小的项目。函数依赖于 left 和 right 之间的所有项目的不变性，尽管它们是任意顺序的，但都是数组的 left..right 最小项目，例如

if left = 0, right = 2, 初始数组 = {0,1,2,3,4}, 那么 arr = [A,B,C,x,x]，其中 {A,B,C} = {0,1,2}，所以 arr = [2,1,0,4,3] 和 arr = [0,1,2,3,4] 都是正确的。

更正代码和注释：

function partitionStart(arr, left, right) {  
  // You were passing pivotIdx here, I think that selecting pivotIdx 
  // should be this method's responsibility, so I moved the code here
  // Also you were taking pivotIdx ignoring left and right - fixed that
  var pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left;
  var storeIdx = left, pivotVal = arr[pivotIdx]
  // You had a swap of pivot with the right here, 
  // which allowed you to traverse 1 item less in a cycle, 
  // but with the cost of one line of code - removed that
  for (var i = left; i <= right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, storeIdx, i)
      storeIdx++
    }
  }  
  // Here was a strange swap of pivot back from right to its position,
  // now it is not needed.
  return storeIdx;
}

function quickSelectLoop(arr, k) {  
  var pivotDist;   
  var left = 0, right = arr.length - 1;       
  while(right !== left) {
    // Maintaining: left <= k <= right, while enclosing left to right 
    pivotDist = partitionStart(arr, left, right)        
    // You were returning arr[k] here if pivotDist == k, 
    // but that is incorrect considering function's invariant - 
    // we can't make such a conclusion unless left == right.
    // I corrected that check - it is now located in the while loop.
    if (k < pivotDist) {
      right = pivotDist - 1;
    } else {
      // You were adding 1 here, which is incorrect, 
      // because item at pivotDist may be the answer as well.
      left = pivotDist;
    }
  }    

  // left == right, and we maintained 'left <= k <= right', so we have an answer
  return arr[k]
}

jsfiddle

快速选择 JavaScript

quickselect into JavaScript

javascript

algorithm

quicksort