JavaScript 实现快速排序算法

乐闻

2022年03月24日 12:27· 阅读 668

前言

快速排序，一种被广泛认可和使用的排序算法，因为其高效率和优秀的平均案例性能而闻名。它的核心理念是“分而治之”，通过递归的方式将大问题化成小问题解决。

本篇文章将介绍如何使用JavaScript来实现这个算法，让你的数组排列得井井有条。

基本思想

快速排序的基本思想非常简单：

选择基准值（Pivot）：从数组中选择一个元素作为基准值，通常选择第一个元素或最后一个元素。
分区操作（Partitioning）：重新排列数组，所有比基准值小的元素统一放到基准值的一侧，所有比基准值大的元素放到另一侧。分区完成后，基准值所处的位置就是它最终的排序位置。
递归排序：递归地将小于基准值的部分数组和大于基准值的部分数组进行排序。

实现思路

首先，我们定义 quickSort函数，它接受一个数组 arr作为参数：

javascript
function quickSort(arr) {
  // 如果数组长度小于等于1，就没有排序的必要了
  if (arr.length <= 1) {
    return arr;
  }

  // 选择基准值，这里我们选择第一个元素
  const pivot = arr[0];

  // 定义两个数组，分别存储小于和大于基准值的元素
  let left = [];
  let right = [];

  // 遍历数组，根据与基准值的比较结果，分配到不同的数组中
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 利用递归继续分别对左右两部分进行排序
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 使用示例
const sortedArray = quickSort([5, 3, 7, 6, 2, 9]);
console.log(sortedArray); // 输出: [2, 3, 5, 6, 7, 9]

在这段代码中，我们首先检查了数组的长度，如果数组长度小于等于1，则没有必要排序，直接返回数组本身。接下来，我们选择数组的第一个元素作为基准值，并定义了两个新数组 left和 right来分别存储小于和大于基准值的元素。我们遍历原数组（从第二个元素开始，因为第一个是基准值），根据元素与基准值的大小关系，将元素推入 left或 right数组。最后，我们递归地对 left和 right数组进行快速排序，并在最终结果中，将这两个数组与基准值合并。

优化思路

虽然上述实现简单易懂，但它并不是最高效的算法实现。例如，它在空间复杂度上有所欠缺，因为它创建了额外的数组。在实际应用中，我们通常会在原地（in-place）进行分区操作，而不是创建新数组，这样可以减少内存使用，并提高算法效率。

在进一步优化之前，请确保你已经理解了基本的快速排序概念。然后，你可以开始探索如何在原数组上进行,操作，以减少不必要的内存开销。这种原地快速排序的实现要复杂一些，但它能提供更好的性能，尤其是在处理大数据集时。

以下是原地快速排序算法的 JavaScript 实现：

javascript
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left < right) { // 递归的基本出口条件
    // 对数组进行分区，并获取分区后基准值所在位置的索引
    const pivotIndex = partition(arr, left, right);
  
    // 分别对基准值左侧和右侧的子数组进行递归排序
    quickSortInPlace(arr, left, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  // 选择基准值，这里我们选择区间末尾的元素
  const pivot = arr[right];
  let partitionIndex = left; // 分区索引

  for (let i = left; i < right; i++) {
    // 如果当前元素小于或等于基准值，交换当前元素与分区索引处的元素
    if (arr[i] <= pivot) {
      [arr[i], arr[partitionIndex]] = [arr[partitionIndex], arr[i]];
      partitionIndex++; // 移动分区索引
    }
  }
  
  // 交换基准值与分区索引处的元素，将基准值放到正确的位置
  [arr[partitionIndex], arr[right]] = [arr[right], arr[partitionIndex]];
  return partitionIndex;
}

// 使用示例
const unsortedArray = [5, 1, 9, 3, 7, 2, 8, 6, 4];
const sortedArray = quickSortInPlace(unsortedArray);
console.log(sortedArray); // 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]

在这个版本的快速排序中，我们新增了 partition函数，它的作用是在原数组上执行分区操作。在该函数中，我们选择区间末尾的元素作为基准值，然后使用一个分区索引（partitionIndex）来跟踪应该插入小于基准值的元素的位置。遍历数组时，我们将小于或等于基准值的元素与分区索引处的元素交换位置，并逐步移动分区索引。遍历结束后，我们将基准值放到分区索引的位置，确保基准值左侧的所有元素都不大于基准值，而右侧的所有元素都不小于基准值。

这样，我们就在原地完成了数组的分区操作，之后递归地对分区后的子数组进行同样的操作，直到整个数组排序完成。

通过这种方式，我们避免了创建额外的数组，但仍然利用了快速排序算法高效的分而治之策略。经过这样的优化，快速排序成为了一个在实际开发中非常实用的工具，能够处理大量数据的同时保持优异的性能。

标签：

算法