Skip to content

Latest commit

 

History

History
808 lines (651 loc) · 25.8 KB

01.0.md

File metadata and controls

808 lines (651 loc) · 25.8 KB
Raw

For-learning-Go-Tutorial

Go语言是谷歌2009发布的第二款开源编程语言。

Go语言专门针对多处理器系统应用程序的编程进行了优化，使用Go编译的程序可以媲美C或C++代码的速度，而且更加安全、支持并行进程。

因而一直想的是自己可以根据自己学习和使用Go语言编程的心得，写一本Go的书可以帮助想要学习Go语言的初学者快速入门开发和使用！

Go排序算法及其性能比较

在我们开发的时候有的时候需要对一个数据集合进行排序，这时候我们就需要用到了排序算法，而Go的标准库提供了排序的包sort，实现了int，float64和string三种基础类型的排序接口。所有排序调用sort.Sort，内部根据排序数据个数自动切换最适合的排序算法(插入排序．快排和堆排序)。

因为Go中排序的包sort,里面是由三种排序算法(插入排序．快排和堆排序)具体实现的，因此真的排序算法又可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

排序算法又分为稳定性算法和不稳定性算法：

  • 稳定的排序算法: 冒泡排序、插入排序、归并排序和基数排序。

  • 不是稳定的排序算法: 选择排序、快速排序、希尔排序、堆排序。

在Go排序算法这一章讲述的目录:

Go的标准包sort排序

因此对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了sort.Interface定义的三个方法：获取数据集合长度的(Len)方法、比较两个元素大小的(Less)方法和交换两个元素位置的(Swap)方法，就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。

标准库提供一个通用接口，只要实现了这个接口，就可以通过调用 sort.Sort 来排序。

type Interface interface {
    // Len is the number of elements in the collection. 获取数据集合元素个数
    Len() int
    // Less returns whether the element with index i should sort 
    // before the element with index j. 如果index为i的元素小于index为j的元素，则返回true，否则返回false
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j. 交换i和j索引的两个元素的位置
    Swap(i, j int)
}

接下来我们看一个测试:

import (
    "fmt"
    "sort"
)

func main() {

    // int 类型的排序
    a := []int{60, 5, 50, 32, 100}
    fmt.Println(a)     // [60 5 50 32 100]
    sort.Ints(a)       // sort.Sort(IntSlice(a)) 的封装
    fmt.Println(a)     // [5 32 50 60 100]，默认的 Less() 实现的是升序
    sort.Sort(sort.Reverse(sort.IntSlice(a)))
    fmt.Println(a)     // [100 60 50 32 5] 实现降序排列
    
    //float类型的排序
    b := []float64{60.23,5.23,50.99,76.32,100.39,20.21}
    fmt.Println(b)    // [60.23 5.23 50.99 76.32 100.39 20.21]
    sort.Float64s(b)  // sort.Float64Slice(b)
    fmt.Println(b)    // [5.23 20.21 50.99 60.23 76.32 100.39]
    sort.Sort(sort.Reverse(sort.Float64Slice(b)))
    fmt.Println(a)    // [100.39 76.32 60.23 50.99 20.21 5.23] 实现降序排列
}

这里需要注意的是，默认的sort.Less实现的是升序排列，如果想要让结果降序，可以先用sort.Reverse包装一次。这个调用会得到一个reverse的类型，包含一个 Interface 的匿名字段，其中Less函数与Interface里的相反，从而实现逆序。

如果我们要对自定义的数据类型进行排序，需要实现 sort.Interface 接口，也就是实现 Len、Less 和 Swap 三个函数。很多场景下 Len 和 Swap 基本上和数据类型无关，所以实际上只有 Less 会有差别。

例如在app市场中app下载排行榜，知道appId和对应的下载量，需要把数据根据下载量进行排序。

import (
	"fmt"
	"math/rand"
	"sort"
)

type DownloadItem struct {
	AppId        	int // appID
	DownloadTimes 	int // 下载次数
}

func (d DownloadItem) String() string{
	return fmt.Sprintf("AppId:%d,DownloadTimes:%d",d.AppId,d.DownloadTimes)
}

type DownloadCollection []*DownloadItem

func (d DownloadCollection)Len() int{
	return len(d)
}

func (d DownloadCollection)Swap(i int,j int){
	d[i],d[j] = d[j],d[i]
}

// 根据app下载量降序排列
func (d DownloadCollection)Less(i int,j int) bool{
	return d[i].DownloadTimes >d[j].DownloadTimes
}

func main() {
	a := make(DownloadCollection,5)
	for i := 0; i < len(a); i++ {
		a[i] = &DownloadItem{i + 1, rand.Intn(1000)}
	}

	fmt.Println(a)
	sort.Sort(a)
	fmt.Println(a)
}

可以看到为排序的数据是:

[AppId:1,DownloadTimes:81 AppId:2,DownloadTimes:887 AppId:3,DownloadTimes:847 AppId:4,DownloadTimes:59 AppId:5,DownloadTimes:81]

排序后的顺序是：

[AppId:2,DownloadTimes:887 AppId:3,DownloadTimes:847 AppId:1,DownloadTimes:81 AppId:5,DownloadTimes:81 AppId:4,DownloadTimes:59]

在了解了Go的sort包排序之后我们继续探索下当今最流行的十大排序算法，然后做个梳理和总结方便我们以后可以学习和回顾．

冒泡排序

冒泡排序(Bubble Sort) 是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，此时该数列就已经排序完成。个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

算法原理

冒泡排序算法的原理如下：

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡算法实现:

func main() {
	var arr = []int{9,10,11,5,3,4,27,2,1,3,20}
	//升序
	bubbleAscendingSort(arr)
	//降序
	bubbleDescendingSort(arr)
}

//升序
func bubbleAscendingSort(arr []int) {
	for i :=0; i < len(arr)-1; i++ {
		for j := i+1; j< len(arr); j++ {
			if (arr[i] > arr[j]) {
				arr[i],arr[j] = arr[j],arr[i]
			}
		}
	}
	
	fmt.Println("bubbleAscendingSort:",arr)
}

//降序
func bubbleDescendingSort(arr []int) {
	for i :=0; i < len(arr)-1; i++ {
		for j := i+1; j< len(arr); j++ {
			if (arr[i] < arr[j]) {
				arr[i],arr[j] = arr[j],arr[i]
			}
		}
	}
	
	fmt.Println("bubbleDescendingSort:",arr)
}

运行结果:

bubbleAscendingSort: [1 2 3 3 4 5 9 10 11 20 27]

bubbleDescendingSort: [27 20 11 10 9 5 4 3 3 2 1]

选择排序

选择排序(Selection sort) 是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法原理

选择排序算法的原理如下：

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  • 重复第二步，直到所有元素均排序完毕。

选择排序算法实现:

func main() {
	var arr = []int{19,28,17,5,13,4,6,7,9,3,10}
	//升序
	selectAscendingSort(arr)
	//降序
	selectDescendingSort(arr)
}

//升序
func selectAscendingSort(arr []int) {
	l := len(arr)
	m := len(arr) - 1
	for i := 0; i < m; i++ {
		k := i
		for j := i+1; j < l; j++ {
			if arr[k] > arr[j] {
				k = j
			}
		}
		if k != i {
			arr[k],arr[i] = arr[i],arr[k]
		}
	}
	
	fmt.Println("selectAscendingSort:",arr)
}

//降序
func selectDescendingSort(arr []int) {
	l := len(arr)
	m := len(arr) - 1
	for i := 0; i < m; i++ {
		k := i
		for j := i+1; j < l; j++ {
			if arr[k] < arr[j] {
				k = j
			}
		}
		if k != i {
			arr[k],arr[i] = arr[i],arr[k]
		}
	}
	
	fmt.Println("selectDescendingSort:",arr)
}

运行结果:

selectDescendingSort: [3 4 5 6 7 9 10 13 17 19 28]

selectAscendingSort: [28 19 17 13 10 9 7 6 5 4 3]

插入排序

插入排序(Insertion Sort) 是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法原理

插入排序算法原理：

  • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

  • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

插入排序算法实现:

func main() {
	var arr = []int{19,13,27,15,3,4,26,12,1,0}
	insertSort(arr)
	fmt.Println("insertSort:",arr)
}

func insertSort(arr []int) {
	n := len(arr)
	if n < 2 {
		return
	}
	for i := 1; i < n; i++ {
		for j := i; j >0 && arr[j] < arr[j-1]; j-- {
			arr[j], arr[j-1] = arr[j-1], arr[j]
		}
	}
}

运行结果:

insertSort: [0 1 3 4 12 13 15 19 26 27]

希尔排序

希尔排序(Shell Sort),又称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法原理

希尔排序算法原理：

  • 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1.
  • 按增量序列个数 k，对序列进行 k 趟排序.
  • 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度.

希尔排序算法实现:

func main() {
	var arr = []int{19,8,27,15,3,17,6,2,1,0}
	shellSort(arr)
	fmt.Println("shellSort:",arr)
}
func shellSort(arr []int) {
	n := len(arr)
	h := 1
	
	//寻找合适的间隔h
	for h < n/3 {
		h = 3*h +1
	}
	
	for h >= 1 {
		for i := h; i < n; i++ {
			for j := i; j >= h && arr[j] < arr[j-1]; j -= h {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			}
		}
		h /= 3
	}
}

运行结果:

shellSort: [0 1 2 3 6 8 15 17 19 27]

归并排序

归并排序(Merge sort) 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归(所有递归的方法都可以用迭代重写，所以就有了第 2 种方法).
  • 自下而上的迭代.
算法原理

归并排序算法原理：

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列.
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置.
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置.
  • 重复上一步直到某一指针达到序列尾；
  • 将另一序列剩下的所有元素直接复制到合并序列尾.

归并排序算法实现：

func main() {
	array := []int{55, 94, 87, 12, 4, 32, 11,8, 39, 42, 64, 53, 70, 12, 9}
	fmt.Println("before MergeSort",array)
	array = MergeSort(array)
	fmt.Println("after MergeSort:",array)
}

func MergeSort(array []int) []int{
	n := len(array)
	if n < 2 {
		return array
	}
	key := n / 2
	left := MergeSort(array[0:key])
	right := MergeSort(array[key:])
	return merge(left, right)
}

func merge(left []int, right []int) []int{
	tmp := make([]int, 0)
	i, j := 0,0
	for  i < len(left) && j < len(right) {
		if left[i] < right[j]{
			tmp = append(tmp, left[i])
			i ++
		}else{
			tmp = append(tmp, right[j])
			j ++
		}
	}
	tmp = append(tmp, left[i:]...)
	tmp = append(tmp, right[j:]...)
	return tmp
}

运行结果:

before MergeSort [55 94 87 12 4 32 11 8 39 42 64 53 70 12 9]
after MergeSort: [4 8 9 11 12 12 32 39 42 53 55 64 70 87 94]

快速排序

快速排序(Quicksort),又称划分交换排序（partition-exchange sort），简称快排，是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单，当听到这个名字的时候其实你就知道它存在的意义，就是快速排序，而且效率高！它是处理大数据最快的排序算法之一了。

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
算法原理

快速排序的算法原理:

  • 从数列中挑出一个元素，称为 “基准”(pivot).
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作.
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

快速排序算法实现：

func main() {
	var arr = []int{19,8,16,15,23,34,6,3,1,0,2,9,7}
	quickAscendingSort(arr, 0, len(arr)-1)
	fmt.Println("quickAscendingSort:",arr)

	quickDescendingSort(arr, 0, len(arr)-1)
	fmt.Println("quickDescendingSort:",arr)
}

//升序
func quickAscendingSort(arr []int, start, end int) {
	if (start < end) {
		i, j := start, end
		key := arr[(start + end)/2]
		for i <= j {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}

		if start < j {
			quickAscendingSort(arr, start, j)
		}
		if end > i {
			quickAscendingSort(arr, i, end)
		}
	}
}

//降序
func quickDescendingSort(arr []int, start, end int) {
	if (start < end) {
		i, j := start, end
		key := arr[(start + end)/2]
		for i <= j {
			for arr[i] > key {
				i++
			}
			for arr[j] < key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}

		if start < j {
			quickDescendingSort(arr, start, j)
		}
		if end > i {
			quickDescendingSort(arr, i, end)
		}
	}
}

运行结果:

quickAscendingSort: [0 1 2 3 6 7 8 9 15 16 19 23 34]
quickDescendingSort: [34 23 19 16 15 9 8 7 6 3 2 1 0]

堆排序

堆排序(Heapsort) 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列.
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列.
算法原理

堆排序的算法原理:

  • 创建一个堆 H[0……n-1].
  • 把堆首（最大值）和堆尾互换.
  • 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置.
  • 重复步骤2，直到堆的尺寸为 1.

堆排序算法实现:

func main()  {
	array := []int{52,16,37,2,3,32,12,27,19,42,29,13,37,12,9}
	HeapSort(array)
	fmt.Println("HeapSort:",array)
}

func HeapSort(array []int) {
	m := len(array)
	s := m/2
	for i := s; i > -1; i-- {
		heap(array, i, m-1)
	}
	for i := m-1; i > 0; i-- {
		array[i], array[0] = array[0], array[i]
		heap(array, 0, i-1)
	}
}

func heap(array []int, i, end int){
	l := 2*i+1
	if l > end {
		return
	}
	n := l
	r := 2*i+2
	if r <= end && array[r]>array[l]{
		n = r
	}
	if array[i] > array[n]{
		return
	}
	array[n], array[i] = array[i], array[n]
	heap(array, n, end)
}

运行结果:

HeapSort: [2 3 9 12 12 13 16 19 27 29 32 37 37 42 52]

桶排序

桶排序(Bucket sort),工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量.

  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中.

算法原理

桶排序的算法原理：

  • 设置一个定量的数组当作空桶子.
  • 寻访序列，并且把项目一个一个放到对应的桶子去.
  • 对每个不是空的桶子进行排序.
  • 从不是空的桶子里把项目再放回原来的序列中.

桶排序算法实现:

func main()  {
	array := []int{31,16,37,2,13,32,10,27,7,42,29,18,28,12,9,}
	BucketSort(array)
	fmt.Println("BucketSort:",array)
}

func sortInBucket(bucket []int) {//此处实现插入排序方式，其实可以用任意其他排序方式
	length := len(bucket)
	if length == 1 {return}

	for i := 1; i < length; i++ {
		backup := bucket[i]
		j := i -1;
		//将选出的被排数比较后插入左边有序区
		for  j >= 0 && backup < bucket[j] {//注意j >= 0必须在前边，否则会数组越界
			bucket[j+1] = bucket[j]//移动有序数组
			j -- //反向移动下标
		}
		bucket[j + 1] = backup //插队插入移动后的空位
	}
}
//获取数组最大值
func getMaxInArr(arr []int) int{
	max := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] > max{ max = arr[i]}
	}
	return max
}

//桶排序
func BucketSort(arr []int) []int {
	//桶数
	num := len(arr)
	//k（数组最大值）
	max := getMaxInArr(arr)
	//二维切片
	buckets := make([][]int, num)

	//分配入桶
	index := 0
	for i := 0; i < num; i++ {
		index = arr[i] * (num-1) /max//分配桶index = value * (n-1) /k

		buckets[index] = append(buckets[index], arr[i])
	}
	//桶内排序
	tmpPos := 0
	for i := 0; i < num; i++ {
		bucketLen := len(buckets[i])
		if bucketLen > 0{
			sortInBucket(buckets[i])

			copy(arr[tmpPos:], buckets[i])

			tmpPos += bucketLen
		}
	}

	return arr

运行结果：

BucketSort: [2 7 9 10 12 13 16 18 27 28 29 31 32 37 42]

计数排序

计数排序(Counting sort) 是一种稳定的线性时间排序算法.计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C 来将A中的元素排到正确的位置。

算法原理

计数排序的算法原理：

  • 找出待排序的数组中最大和最小的元素.
  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项.
  • 对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加).
  • 反向填充目标数组：将每个元素 i放在新数组的第C[i]项，每放一个元素就将C[i]减去1.

计数排序算法实现:

func main()  {
	array := []int{69,16,48,2,3,32,10,27,17,42,29,8,28,12,9,}
	countingSort(array,array[0])
	fmt.Println("BucketSort:",array)
}

func countingSort(arr []int, maxValue int) []int {
	bucketLen := maxValue + 1
	bucket := make([]int, bucketLen) // 初始为0的数组

	sortedIndex := 0
	length := len(arr)

	for i := 0; i < length; i++ {
		bucket[arr[i]] += 1
	}

	for j := 0; j < bucketLen; j++ {
		for bucket[j] > 0 {
			arr[sortedIndex] = j
			sortedIndex += 1
			bucket[j] -= 1
		}
	}

	return arr
}

运行结果:

countingSort: [2 3 8 9 10 12 16 17 27 28 29 32 42 48 69]

基数排序

基数排序(Radix sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法原理

基数排序的算法原理：

  • 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

  • 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

LSD 基数排序动图演示:

基数排序算法实现:

func main() {
	array := []int{12, 3, 8, 5, 9, 11, 23, 36,20,28,21}
	fmt.Println("before radixSort:",array)

	radixSort(array)
	fmt.Println("after radixSort:",array)
}

//获取数组的最大值
func maxValue(arr []int) (ret int) {
	ret = 1 
	var key int = 10
	for i := 0; i < len(arr); i++ {
		for arr[i] >= key {
			key = key * 10
			ret++
		}
	}
	return
}

func radixSort(arr []int) {
	key := maxValue(arr)
	tmp := make([]int, len(arr), len(arr))
	count := new([10]int)
	radix := 1
	var i, j, k int
	for i = 0; i < key; i++ { //进行key次排序
		for j = 0; j < 10; j++ {
			count[j] = 0
		}
		for j = 0; j < len(arr); j++ {
			k = (arr[j] / radix) % 10
			count[k]++
		}

		for j = 1; j < 10; j++ { //将tmp中的为准依次分配给每个桶
			count[j] = count[j-1] + count[j]
		}
		for j = len(arr) - 1; j >= 0; j-- {
			k = (arr[j] / radix) % 10
			tmp[count[k]-1] = arr[j]
			count[k]--
		}
		for j = 0; j <len(arr); j++ {
			arr[j] = tmp[j]
		}
		radix = radix * 10
	}
}

运行结果:

before radixSort: [12 3 8 5 9 11 23 36 20 28 21]

after radixSort: [3 5 8 9 11 12 20 21 23 28 36]