这个快速排序逻辑正确吗？

Question

我曾尝试在Javascript中实现Quick-Sort，但没有引用任何psuedo代码。这是正确的实现吗？如果没有，我怎么能改进它呢？

​

const quickSort = (arr = []) => {
  const length = arr.length;
  if (length === 0 || length === 1) {
    return arr;
  }

  const pivot = arr[0];
  const leftArray = [];
  const rightArray = [];
  for (let i = 1; i < length; i++) {
    if (arr[i] < pivot) {
      leftArray.push(arr[i]);
    } else {
      rightArray.push(arr[i]);
    }
  }
  return [...quickSort(leftArray), pivot, ...quickSort(rightArray)];
};

console.log(quickSort([2, 45, 6, 7, 8, 1]));

​

我已经添加了测试用例的代码，并执行了超过250000次。

// Function to generate random array.
const generateRandomArray = n =>
  Array.from({
    length: n
  }, () => Math.floor(Math.random() * n));

// Function to check whether array is sorted.
const checkSorted = (arr = []) => {
  let sorted = true;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      sorted = false;
      break;
    }
  }
  return sorted;
};

// Testing Quick-Sort
const testQuickSort = () => {
  for (let i = 1; true; i++) {
    const sortedArray = quickSort(generateRandomArray(Date.now() % 100000));
    const isSorted = checkSorted(sortedArray);
    if (!isSorted) {
      console.log("error");
      break;
    }
    console.log("pass", i);
  }
};

testQuickSort();

Answer 1

您可以尝试以下解决方案

​

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  // We are assuming the pivot is always the first element
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  // Swap the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}


function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivotIndex-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
           
console.log(quickSort([100,-3,2,4,6,9,1,2,5,3,23]));

​