我用了蒂莫西·拉夫花园的隔板,他选择了第一个元素,但并没有完全按照我想要的方式工作。

function swap(items, firstIndex, secondIndex){
  var temp = items[firstIndex];
  items[firstIndex] = items[secondIndex];
  items[secondIndex] = temp;
}


function partition(arr, left, right) {
  left = left || 0;
  right = right || arr.length - 1;
  var pivot = arr[0];
  var i = left + 1;
  for (var j = left + 1; j < right; j++) {
    if (arr[j] < pivot) {
      swap(arr, j, i);  //need to swap with left most array entry which is currently bigger than pivot
      i++;
    }
  }
  //swap pivot with right most element smaller than the pivot (i-1)
  swap(arr, left, i-1)
  // console.log(arr);
  // return i;
  return i - 1;
}



function quickSort(arr, start, end) {
  start = start || 0;
  end = end || arr.length - 1;

  var pivotNewIndex = partition(arr, start, end);

  if (start < end) {
    quickSort(arr, start, pivotNewIndex - 1);
    quickSort(arr, pivotNewIndex + 1, end);
  }
  return arr;
}


var arr4 = [3, 8, 2, 1, 5];


console.log(quickSort(arr4)); --- > [ 1, 2, 3, 8, 5 ];

我在这里做错什么了?我想结局是从最初的结局被重新分配的,我该如何阻止

最佳答案

在此处选择整个数组的第一个元素作为工作范围的轴:
var pivot = arr[0];
但必须使用当前段的第一个元素
var pivot = arr[left];
检查并调试分区周期必须有两个指针,一个从段的左端开始,另一个从段的右端开始。但我看到两个人都是从左向右走的(对JS的了解不足以纠正这个问题)

关于javascript - 在javascript中实现quickSort时遇到麻烦,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33460003/

10-13 02:00
查看更多