快速排序（Quicksort）中Partition函数无法正常工作的问题排查

嘿，我仔细看了你的快排实现，确实partition函数里有几个关键问题导致它没法正常工作，咱们一步步拆解修复：

核心问题点 #

• endPointer初始化错误：你写的let endPointer = arr[end - 1]是把数组元素的值赋值给了指针，但这里需要的是索引，不是元素值！应该改成let endPointer = end - 1，否则后续用它作为数组下标操作时，完全是在操作错误的位置。
• 循环逻辑混乱：你在同一个while循环里同时处理start和endPointer的判断，还在每个分支里直接执行交换，这会导致重复交换、逻辑跳步，甚至数组越界。标准的partition逻辑应该是先分别找到需要交换的两个元素，再执行交换操作。
• 交换时机错误：你在每个if分支里直接交换，而不是等找到一对不符合pivot划分规则的元素后再交换，这会打乱数组的正常遍历顺序。

修复后的完整代码 #

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 = end - 1; // 修正：初始化指针为索引，不是元素值

  while (start <= endPointer) {
    // 移动start指针，找到第一个大于等于pivot的元素
    while (start <= endPointer && arr[start] < pivotValue) {
      start++;
    }
    // 移动endPointer指针，找到第一个小于等于pivot的元素
    while (start <= endPointer && arr[endPointer] > pivotValue) {
      endPointer--;
    }
    // 如果两个指针还没交叉，交换元素并继续移动指针
    if (start <= endPointer) {
      swap(arr, start, endPointer);
      start++;
      endPointer--;
    }
  }
  // 最后将pivot交换到正确的位置（start指针的位置）
  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)); // 输出：[0,1,2,3,5,6]

修复后的逻辑说明 #

1. 先初始化endPointer为end-1（pivot的前一个索引），确保操作的是正确的数组位置。
2. 在循环中，先单独移动start直到找到大于等于pivot的元素，再单独移动endPointer直到找到小于等于pivot的元素。
3. 当两个指针未交叉时，交换这两个元素，然后同时移动指针继续遍历。
4. 循环结束后，start的位置就是pivot应该在的位置，交换pivot和start指向的元素，返回这个索引作为后续递归的分界点。

内容的提问来源于stack exchange，提问作者Seattle206