javascript实现快速排

快速排序（Quick Sort）是一种常见的排序算法，其核心思想是通过分治的方式逐步缩小待排序的序列范围，从而实现排序。下面我们使用 JavaScript 实现一个快速排序算法。

算法思想

快速排序的算法过程如下：

1. 选择一个基准元素，将它放在序列的正确位置上；
2. 将序列分为左右两部分，其中左边部分的元素都小于基准元素，右边部分的元素都大于或等于基准元素；
3. 递归地对左右两部分执行第 1 步和第 2 步，直到子序列的大小为 1 或 0。

实现过程

下面是使用 JavaScript 实现快排的代码：

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }

  const pivotIndex = Math.floor(array.length / 2);
  const pivot = array.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];

  for (let i = 0; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

实现过程分为三部分：

1. 如果数组的长度小于等于 1，那么直接返回该数组，因为长度为 1 或 0 的数组已经是有序的了，无需排序。
2. 选择一个基准元素 pivot（一般选择中间位置的数），并将其从数组中删除。
3. 遍历整个数组，将小于 pivot 的元素放入左子数组 left 中，大于等于 pivot 的元素放入右子数组 right 中。然后递归地对左右子数组进行快排，最后将结果数组返回。

测试代码

下面是一个测试函数 quickSortTest，用于验证 quickSort 函数的正确性：

function quickSortTest() {
  const testCases = [
    { input: [], expected: [] },
    { input: [5], expected: [5] },
    { input: [3, 5, 1, 6, 4, 2], expected: [1, 2, 3, 4, 5, 6] },
    { input: [5, 4, 3, 2, 1], expected: [1, 2, 3, 4, 5] },
    { input: [1, 2, 3, 4, 5], expected: [1, 2, 3, 4, 5] },
    { input: [5, 5, 5, 5, 5], expected: [5, 5, 5, 5, 5] },
  ];

  testCases.forEach(({ input, expected }) => {
    const result = quickSort(input);
    console.assert(
      JSON.stringify(result) === JSON.stringify(expected),
      `Failed: input=[${input}], result=[${result}], expected=[${expected}]`
    );
  });

  console.log("All test cases pass");
}

总结

快速排序是一种高效的排序算法，它的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。我们使用 JavaScript 实现了快速排序算法，它不仅简单易懂，而且代码量很小，非常适合在实际项目中使用。