使用JavaScript中的快速排序对文字数组进行排序

Z时代
2024-01-10
分类：综合

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

快速排序：

此算法基本上是分治法，我们在循环的每个遍历中选择一个枢轴，并将所有小于枢轴的元素置于其左侧，而将所有大于枢轴的元素置于其右侧（如果其升序排序相反）

示例

为此的代码将是-

const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// Find a "pivot" element in the array to compare all other
//之前或之后移动元素
//取决于它们的值
const quickSort = (arr, left = 0, right = arr.length - 1) => {
   let len = arr.length, index;
   if(len > 1) {
      index = partition(arr, left, right)
         if(left < index - 1) {
            quickSort(arr, left, index - 1)
         }
         if(index < right) {
            quickSort(arr, index, right)
      }
   }
   return arr
}
const partition = (arr, left, right) => {
   let middle = Math.floor((right + left) / 2),
   pivot = arr[middle],
   i = left, // Start pointer at the first item in the
   array
   j = right // Start pointer at the last item in the
   array
   while(i <= j) {
      //处的值
      //左大于枢轴值
      while(arr[i] < pivot) {
         i++
      }
      //处的值
      //右小于枢轴值
      while(arr[j] > pivot) {
         j--
      }
      //如果左指针小于或等于
      //向右指针，然后交换值
      if(i <= j) {
         [arr[i], arr[j]] = [arr[j], arr[i]] // ES6 destructuring swap
         i++
         j--
      }
   }
   return i
}
console.log(quickSort(arr));