前言
上次使用的是双边循环法，这次补充一下单边循环法。
双边循环法从数组的两边交替遍历元素，虽然更加直观，但是代码实现相对繁琐。而单边循环法则简单得多，值从数组的一边进行遍历和交换。直接上代码
正文
函数签名不变：
function quick_sort(input: number[], start: number, end: number) { if (start >= end) { return } let pivotIndex = partition(input, start, end) quick_sort(input, start, pivotIndex - 1) quick_sort(input, pivotIndex + 1, end) }
不同的是 partition 函数
function partition(input: number[], start: number, end: number): number { let pivot = input[start] // 1. let mark = start // 2. for (let i = start + 1; i <= end; i++) { // 3. A. if (input[i] < pivot) {// 4. 每次是正在移动的元素(input[i])，与基准元素比较的值（pivot） mark++ // 5. [input[i], input[mark]] = [input[mark], input[i]] // 6. } } input[start] = input[mark] // 7. input[mark] = pivot return mark }
- 设定基准元素时最左边的元素
- 设定最后要与基准元素交换的元素的下标是最左边元素的下边
- 这里只列出说明：因为选的是最左边元素，比较的话也是和基准元素自身比较，所以此处是start + 1,第一次比较就不需要了
- 这里要划重点：每次是正在移动的元素(input[i]) -> i，与基准元素比较的值（pivot）-> pivot，切记这里的下标和比较对象很容易出错
- 当当前元素的值比基准元素小的时候，最后要与基准元素交换的元素下标右移
- 当当前元素的值比基准元素小的时候，最后要与基准元素交换的元素的值与当前元素交换
- 最后要与基准元素交换的元素与基准元素交换值
A.这里强调一下：“=start+1”是起点，“<=end”是重点，注意边界。A.[2021-08-19 补充~]
继续核对结果
let input = [2, 4, 2, 4, 4, 32, 5, 3, 5, 53, 5, 53, 3, 5, 5, 53,] console.log("start -> ", input.toString()) quick_sort(input, 0, input.length - 1) console.log("end -> ", input.toString())
核对结果
