|
快速排序的难点在于，根据锚点划分为2个子区间，经典解法是这样：
- 使用 i、j 两个指针，从左右两边双向扫描，直到 i、j 相遇
- 一会移动 i 指针，一会移动 j 指针，容易弄晕
本文只需 1个指针，从左向右单向扫描，更加容易理解和记忆，大致思路如下：
- 经典解法是扫描结束后，才得到2个子区间
- 本解法初始就划分为2个子区间，其中
- 左区间：只有锚点 1个元素
- 右区间：有 n-1 个元素，待检测
- 从 left+1 ~ right 开始扫描
- 每遇到一个小于锚点的元素，就将其交换到左区间，左区间长度加1
- 当扫描完毕后，再将锚点交换到左区间最后一个位置，完成分区
代码实现
package main
import (
"fmt"
)
func qsort(nums []int) []int {
quicksort(nums, 0, len(nums)-1)
return nums
}
func quicksort(nums []int, left, right int) {
if left >= right {
return
}
pivot := nums[left]
mid := left
for i := left + 1; i <= right; i++ {
if nums[i] < pivot {
mid++ //左区间长度加1，然后将 元素i 交换到左区间
nums[mid], nums[i] = nums[i], nums[mid]
}
}
// 锚点交换到 左区间 最后一个位置
nums[left], nums[mid] = nums[mid], nums[left]
quicksort(nums, left, mid-1)
quicksort(nums, mid+1, right)
}
func main() {
fmt.Println(qsort([]int{1, 3, 5, 4, 2, 9, 1, 2, 2}))
fmt.Println(qsort([]int{1, 1, 1, 3, 3, 3, 2, 2, 2, 4, 4, 4}))
fmt.Println("Hello World")
}
| 
转播
