LeetCode 补充题 4. 手撕快速排序
题目描述
思路分析
快速排序
✅ 生成 [a, b] 范围的随机数（包含 b）:
rand.Intn(b-a+1) + a✅ 生成 [a, b) 范围的随机数（不包含 b）:
rand.Intn(b - a) + a
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, left, right int) {
if left >= right {
return
}
// 随机选择基准元素
pivotIndex := rand.Intn(right-left+1) + left
nums[left], nums[pivotIndex] = nums[pivotIndex], nums[left]
pivot := nums[left]
i, j := left, right
for i < j {
for i < j && nums[j] >= pivot {
j--
}
if i < j {
nums[i] = nums[j] // 将小于基准的元素放到左边
i++
}
for i < j && nums[i] <= pivot {
i++
}
if i < j {
nums[j] = nums[i] // 将大于基准的元素放到右边
j--
}
}
nums[i] = pivot
quickSort(nums, left, i-1)
quickSort(nums, i+1, right)
}
- 时间复杂度：
- 平均情况：O (n log n)
- 最坏情况：O (n^2)
- 最好情况：O (n log n)
- 空间复杂度：O (log n)
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！