Go数据结构与算法-快速排序

---

title: Go数据结构与算法-快速排序
tags: go,算法

---

介绍

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。快速排序是冒泡排序的优化版，同属于交换类排序。它使用了 “分治法” 的思想，将集合分割为相似子集，再对子集进行递归排序，最后将子集的排序结果组合即可。

基本思想

使用分治法

• 先从数列中取出一个数作为key值；
• 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
• 对左右两个小数列重复第二步，直至各区间只有1个数。

算法复杂度

平均时间复杂度：O(N*logN)

排序过程

使用数组[27 38 12 39 27 16]

[UNSORTED]:      [27 38 12 39 27 16]
[DEBUG low]:     []
[DEBUG high]:    [16]
[DEBUG low]:     [27]
[DEBUG high]:    [39]
[DEBUG low]:     [12 16]
[DEBUG high]:    [27 38 39]
[SORTED]:        [12 16 27 27 38 39]
1
2
3
4
5
6
7
8

使用场景

适用于大规模无序数据排序。

演示

package main

import (
	"algorithms"
	"fmt"
)

func main() {

	arr := algorithms.GetArr(5, 20)
	//arr = []int{27, 38, 12, 39, 27, 16}
	fmt.Println("[UNSORTED]:\t", arr)
	fmt.Println("[SORTED]:\t", quickSort(arr))
}

func quickSort(arr []int) []int {

	n := len(arr)
	// 递归结束条件
	if n <= 1 {
		temp := make([]int, n)
		copy(temp, arr)
		return temp
	}

	// 使用第一个元素作为基准值
	pivot := arr[0]

	// 小元素 和 大元素各成一个数组
	low := make([]int, 0, n)
	high := make([]int, 0, n)

	// 更小的元素放 low[]
	// 更大的元素放 high[]
	for i := 1; i < n; i++ {
		if arr[i] < pivot {
			low = append(low, arr[i])
		} else {
			high = append(high, arr[i])
		}
	}
	// 子区间递归快排，分治排序
	low, high = quickSort(low), quickSort(high)
	fmt.Println("[DEBUG low]:\t", low)
	fmt.Println("[DEBUG high]:\t", high)
	return append(append(low, arr[0]), high...)
}

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
43
44
45
46
47
48