在js中快速排序

Question

帮手

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。当我们遇到一个大于pivot值的数字时，splitIndex将保持其值，i将递增。在下一步中，如果该数字也小于枢轴，我们交换它们

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

谢谢

Answer 1

splitindex变量跟踪（在当前排序的数组的节中）比透视“小”和“等于或大于”的元素之间的分隔符。你对它工作原理的描述似乎基本正确。

通常，如果我们遇到一个比pivot小的元素，我们将其与splitindex处的元素交换，将其放入“small than pivot”部分，然后递增splitindex以指示该部分已增长。如果我们遇到一个相等或更大的，我们就把它留在原地，不增长截面。

假设splitindex处的元素不小于透视，这就有意义了。如果i大于splitindex则是这样，因为我们已经遇到了至少一个这样的元素，并跳过了它。

例外情况是，我们当前正在检查splitindex处的元素（只要所有元素到目前为止都小于pivot就会出现这种情况）。在这种情况下，我们会将元素与其本身进行交换。这是多余的，所以这就是splitindex！==i检查的原因。

至于

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

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