JavaScript 快速排序递归

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/1/11 15:40:17

我们需要编写一个 JavaScript 函数，该函数接受一个数字数组。该函数应应用快速排序算法对数组进行升序或降序排序。

快速排序算法

快速排序遵循以下步骤 −

步骤 1 − 将任何元素作为枢轴(最好是第一个或最后一个，但任何元素都可以是枢轴)

步骤 2 − 根据枢轴对数组进行分区

步骤 3 − 递归地对左侧分区应用快速排序

步骤 4 −递归地对右侧分区应用快速排序

QuickSort 的平均和最佳情况下的时间复杂度为 O(nlogn)，而在最坏情况下，其时间复杂度可能会降低至 O(n^2)。

示例

其代码为 −

const arr = [5,3,7,6,2,9];
const swap = (arr, leftIndex, rightIndex) => {
   let temp = arr[leftIndex];
   arr[leftIndex] = arr[rightIndex];
   arr[rightIndex] = temp;
};
const partition = (arr, left, right) => {
   let pivot = arr[Math.floor((right + left) / 2)];
   let i = left;
   let j = right;
   while (i <= j) {
      while (arr[i] < pivot) {
         i++;
      };
      while (arr[j] > pivot) {
         j--;
      };
      if (i <= j) {
         swap(arr, i, j); //交换两个元素
         i++;
         j--;
      };
   };
   return i;
}
const quickSort = (arr, left = 0, right = arr.length - 1) => {
   let index;
   if (arr.length > 1) {
      index = partition(arr, left, right);
      if (left < index - 1) {
         quickSort(arr, left, index - 1);
      };
      if (index < right) {
         quickSort(arr, index, right);
      };
   }
   return arr;
}
let sortedArray = quickSort(arr);
console.log(sortedArray);