快速排序算法在JS中的实现

快速排序算法

快速排序是一种比较常用的排序算法，它的时间复杂度为O(nlogn)，是一种不稳定的排序算法。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比一部分的所有数据都要小，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

JS中快速排序的实现

JS中快速排序的实现主要由以下几个步骤组成：

• 1、从数列中取出一个数作为基准数。
• 2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3、再对左右区间重复第二步，直到各区间只有一个数。

JS实现快速排序的示例代码

function quickSort(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

上面的代码实现了快速排序的基本思想，选择一个基准数，将数组中的数据分割成两部分，一部分比基准数小，另一部分比基准数大，将左右两部分数据分别进行快速排序，最终达到排序的目的。