快速排序
2020-12-13 01:39
标签：golang ret partition pre quick 复杂度 原理 pac 这一 快速排序思想：如果要排数组p到r之间的一组数据，选择p到r之间任意一个一个数据作为pivot（分区点，这里选择的是s[r]作为pivot）。遍历p到r之间的数据，将小于pivot的数据放在左边，其他的放右边。经过这一步骤后数据p到r被分成了三份，前面p～q-1的数据小于pivot，q+1~r的数据大于pivot。接着递归分治实现剩下子分区的排序。 时间复杂度O(nlogn), 空间复杂度O(1) O(n)时间复杂度求数组的第K大数据 快速排序 标签：golang ret partition pre quick 复杂度 原理 pac 这一 原文地址：https://www.cnblogs.com/makelu/p/11004209.html实现原理
代码实现(golang)
1 package main
2
3 import "fmt"
4
5 func quicklySort(s []int) []int {
6 quickylySortImpl(s, 0, len(s)-1)
7 return s
8 }
9
10 func quickylySortImpl(s []int, p, r int) {
11 if p >= r {
12 return
13 }
14 q := partition(s, p, r)
15 quickylySortImpl(s, p, q-1)
16 quickylySortImpl(s, q+1, r)
17 }
18
19 func partition(s []int, p, r int) int {
20 pivot := s[r]
21 i := p
22 for j := p; j {
23 if s[j] pivot {
24 s[i], s[j] = s[j], s[i]
25 i = i + 1
26 }
27 }
28 s[i], s[r] = s[r], s[i]
29 return i
30 }
31
32 func main() {
33 fmt.Println(quicklySort([]int{8, 10, 2, 3, 6, 1, 5}))
34 }
扩展应用