JavaScript 快速排序算法实现详解

核心原理

假设要排序的数组是 A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为基准数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的具体步骤如下：

1. 初始化变量：设置两个变量 low、high，排序开始的时候：low=0，high=N-1；
2. 选择基准值：以第一个数组元素作为基准数据，赋值给 base，即 base=A[0]；
3. 从后向前搜索：从 high 开始向前搜索（即由后开始向前搜索 high--），找到第一个小于 base 的值 A[high]，将 A[high] 和 A[low] 互换；
4. 从前向后搜索：从 low 开始向后搜索（即由前开始向后搜索 low++），找到第一个大于 base 的 A[low]，将 A[low] 和 A[high] 互换；
5. 重复操作：重复第 3、4 步，直到 low=high。

JavaScript 代码实现

在 JavaScript 中，我们可以通过定义 partition（分区）函数和 sort（递归排序）函数来实现这一逻辑。

function partition(elements, low, high){
  //默认将左侧首元素作为基准元素
  var base=elements[low];
  while(low < high){
    //从后往前搜索，直到找到比基准元素小的元素，并进行交换
    while(low < high && elements[high] >= base) high--;
    var swap1=elements[low];elements[low]=elements[high];elements[high]=swap1;
    //从前往后搜索，直到找到比基准元素大的元素，并进行交换
    while(low < high && elements[low] <= base) low++;
    var swap2=elements[low];elements[low]=elements[high];elements[high]=swap2;
  }
  //返回基准元素的位置，作为序列的分割位置
  return low;
}

function sort(elements, low, high){
  if(low<high){
    //将序列一分为二，分为分割位置的前后序列，前序列比分割位置的值小，后序列比分割位置的值大
    var partitionPos=partition(elements, low, high);
    //对前序列继续递归排序
    sort(elements, 0, partitionPos-1);
    //对后序列继续递归排序
    sort(elements, partitionPos+1, high);
  }
}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements, 0, elements.length-1);
console.log(' after: ' + elements); 

性能分析

• 时间复杂度：最好情况 O(nlog₂n)，最坏情况 O(n²)，平均情况 O(nlog₂n)。在大多数实际应用中，其性能表现优异。
• 空间复杂度：主要是递归调用栈带来的开销，约为 O(log n)。但在某些极端或特定的实现下，可能会被视为 O(nlog n) 级别的空间消耗考量，具体取决于系统栈的大小限制和递归深度。
• 稳定性：不稳定。相等元素的相对位置可能发生变化。

以上就是 JavaScript 快速排序算法的详细内容，更多关于 JavaScript 算法资料的关注本站其它相关文章！