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
41
42
| func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
rand.Seed(time.Now().UnixNano())
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, left, right int) {
if left >= right {
return // 如果左指针大于等于右指针，结束递归
}
// 随机选择基准元素
pointIndex := rand.Intn(right-left+1) + left
nums[left], nums[pointIndex] = nums[pointIndex], nums[left] // 将随机基准放到左边
point := nums[left] // 选择基准
i, j := left, right
// 分区过程
for i < j {
for i < j && nums[j] >= point {
j-- // 从右向左找到小于基准的元素
}
if i < j {
nums[i] = nums[j] // 将小于基准的元素放到左边
i++
}
for i < j && nums[i] <= point {
i++ // 从左向右找到大于基准的元素
}
if i < j {
nums[j] = nums[i] // 将大于基准的元素放到右边
j--
}
}
nums[i] = point // 将基准放到正确的位置
// 递归排序左右部分
quickSort(nums, left, i-1) // 排序左半部分
quickSort(nums, i+1, right) // 排序右半部分
}
|