JavaScript 中的快速排序算法

大家好，今天我将向大家展示如何用 Javascript 编写快速排序算法。

快速排序是一种分治算法。它选择一个元素作为枢轴，并围绕该枢轴对给定数组进行分区。快速排序有很多不同的版本，它们选择枢轴的方式各不相同。

始终选择第一个元素作为枢轴。
始终选择最后一个元素作为枢轴（如下实现）。
随机选择一个元素作为枢轴。
选择中位数作为枢轴。
快速排序的关键步骤是 partition() 函数。partition() 函数的目标是：给定一个数组和一个元素 x 作为枢轴，将 x 放到排序后数组的正确位置，并将所有小于 x 的元素放在 x 之前，所有大于 x 的元素放在 x 之后。所有这些操作都应该在线性时间内完成。

以下是代码部分 -

function QuickSort(Arr){
  if(Arr.length <= 1){
    return Arr;
  }

  const pivot = Arr[Arr.length - 1];
  const leftArr = [];
  const rightArr = [];

  for(let i=0; i < Arr.length-1;i++){
    Arr[i] < pivot ? leftArr.push(Arr[i]) :  rightArr.push(Arr[i])
  }

  return [...QuickSort(leftArr) ,pivot,...QuickSort(rightArr)];

}

const items = [1,5,2,99,81,100,144,121,91,85,74,10];
console.log(QuickSort(items));

1. 首先，我们将检查数组的长度，如果长度为 1，则直接返回数组。
2. 然后我们将选择一个枢轴元素，在本例中，它是最后一个元素。
3. 然后我们将创建两个空数组 leftarr 和 rightarr，以便将元素与 pivot 进行比较，并相应地放置元素。
4. 然后我们将使用 for 循环遍历数组，并在循环内部检查每个元素是否小于或大于基准值。
5. 如果元素小于基准值，则将其推入左数组；如果元素大于基准值，则将其推入右数组。
6. 然后我们将递归地对左右数组调用快速排序算法来划分数组，直到数组完全排序为止。

Output - 
[1,2,5,10,74,81,85,91,99,100,121,144]

我是数据结构和算法的新手。所以，如果您发现这篇文章有任何错误，请在评论区指正，
谢谢！

Instagram - https://instagram.com/w_a_a_d_u__h_e_c_k