javascript - js中的快速排序

Question

我找到了这个article在媒介上，我试图弄清楚代码实际上是做什么的。

这是代码:

helper

const defaultComparator = (a, b) => {
  if (a < b) {
    return -1;
  }
  if (a > b) {
    return 1;
  }
  return 0;
};

排序功能

const quickSort = (
  unsortedArray,
  comparator = defaultComparator
) => {

  // Create a sortable array to return.
  const sortedArray = [ ...unsortedArray ];

  // Recursively sort sub-arrays.
  const recursiveSort = (start, end) => {

    // If this sub-array is empty, it's sorted.
    if (end - start < 1) {
      return;
    }

    const pivotValue = sortedArray[end];
    let splitIndex = start;
    for (let i = start; i < end; i++) {
      const sort = comparator(sortedArray[i], pivotValue);

      // This value is less than the pivot value.
      if (sort === -1) {

        // If the element just to the right of the split index,
        //   isn't this element, swap them.
        if (splitIndex !== i) {
          const temp = sortedArray[splitIndex];
          sortedArray[splitIndex] = sortedArray[i];
          sortedArray[i] = temp;
        }

        // Move the split index to the right by one,
        //   denoting an increase in the less-than sub-array size.
        splitIndex++;
      }

      // Leave values that are greater than or equal to
      //   the pivot value where they are.
    }

    // Move the pivot value to between the split.
    sortedArray[end] = sortedArray[splitIndex];
    sortedArray[splitIndex] = pivotValue;

    // Recursively sort the less-than and greater-than arrays.
    recursiveSort(start, splitIndex - 1);
    recursiveSort(splitIndex + 1, end);
  };

  // Sort the entire array.
  recursiveSort(0, unsortedArray.length - 1);
  return sortedArray;
};

所以，我花了一些时间来弄清楚 splitIndex 是如何工作的。它从 0 开始，仅当 for 循环中的当前元素小于主元时，它才会递增 1。当我们遇到大于主元值的数字时，splitIndex 保持其值，并且 i 会递增。在下一步中，如果数字也小于主元，我们将交换它们

例如，对于这个数组:[2,4,65,1,15]，在 for 循环期间，splitIndex 和 i 相等，直到我们得到数字 65。这里 splitIndex 是不增加，当我们到达数字 1 时，我们交换 1 和 65。

我不是以英语为母语的人，所以我不完全理解作者的意思:

 // If the element just to the right of the split index,
        //   isn't this element, swap them.

我必须完全理解代码是如何工作的，但是，您认为我所说的是正确的吗？

谢谢

Answer 1

splitIndex 变量跟踪(在当前正在排序的数组部分中)“小于”和“等于或大于”主元的元素之间的分隔符。您对其工作原理的描述似乎基本正确。

一般来说，如果我们遇到小于主元的元素，我们会将其与 splitIndex 处的元素交换，将其放入“小于主元”部分，然后递增 splitIndex 指示该部分已增长。如果我们遇到一个相等或更大的部分，我们会将其保留在原处，并且不会增大该部分。

这是有道理的假设 splitIndex 处的元素不小于主元。如果 i 大于 splitIndex 则成立，因为这样我们已经遇到至少一个这样的元素，并跳过它。

异常(exception)情况是，如果我们当前检查splitIndex处的元素(只要到目前为止所有元素都小于枢轴，就会出现这种情况)。在这种情况下，我们将与元素本身交换。这是多余的，因此这就是 splitIndex !== i 检查的原因。

至于

    // If the element just to the right of the split index,
    //   isn't this element, swap them.

我怀疑作者在评论中犯了一个微小的错误。它应该说“拆分索引处的元素”，而不是“拆分索引右侧的元素”。