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

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);

 

上一篇:两点路径


下一篇:元素类型为 “mapper“ 的内容必须匹配 “(cache-ref|cache|resultMap*|parameterMap*|sql*|insert*|update*|delete*|selec