计数排序
package main
import (
"fmt"
)
/*
计数排序：
示例：1 3 5 2 1
初始化指针指向第一个元素（指针指向元素1）
第一轮循环，没有比1小的数，因此1在最终排序结果中的位置确定，确定了元素1的位置，同时指针向右移动一位（指针指向元素3）
[1 3 5 2 1]
第二轮循环，比3小的数有2个（元素2、1），交换元素2和3，确定了元素3的位置，指针保持不动（指针指向元素2）
[1 2 5 3 1]
第三轮循环，比2小的数有1个（元素1），交换元素2和5，确定了元素2的位置，指针保持不动（指针指向元素5）
[1 5 2 3 1]
第四轮循环，比5小的数有3个（元素2、3、1），交换元素5和1，确定了元素5的位置，指针保持不动（指针指向元素1）
[1 1 2 3 5]
第五轮循环，比1小的数没有，不需要元素不交换，确定了元素1的位置，同时指针向右移动一位（指针指向元素2）
[1 1 2 3 5]
第六轮循环，再次确定了元素2的位置，同时指针向右移动一位（指针指向元素3）
[1 1 2 3 5]
第七轮循环，再次确定了元素3的位置，同时指针向右移动一位（指针指向元素5）
[1 1 2 3 5]
第八轮循环，再次确定了元素5的位置，结束
[1 1 2 3 5]
*/
func count_sort1(a []int) {
count := 0 //计数器
for i := 0; i < len(a); {
for j := i+1; j < len(a); j++ {
if a[j] < a[i] {
count++
}
}
if count == 0 {
i++
}
if count > 0 {
temp := a[i]
a[i] = a[i+count]
a[i+count] = temp
count = 0
}
fmt.Println(a)
}
}
/*
上述过程分析可以看到：
5个元素，进行了8次循环，实际上每次循环都可以确定一个元素的位置，因此5次后，元素金已经是排好序了。
因此可以增加一个变量记录已经确定位置的元素个数，当变量值达到数组元素个数，说明可以结束循环了
示例：1 3 5 2 1
初始化指针指向第一个元素
第一轮循环，没有比1小的数，因此1在最终排序结果中的位置确定，确定了元素1的位置，同时指针向右移动一位
[1 3 5 2 1]
第二轮循环，比3小的数有2个（元素2、1），交换元素2和3，确定了元素3的位置，指针保持不动
[1 2 5 3 1]
第三轮循环，比2小的数有1个（元素1），交换元素2和5，确定了元素2的位置，指针保持不动
[1 5 2 3 1]
第四轮循环，比5小的数有3个（元素2、3、1），交换元素5和1，确定了元素5的位置，指针保持不动
[1 1 2 3 5]
第五轮循环，比1小的数没有，不需要元素不交换，确定了元素1的位置，同时指针向右移动一位，此时5个元素位置都确定了，循环结束
[1 1 2 3 5]
*/
func count_sort2(a []int) {
sorted_count := 0 //已确定好位置的元素的个数
count := 0 //计数器
for i := 0; i < len(a); {
for j := i+1; j < len(a); j++ {
if a[j] < a[i] {
count++
}
}
if count == 0 {
i++
}
if count > 0 {
temp := a[i]
a[i] = a[i+count]
a[i+count] = temp
count = 0
}
fmt.Println(a)
sorted_count++
if sorted_count == len(a) {
break
}
}
}
func main() {
a := []int{1,3,5,2,1}
fmt.Println("排序前：",a)
count_sort1(a)
fmt.Println("排序后：",a)
a = []int{1,3,5,2,1}
fmt.Println("排序前：",a)
count_sort2(a)
fmt.Println("排序后：",a)
}
运行结果：
GOROOT=C:\Go #gosetup
GOPATH=F:\goPath #gosetup
C:\Go\bin\go.exe build -o C:\Users\windows10\AppData\Local\Temp\___2go_build_count_sort_go.exe F:/code/test/count_sort/count_sort.go #gosetup
C:\Users\windows10\AppData\Local\Temp\___2go_build_count_sort_go.exe #gosetup
排序前： [1 3 5 2 1]
[1 3 5 2 1]
[1 2 5 3 1]
[1 5 2 3 1]
[1 1 2 3 5]
[1 1 2 3 5]
[1 1 2 3 5]
[1 1 2 3 5]
[1 1 2 3 5]
排序后： [1 1 2 3 5]
排序前： [1 3 5 2 1]
[1 3 5 2 1]
[1 2 5 3 1]
[1 5 2 3 1]
[1 1 2 3 5]
[1 1 2 3 5]
排序后： [1 1 2 3 5]
Process finished with exit code 0
