排序算法（下）

发表于 更新于

本文讨论关于数组排序算法的实现， 给定一个整形数组，按从小到大排列

本节主要实现的排序算法有：希尔排序，计数排序，基数排序，桶排序，堆排序

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package sort

func ShellSort(arr []int, len int) {
	if len <=1 {
		return
	}

	times := 0

	gap := len / 2

	for gap >=1 {
		j := 0

		for i:=gap; i<len; i++ {
			curr := arr[i]

		//	对第i个元素以及之前相同的gap间距元素进行对比排序
		   for j = i - gap; j>=0 && curr < arr[j]; j -= gap {

			   times++
			   arr[j+gap] = arr[j]
		   }

		   arr[j + gap] = curr
		}

		gap /= 2
	}

	println("time O(", times, ")")
}

计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，
它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。  当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过
对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列
中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些
元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package sort

import "math"

func CountingSort(a []int, n int) {
	if n <= 1 {
		return
	}

	var times = 0

	var max int = math.MinInt32
	for i := range a {
		if a[i] > max {
			max = a[i]
		}
		times++
	}

	c := make([]int, max+1)
	for i := range a {
		c[a[i]]++
		times++
	}
	for i := 1; i <= max; i++ {
		c[i] += c[i-1]
		times++
	}

	r := make([]int, n)
	for i := range a {
		index := c[a[i]] - 1
		r[index] = a[i]
		c[a[i]]--
		times++
	}

	copy(a, r)

	println("Time O(", times, ")")
}

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

基数排序要求基数的量不能太大， 否则做不到O(n)的时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package sort

// 基数排序
func RadixSort(arr []int, len int) {
	if len<=1 {
		return
	}

	max := arr[0]

	for i:=0; i< len; i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}

	for exp:=1; max/exp > 0; exp *= 10 {
		countSort(arr, exp, len)
	}
}


func countSort(arr []int, exp int, len int) {

	c := make([]int, 10, 10)

	for i := range arr {
		c[arr[i]/exp % 10]++
	}

	for i := 1; i < cap(c); i++ {
		c[i] += c[i-1]
	}

	r := make([]int, len, len)

	for i := 0; i<len; i++ {
		r[c[arr[i]/exp %10] -1] = arr[i]
		c[arr[i]/exp %10]--
	}

	copy(arr, r)
}

桶排序

桶排序(Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。 每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。 桶排序是鸽巢排序的一种归纳结果。 当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package sort

func getMax(arr []int) int {
	max := 0

	for i := range arr {
		if i > max {
			max = i
		}
	}

	return max
}

func BucketSort(arr []int, arrLen int) {
	if arrLen <= 1 {
		return
	}

	max := getMax(arr)
	buckets := make([][]int, arrLen / 10) // seperate to length/10 buckets

	for i := 0; i < arrLen; i++ {
		index := arr[i] * ( arrLen - 1 ) / (10 * max) // sperate data to different bucket

		buckets[index] = append(buckets[index], arr[i])
	}

	datalen := 0 // mark current data processed

	for j := 0; j < len(buckets); j++ {
		bucLen := len(buckets[j])

		if bucLen > 0 {
			// use quicksort to sort every bucket
			QuickSort(buckets[j], bucLen)

			copy(arr[datalen:], buckets[j])

			datalen += bucLen
		}
	}
}

堆排序

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

1
// TBD