- 奇偶排序
- 归并排序
- 希尔排序
- 基数排序
- 统计排序
奇偶排序
先对奇数位进行排序，再对偶数位进行排序， 直到 奇数位，偶数位都不需要排序（不需要交换）
1package main
2
3import "fmt"
4
5// 9 2 1 6 0 7
6// 2 9 1 6 0 7 所有奇数位与身后的相邻的偶数位比较交换
7// 2 1 9 0 6 7所有偶数位与身后的相邻的奇数位比较交换
8//1 2 09 6 7 所有奇数位与身后的相邻的偶数位比较交换
9//1 0 2 6 9 7 所有偶数位与身后的相邻的奇数位比较交换
10//0 1 2 6 7 9 所有奇数位与身后的相邻的偶数位比较交换
11
12func OddEven(arr []int) []int {
13
14 isSorted := false //奇数位，偶数位都不需要排序的有序
15
16 for isSorted == false {
17 isSorted = true
18 for i := 1; i < len(arr)-1; i = i + 2 { //奇数位
19 if arr[i] > arr[i+1] { //需要交换换
20 arr[i], arr[i+1] = arr[i+1], arr[i]
21 isSorted = false
22 }
23 }
24 fmt.Println("1", arr)
25 for i := 0; i < len(arr)-1; i = i + 2 { //偶数位
26 if arr[i] > arr[i+1] { //需要交换换
27 arr[i], arr[i+1] = arr[i+1], arr[i]
28 isSorted = false
29 }
30 }
31 fmt.Println("0", arr)
32 }
33 return arr
34
35}
36
37func main() {
38 arr := []int{1, 9, 2, 8, 3, 7, 4, 6, 5, 10}
39 fmt.Println(OddEven(arr))
40}
归并排序
把排序数组分成多端，再合并
1package main
2
3import "fmt"
4
5//把元素分成2端分别排序 在合并
6//1,9,2,8,3, 7,4,6,5,10
7
8//1 2 3 8 9 // 456 7 10
9//12345678910
10func merge(leftarr []int, rightarr []int) []int {
11 leftindex := 0 //左边索引
12 rightindex := 0 //右边索引
13 lastarr := []int{} //最终的数组
14 for leftindex < len(leftarr) && rightindex < len(rightarr) {
15 if leftarr[leftindex] < rightarr[rightindex] {
16 lastarr = append(lastarr, leftarr[leftindex])
17 leftindex++
18
19 } else if leftarr[leftindex] > rightarr[rightindex] {
20 lastarr = append(lastarr, rightarr[rightindex])
21 rightindex++
22 } else {
23 lastarr = append(lastarr, rightarr[rightindex])
24 lastarr = append(lastarr, leftarr[leftindex])
25 leftindex++
26 rightindex++
27 }
28 }
29 for leftindex < len(leftarr) { //把没有结束的归并过来
30 lastarr = append(lastarr, leftarr[leftindex])
31 leftindex++
32 }
33 for rightindex < len(rightarr) { //把没有结束的归并过来
34 lastarr = append(lastarr, rightarr[rightindex])
35 rightindex++
36 }
37 return lastarr
38}
39
40func MergeSort(arr []int) []int {
41 length := len(arr)
42 if length <= 1 {
43 return arr
44 } else if length > 1 && length < 5 { //小于5个元素改用插入排序
45 return InsertSortX(arr)
46 } else {
47 mid := length / 2
48 leftarr := MergeSort(arr[:mid])
49 rightarr := MergeSort(arr[mid:])
50
51 return merge(leftarr, rightarr)
52 }
53}
54
55func InsertSortX(arr []int) []int {
56 length := len(arr) //数组长度
57 if length <= 1 {
58 return arr //一个元素的数组，直接返回
59 } else {
60 for i := 1; i < length; i++ { //跳过第一个
61 backup := arr[i] //备份插入的数据
62 j := i - 1 //上一个位置循环找到位置插入
63 for j >= 0 && backup < arr[j] {
64 arr[j+1] = arr[j] //从前往后移动
65 j--
66 }
67 arr[j+1] = backup //插入
68 //fmt.Println(arr)
69 }
70 return arr
71 }
72}
73
74func main() {
75 arr := []int{1, 9, 2, 8, 3, 7, 4, 6, 5, 10}
76 fmt.Println(MergeSort(arr))
77}
希尔排序
根据步长 一一交换数据，减少步长，直到步长为1。交换后 就是排序好后的数组
下面 先步长5 ， 然后步长
1package main
2
3import "fmt"
4
5//1 9 2 8 3 7 4 6 5 10
6//1 7
7// 9 4
8// 2 6
9// 8 5
10// 3 10
11//1 4 2 5 3 7 9 6 8 10
12//1 3 8
13// 4 7 10
14// 2 9
15// 5 6
16//1 4 2 5 3 7 9 6 8 10
17//1 5 9 10
18// 3 4 6
19// 2 7 8
20//1 3 2 5 4 7 9 6 8 10
21//1 2 4 8 9
22// 3 5 6 7 10
23//1 3 2 5 4 6 8 7 9 10
24
25func ShellSortStep(arr []int, start int, gap int) {
26 length := len(arr) //数组长度
27 for i := start + gap; i < length; i += gap { //插入排序的变种
28 backup := arr[i] //备份插入的数据
29 j := i - gap //上一个位置循环找到位置插入
30 for j >= 0 && backup < arr[j] {
31 arr[j+gap] = arr[j] //从前往后移动
32 j -= gap
33 }
34 arr[j+gap] = backup //插入
35 fmt.Println(arr)
36
37 }
38
39}
40
41func ShellSort(arr []int) []int {
42 length := len(arr) //数组长度
43 if length <= 1 {
44 return arr //一个元素的数组，直接返回
45 } else {
46 gap := length / 2
47 for gap > 0 {
48 for i := 0; i < gap; i++ { //处理每个元素的步长
49 ShellSortStep(arr, i, gap)
50 }
51 //gap--
52 gap /= 2
53 }
54
55 }
56
57 return arr
58}
59
60func main() {
61 arr := []int{1, 9, 2, 8, 3, 7, 4, 6, 5, 10}
62 fmt.Println(ShellSort(arr))
63
64}
基数排序
1package main
2
3import "fmt"
4
5
6func SelectSortMaxx(arr []int) int {
7 length := len(arr) //数组长度
8 if length <= 1 {
9 return arr[0] //一个元素的数组，直接返回
10 } else {
11 max := arr[0] //假定第一个最大
12 for i := 1; i < length; i++ {
13 if arr[i] > max { //任何一个比我的大的数，最大的
14 max = arr[i]
15 }
16 }
17 return max
18 }
19}
20
21func RadixSort(arr []int) []int {
22 max := SelectSortMaxx(arr) //寻找数组极大值 99991
23 for bit := 1; max/bit > 0; bit *= 10 {
24 //按照数量级分段
25 arr = BitSort(arr, bit) //每次处理一个级别的排序
26 }
27 return arr
28}
29func BitSort(arr []int, bit int) []int {
30 length := len(arr) //数组长度
31 bitcounts := make([]int, 10) //统计长度0,1,2,3,4,5,6,7,8,9
32 for i := 0; i < length; i++ {
33 num := (arr[i] / bit) % 10 //分层处理，bit=1000的，三位数不参与排序了，bit=10000的四位数不参与排序
34 bitcounts[num]++ //统计余数相等个数
35 }
36
37 // 11, 91, 222, 878, 348, 7123, 4213, 6232, 5123, 111011
38 //fmt.Println(bitcounts)
39
40 // 0 1 2 3 4 5
41 // 1 0 3 0 0 1
42 // 1 1 4 4 4 5
43 for i := 1; i < 10; i++ {
44 bitcounts[i] += bitcounts[i-1] //叠加，计算位置
45 }
46 //fmt.Println(bitcounts)
47
48 tmp := make([]int, 10) //开辟临时数组
49 for i := length - 1; i >= 0; i-- {
50 num := (arr[i] / bit) % 10
51 tmp[bitcounts[num]-1] = arr[i] //计算排序的位置
52 bitcounts[num]--
53 }
54 //fmt.Println("---", tmp)
55 //91, 222, 878, 348, 7123, 4213, 6232, 5123, 111011,10
56
57 for i := 0; i < length; i++ {
58 arr[i] = tmp[i] //保存数组
59 }
60 fmt.Println(arr)
61 return arr
62
63}
64
65func main() {
66 arr := []int{91, 222, 878, 348, 9, 7123, 4213, 6232, 5123, 11}
67 fmt.Println(RadixSort(arr))
68
69}
统计排序
1package main
2
3import "fmt"
4
5func SelectSortMaxy(arr []int) int {
6 length := len(arr) //数组长度
7 if length <= 1 {
8 return arr[0] //一个元素的数组，直接返回
9 } else {
10 max := arr[0] //假定第一个最大
11 for i := 1; i < length; i++ {
12 if arr[i] > max { //任何一个比我的大的数，最大的
13 max = arr[i]
14 }
15 }
16 return max
17 }
18
19}
20func Countsort(arr []int) []int {
21 max := SelectSortMaxy(arr) //寻找最大值
22
23 sortedarr := make([]int, len(arr)) //排序之后存储
24
25 countsarr := make([]int, len(arr)) //统计次数
26
27 for _, v := range arr {
28 countsarr[v]++
29 }
30 fmt.Println("第一次统计次数", countsarr) //统计次数
31
32 for i := 1; i <= max; i++ {
33 countsarr[i] += countsarr[i-1] //叠加
34 }
35 fmt.Println("次数叠加", countsarr) //统计次数
36
37 for _, v := range arr {
38 // 值就越大 下标越大
39 sortedarr[countsarr[v]-1] = v //展开数据
40 countsarr[v]-- //递减
41
42 fmt.Println("zkcount", countsarr)
43 fmt.Println("zk", sortedarr)
44 }
45 return sortedarr
46
47}
48
49//1 2 3 4 5
50//2 3 2 2 1
51
52//2 5 7 9 10
53
54// 1 2 3 4 5
55// 11 222 33 44 15
56//11 222 33 44 5
57
58func main() {
59 arr := []int{0, 2, 3, 4, 4, 3, 2, 1, 2, 5, 5, 3, 4, 3, 2, 1}
60 fmt.Println(Countsort(arr))
61
62}