quickselect into JavaScript

Question

我已经在互联网上搜索了所有不同版本的quicksort实现，以转换为JavaScript，但其中许多都没有成功移植。

我还不能弄清楚这是因为我不知道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 -将数组的一部分从left分区到right索引，使用pivotIdx处的项作为部分分隔符。返回分隔sepIdx的索引，这样sepIdx之前的每一项都小于透视表项，而它之后的每一项都大于或等于它。

quickSelectLoop -从给定数组中选择第k个最小项。函数依赖于不变量，即left和right之间的所有项都是数组的left。right最小项，例如

如果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