image frame

XiShng Blog

既往拼搏，守护一生所爱

基数排序

算法 / 排序算法

基数排序

基数排序是一种对整数进行排序的排序算法，它的做法是首先对待排序列的个位进行按位插入，即是：如果一个数字的个位为1则插入1所对应的位置，其他的同理。然后对十位，一直到所有数字里面的最高位为止，这个排序才算完成。

具体的操作我用下面的示意图进行说明：

基数排序示意图

基数排序示意图

上图中我们设置了一个待排序的整数数列为 10， 1， 18， 7， 17， 23， 9， 26， 16， 8.

第一个需要设置循环次数，也就是我们上面所说的待排序列的最大数的位数。在这个例子里面是2.

然后进行按位插入，譬如10的个位为0，则插入到index=0 的那一行；1的个位为1，插入到index=1的那一行；18的个位为8，插入到index=8的那一行； …… 以此类推，得到一个中间数组如上图中 中间的那个绿色的数组。然后进行第二次按位插入，譬如10的十位为1，则插入到index=1的位置；1的十位为0，插入到index=0的为止，以此类推，循环终止，得到最终的排序完毕的结果。

下面是golang的代码实现：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
func RadixSort(nums []int) []int  {
	numberBit := howManyBit(maximum(nums))
	// 循环的次数
	// 定义一个rec 二维切片 rec[i][x] 用来接受尾数是 i的数字

	for i := 0; i < numberBit; i++ {
		rec := make([][]int, 10)

		for _, num := range nums {
			rec[(num/pow10(i))%10] = append(rec[(num/pow10(i))%10], num)
		}
		// flatten the rec slice to the one dimension slice
		numsCopy := make([]int, 0)
		for j := 0; j < 10; j++ {
			numsCopy = append(numsCopy, rec[j]...)
		}
		// refresh nums，使得他变为 经过一次基数排序之后的数组
		nums = numsCopy
	}
	return nums
}

func pow10(num int) int {
	res := 1
	base := 10
	for num != 0 {
		if num&1 ==1 {
			num -= 1
			res *= base
		}
		num >>= 1
		base *= base
	}
	return res
}

func maximum(list []int) int {
	max := 0
	for _, i2 := range list {
		if i2 > max {
			max = i2
		}
	}
	return max
}

func howManyBit(number int) int  {
	count := 0
	for number != 0 {
		number = number/10
		count += 1
	}
	return count
}

func main() {
	var theArray = []int{10, 1, 18, 30, 23, 12, 7, 5, 18, 233, 144}
	fmt.Print("排序前")
	fmt.Println(theArray)
	fmt.Print("排序后")
	fmt.Println(RadixSort(theArray))
}

冒泡排序算法

算法 / 排序算法

冒泡排序

方法的原理：冒泡排序算法清楚地演示了排序是如何工作的，同时又简单易懂。冒泡排序步骤遍历列表并比较相邻的元素对。如果元素顺序错误，则交换它们。重复遍历列表未排序部分的元素，直到完成列表排序。
简单点来讲冒泡排序算法主要思想就是每一次确定一个值。如果是从左开始比较就是通过两两比较找到最大值。如果是从右开始比较就是两两比较找到最小值。 如下图所示

时间复杂度：因为冒泡排序重复地通过列表的未排序部分，所以它具有最坏的情况复杂度O(n^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
33
package main

import "fmt"

func main() {
    values := []int{5,6,3,1,8,7,2,4}
    fmt.Println(values)
    BubbleAsort(values)
    BubbleZsort(values)
}

func BubbleAsort(values []int) {
    for i := 0; i < len(values)-1; i++ {
        for j := i+1; j < len(values); j++ {
            if  values[i]>values[j]{
                values[i],values[j] = values[j],values[i]
            }
        }
    }
    fmt.Println(values)
}

func BubbleZsort(values []int) {
    for i := 0; i < len(values)-1; i++ {
        for j := i+1; j < len(values); j++ {
            if  values[i]<values[j]{
                values[i],values[j] = values[j],values[i]
            }
        }
    }
    fmt.Println(values)
}

计数排序

算法 / 排序算法

计数排序

介绍

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

基本思想

计数排序和基数排序都是非比较类排序，过程比较简单，但是计数是比较巧妙的，借助第三个数组 countsArr 存元素出现的频率往后累加，对应减一即可得出该元素在排序数组中的位置。

算法复杂度

时间复杂度为 ：O(N + max + 1)

排序过程

计数排序示意图

1
2
3
4
[UNSORTED]:      [1 4 2 4 6 9 8 2]
[DEBUG countsArr]:  [0 1 3 3 5 5 6 6 7 8]
[SORTED]:        [1 2 2 4 4 6 8 9]

实用场景

计数排序的复杂度比任何基于比较的排序都要低，不过空间开销不容忽视。

演示

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
45
46
47
48
49
package main

import (
	"algorithms"
	"fmt"
)

func main() {
	arr := algorithms.GetArr(5, 20)
	//arr = []int{1, 4, 2, 4, 6, 9, 8, 2}
	fmt.Println("[UNSORTED]:\\t", arr)

	max := getMax(arr)
	sortedArr := make([]int, len(arr))
	countsArr := make([]int, max+1) // max+1 是为了防止 countsArr[] 计数时溢出

	// 元素计数
	for _, v := range arr {
		countsArr[v]++
	}

	// 统计独特数字个数并累加
	for i := 1; i <= max; i++ {
		countsArr[i] += countsArr[i-1]
	}

	fmt.Println("[DEBUG countsArr]:\\t", countsArr)

	// 让 arr 中每个元素找到其位置
	for _, v := range arr {
		sortedArr[countsArr[v]-1] = v
		//fmt.Print(countsArr[v]-1, " ")
		// 保证稳定性
		countsArr[v]--
	}
	//fmt.Println()
	fmt.Println("[SORTED]:\\t", sortedArr)
}

func getMax(arr []int) (max int) {
	max = arr[0]
	for _, v := range arr {
		if max < v {
			max = v
		}
	}
	return
}

请我喝杯咖啡吧~

支付宝
微信