以下模块以Golang调试
桶排序(简化版)
桶排序，受限于所需要排序的数字区间，也就是说，当所需要排序的数字足够大的时候，就需要申请足够容纳数字最大值长度的内容空间，只需要对数字区间内的几个数字做排序；浪费空间；
复杂度：O(M+N)
func bucketSort() {
var (
input = []int{1, 8, 3, 5, 2, 4, 5}
result = []int{}
)
for i := 0; i <= 10; i++ {
result = append(result, 0)
}
for _, value := range input {
result[value] += 1
}
for index, value := range result {
if value > 0 {
for i := 0; i < value; i++ {
if i < len(result)-1 {
fmt.Printf(" %v ", index)
} else {
fmt.Printf(" %v \n", index)
}
}
}
}
}
冒泡排序
每相邻的两位数进行排序，每次便利需要比较数组长度次数的数字，以上称为趟，总共需要比较数组长度-1趟；
排序复杂度：O(N2)
func bubbleSort() {
var (
input = []int{1, 8, 3, 5, 2, 4, 5}
)
fmt.Printf("before sort input : %v\n", input)
for index := 1; index <= len(input)-1; index++ {
for i, j := 0, 1; j < len(input); i, j = i+1, j+1 {
x, y := input[i], input[j]
if x < y {
tmp := x
input[i] = y
input[j] = tmp
}
}
}
fmt.Printf("after sort input : %v\n", input)
}
快速排序
快速排序，基于二分思想，以一个基准对象为分割，分割对象左右两边分别冒泡兑换，结果变成分割对象左右两边分别是大、小对象集合；然后再将两个集合依照上述的二分方式再次分割，直至全部排序，此处实现需要用到递归算法；
排序复杂度：O(N2), 平均时间复杂度：O(NlogN)
func main() {
var (
input = []int{6, 1, 2, 7, 9, 3, 4, 5, 10, 8}
)
fastSort(input)
fmt.Println("=========================> ", input)
}
func fastSort(arr []int) {
if len(arr) > 1 {
var (
base = arr[0]
focus int
)
for j := len(arr) - 1; j >= 0; j-- {
if j == focus {
break
}
if arr[j] < base {
for i := focus; i <= j; i++ {
if arr[i] > base {
tmp := arr[i]
arr[i] = arr[j]
arr[j] = tmp
focus = i
break
}
focus = i
}
}
}
tmp := arr[focus]
arr[focus] = arr[0]
arr[0] = tmp
fmt.Println("=========================> ", arr)
fastSort(arr[:focus])
fastSort(arr[focus+1:])
}
}
// 结果:
// =========================> [3 1 2 5 4 6 9 7 10 8]
// =========================> [2 1 3 5 4]
// =========================> [1 2]
// =========================> [4 5]
// =========================> [8 7 9 10]
// =========================> [7 8]
// =========================> [1 2 3 4 5 6 7 8 9 10]
Note：转载注明出处！
有疑问加站长微信联系（非本文作者）
