javascript - 分区在我的快速排序功能中不起作用

Question

我一直在研究这个问题，但我无法让我的分区功能工作。我递增起始值，直到它达到小于枢轴的值，反之亦然，我的结束指针。我用我的开始和端点交换值。然后我用我的开始和支点交换价值。我错过了什么吗？

function quickSort(arr, start, end) {
    if (start >= end) {
        return
    }


    let index = partition(arr, start, end)

    quickSort(arr, start, index - 1)
    quickSort(arr, index + 1, end)
    return arr
}

function partition(arr, start, end) {
    let pivotIndex = end 
    let pivotValue = arr[end]
    let endPointer = arr[end - 1] //end pointer start w/ value left of pivot

    while (start <= end) {
        if (arr[start] < pivotValue) {
            start++
        } else {
            swap(arr,start, endPointer)
        }
        if (arr[endPointer] > pivotValue) {
            endPointer--
        } else {
            swap(arr,start, endPointer)
        }
    }

    swap(arr,start, pivotIndex)
    return start


}

function swap(arr, a, b) {
    let temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp 
}

let arr = [0,5,2,1,6,3]
console.log(quickSort(arr, 0, arr.length - 1))

标签： javascriptarraysquicksortpartitioning

Answer 1

配分函数似乎是 Hoare 的一种变体。有几个问题（endPointer 应该是 end-1，而不是 arr[end-1]; while (start < endPointer); if/else/swap if/else/swap 应该是 while / while / swap / 再次增加索引 / ...) 并且通过使用最后一个值作为枢轴意味着向后扫描将需要检查它是否已在开始以下递减。通常，Hoare 依赖于运行到枢轴，因此枢轴是从中间选择的，或者至少不是从第一个或最后一个元素中选择。这是一个将分区代码合并到快速排序函数中的“经典”Hoare 示例：

function quicksort(a, lo, hi) {
  if(lo >= hi)
    return;
  var p = a[Math.floor(lo+(hi-lo)/2)];
  var i = lo - 1;
  var j = hi + 1;
  var t;
  while (true){
    while (a[++i] < p);
    while (a[--j] > p);
    if (i >= j)
      break;
    t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
  quicksort(a, lo, j);
  quicksort(a, j+1, hi);
}

由于代码使用最后一个值作为枢轴值，因此另一种选择是 Lomuto 分区方案：

function quicksort(a, lo, hi) {
  if(lo >= hi)
    return;
  var p = a[hi];
  var i = lo;
  var j;
  var t;
  for(j = lo; j < hi; j++){
    if(a[j] < p){
      t = a[i];
      a[i] = a[j];
      a[j] = t;
      i++;
    }
  }
  t = a[i];
  a[i] = a[hi];
  a[hi] = t;
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}