以数组首元素为基准的快排中首次调用getPartitionIndex返回值异常问题

嘿，我瞅你这快速排序里的getPartitionIndex函数出问题了，尤其是首次调用时没法正确返回分区索引对吧？这大概率是分区逻辑里漏了关键的交换步骤，咱们一步步把它捋顺修好～

首先先把你给出的代码整理一下，加上大概率没写完的错误部分（这是这类问题的常见坑点）：

var quickSort = function (arr, left, right) { 
  if (left < right) { 
    const partitionIndex = getPartitionIndex(arr, left, right); 
    quickSort(arr, left, partitionIndex-1); 
    quickSort(arr, partitionIndex+1, right); 
  } 
  return arr; 
} 

// 假设你没写完的错误版本是这样的
var getPartitionIndex = function (arr, left, right) { 
  let pivot = arr[left], 
      partitionIndex = left; 
  for (let i = left + 1; i <= right; i++) { 
    if (arr[i] < pivot) { 
      partitionIndex++; 
      // 坑点1：这里没交换元素，没法把小元素挪到左侧
    } 
  } 
  // 坑点2：最后没把pivot换到正确位置，返回的索引根本不是pivot的最终位置
  return partitionIndex; 
}

问题到底出在哪？ #

• 漏了遍历中的元素交换：找到比pivot小的元素时，只给partitionIndex加1，但没把当前元素和partitionIndex位置的元素交换，这样小于pivot的元素没法聚集到左侧，分区等于白做。
• 没把Pivot归位：遍历完之后，pivot还待在最左边的初始位置，返回的partitionIndex根本不是它该在的地方，后续递归的区间自然全错了。

修复后的完整代码 #

咱们用标准的Lomuto分区方案（就是以首个元素当pivot的常规实现）来改，修复后的代码如下：

var quickSort = function (arr, left, right) { 
  // 加个默认值，外部调用的时候直接传数组就行，不用手动写0和长度-1
  if (typeof left === 'undefined') left = 0;
  if (typeof right === 'undefined') right = arr.length - 1;
  
  if (left < right) { 
    const partitionIndex = getPartitionIndex(arr, left, right); 
    quickSort(arr, left, partitionIndex - 1); 
    quickSort(arr, partitionIndex + 1, right); 
  } 
  return arr; 
} 

var getPartitionIndex = function (arr, left, right) { 
  const pivot = arr[left]; // 以最左侧元素作为pivot
  let partitionIndex = left; // 初始索引设为pivot的位置

  // 从pivot的下一个元素开始遍历到数组末尾
  for (let i = left + 1; i <= right; i++) { 
    // 遇到比pivot小的元素，就把它挪到partitionIndex的右侧
    if (arr[i] < pivot) { 
      partitionIndex++;
      // 交换当前元素和partitionIndex位置的元素
      [arr[partitionIndex], arr[i]] = [arr[i], arr[partitionIndex]];
    } 
  } 

  // 最后把pivot交换到partitionIndex的位置，这才是它的最终正确位置
  [arr[left], arr[partitionIndex]] = [arr[partitionIndex], arr[left]];

  return partitionIndex; // 返回pivot的索引，给后续递归划分区间用
}

关键修复点讲明白 #

• 遍历中的交换：每次找到小于pivot的元素，先把partitionIndex右移一位，再交换当前元素和partitionIndex位置的元素，保证partitionIndex左边的元素全是小于等于pivot的。
• Pivot归位：遍历结束后，把pivot从初始的左端点换到partitionIndex的位置，这时返回的索引才是pivot在排序后数组里的正确位置，后续递归的左右区间才会准确。
• 参数默认值：给quickSort加了left和right的默认值，外部调用的时候直接写quickSort([5,3,8,4,2])就行，不用额外传参数，更方便。

测试一下 #

比如拿数组[5,3,8,4,2]测试，首次调用getPartitionIndex之后，数组会变成[2,3,5,4,8]，返回的partitionIndex是2（也就是pivot元素5的正确位置），接下来递归处理左边的[2,3]和右边的[4,8]，最后就能得到排序好的[2,3,4,5,8]啦～

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