排序算法 | Peanuts' Blog

排序算法

复习经典排序算法,按照面试优先级复习 :)

快速排序(Quicksort)

平均时间复杂度n*logn,最坏时间复杂度n^2

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
//QuickSort 快速排序
func QuickSort(nums []int, start, end int) {
if start >= end {
return
}
left, right := start, end
pivot := nums[left]
for left < right {
for left < right && nums[right] >= pivot {
right--
}
if left < right {
nums[left] = nums[right]
}
for left < right && nums[left] <= pivot {
left++
}
if left < right {
nums[right] = nums[left]
}
if left >= right {
nums[left] = pivot
}

QuickSort(nums, start, left-1)
QuickSort(nums, left+1, end)
}

}