Created
May 2, 2024 14:26
-
-
Save weedsx/d50b56c48f850323ba9ea52c7df9eef7 to your computer and use it in GitHub Desktop.
随机快速排序 O(n * logn)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package sort | |
| import "math/rand" | |
| // QuickSort 随机快速排序改进版，时间复杂度收敛至 O(n * logn) | |
| func QuickSort(arr []int) []int { | |
| var first, last int | |
| // 已知arr[l....r]范围上一定有x这个值 | |
| // 划分数组 小于x放左边，等于x放中间，大于x放右边 | |
| // 把全局变量first, last，更新成等于x区域的左右边界 | |
| partition := func(arr []int, l, r, x int) { | |
| first, last = l, r | |
| i := l | |
| for i <= last { | |
| if arr[i] == x { | |
| i++ | |
| } else if arr[i] < x { | |
| arr[first], arr[i] = arr[i], arr[first] | |
| i++ | |
| first++ | |
| } else { | |
| arr[last], arr[i] = arr[i], arr[last] | |
| last-- | |
| } | |
| } | |
| } | |
| var recursion func(arr []int, l, r int) | |
| recursion = func(arr []int, l, r int) { | |
| if l >= r { | |
| return | |
| } | |
| // 此处随机能在概率上把快速排序的时间复杂度收敛到O(n * logn) | |
| x := arr[l+rand.Intn(r-l+1)] | |
| partition(arr, l, r, x) | |
| left, right := first, last | |
| recursion(arr, l, left-1) | |
| recursion(arr, right+1, r) | |
| } | |
| if len(arr) > 1 { | |
| recursion(arr, 0, len(arr)-1) | |
| } | |
| return arr | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment