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