基础算法复习——快速排序

本文主要是介绍基础算法复习——快速排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 最近一直在忙课程，每天只能抽空刷几道LeetCode，好久没看JS了...有点慌，但是先抽空把排序算法啥的写一遍吧，等忙完操作系统课设再好好复习JS.

2. 快速排序算法思想大概就是设定一个基准值，根据基准值不断地交换数组中前后的元素值，在此过程中目的是把基准值排序到最终的位置，再对基准值位置之前和之后的数组元素重复以上过程。

（1）给定一个数组 arr，首先寻找它的基准值 base.

（2）设置指针 low 指向指定数组范围首元素，high 指向指定数组范围末尾元素，并设置变量 left 和 right 保存 low 和 high 的值，因为 low 和 high 之后会变化

（3）只要满足 low < high，则循环进行下面操作：

　　从 high 开始判断，如果 arr[ high ] 大于 base 值，且 low < high，则 high--；

　　若小于 base 值，则 arr[ low ] = arr[ high ]，

　　并且改换为从 low 判断，如果 arr[ low ] 小于 base 值，且 low < high，则 low++；

　　若大于 base 值，则 arr[ high ] = arr[ low ]

（4） 循环结束时，条件必定是 low === high，此时 low 处或 high 处就是 base 基准值最终的位置

（5）我们对数组 [ left, low - 1] 和 [ low + 1, right ] 两个范围元素递归进行 （1）~（4）过程，最终得到的数组即为排序后数组。

function quickSort(arr) {
  function sort(arr, low = 0, high = arr.length - 1) {
    if (low >= high) {
      return;
    }
    let left = low, right = high;
    let base = arr[low];
    while (low < high) {
      while (low < high && arr[high] > base) {
        high--;
      }
      arr[low] = arr[high];
      while (low < high && arr[low] < base) {
        low++;
      }
      arr[high] = arr[low];
    }
    arr[low] = base;
    sort(arr, left, low-1);
    sort(arr, low+1, right);
  }
  const newArr = Array.from(arr);
  sort(newArr);
  return newArr;
}
let arr = [85, 24, 63, 45, 17, 31, 96, 50];
console.log(quickSort(arr));
console.log(arr);

这篇关于基础算法复习——快速排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！