计数排序

计数排序

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