乐闻世界logo
搜索文章和话题
中文
JavaScript 实现快速排序算法

JavaScript 实现快速排序算法

乐闻的头像
乐闻

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

前言

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

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

基本思想

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

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

实现思路

首先,我们定义 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,则没有必要排序,直接返回数组本身。接下来,我们选择数组的第一个元素作为基准值,并定义了两个新数组 leftright来分别存储小于和大于基准值的元素。我们遍历原数组(从第二个元素开始,因为第一个是基准值),根据元素与基准值的大小关系,将元素推入 leftright数组。最后,我们递归地对 leftright数组进行快速排序,并在最终结果中,将这两个数组与基准值合并。

优化思路

虽然上述实现简单易懂,但它并不是最高效的算法实现。例如,它在空间复杂度上有所欠缺,因为它创建了额外的数组。在实际应用中,我们通常会在原地(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)来跟踪应该插入小于基准值的元素的位置。遍历数组时,我们将小于或等于基准值的元素与分区索引处的元素交换位置,并逐步移动分区索引。遍历结束后,我们将基准值放到分区索引的位置,确保基准值左侧的所有元素都不大于基准值,而右侧的所有元素都不小于基准值。

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

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

标签: