基数排序简析

原创
2015/03/15 15:54
阅读数 279

基数排序是一种适用于特定数据类型的内部排序算法。这种排序算法要求数据必须能够划分为多个排序关键字,且这些排序关键字应该有优先级的区别。比如某个序列的数据都是整数,且取值范围在[0,99],则我们可以划分出两个关键字:十位数和个位数。其中十位数比个位数的优先级要高。

一种基数排序的方法,是从优先级最高的关键字开始,将序列中各值分配为多个子序列,然后对每个子序列进行排序(这一次排序可以采用次高优先级关键字继续基数排序,也可以采用其他排序方法),然后将各个子序列顺序连接——因为最高优先级关键字是排好序的,各子序列必然也是有序连接的。这种又称为MSD法。

这种方法很明显和快速排序一样,都是分治策略。

另一种基数排序的方法,是从优先级最低的关键字开始,将序列中各值分配为多个子序列,按关键字顺序连接各子序列之后,再以优先级第二低的关键字进行第二次分配-连接......如此往复直到最高优先级的关键字也进行了分配连接过程,排序完毕。这种又称为LSD法。这种排序的要求是,每一次分配的时候,应保存序列的稳定性——也就是说,如果两个数据被分配到同一个子序列,则其先后顺序应保持稳定——这就代表着,我们对更高一级关键字进行分配的时候,同一子序列中的低级关键字产生的顺序不会被破坏。

可见,采用LSD法时,时间复杂度为O(d * n),其中d为关键字数目,一般稳定,所以时间复杂度为O(n)。MSD法,如果各层都采用基数排序,同样是O(d * n),但是会有额外的内存花费;如果下面几层采用别的算法,就比较复杂了,且不提。

通常我们说基数排序,默认指的就是LSD法。MSD法往往用于类似先区分男女再按身高排序之类的情况。

LSD法速度快,缺点一是对数据有类型要求,二是在顺序存储结构(如数组)时很难进行分配。典型用法是对线性链表进行排序。

仍然以[0,99]范围内的数组进行排序为例:

1)将数组转化为单链表A。

2)我们另外制作出一个链表B,该链表有10个节点依次表示0-9。

3)另设10个指针分别指向这10个节点,节点和指针之间的链表就是根据关键字分配来的序列。

4)将单链表A的元素依次取出插入链表B:提取关键字,然后分配到对应的指针那里,插入指针后面然后将指针后移。

(可见节点始终指向各分配序列的尾部,而指针始终指向各分配序列的头部)

5)将节点取出来,连接空隙,就可以得到经过一次排序的链表了。

6)对更高一级优先级的关键字进行同样的操作,直到最高优先级关键字。

7)将链表的值转交到数组,销毁申请的内存,完毕。

以下是golang编写的算法代码:

<!-- lang: go -->
package main

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

// 基数排序
func RadixSort(sz []int) {
	// 链表的数据类型
	type ele struct {
		data int
		next *ele
	}

	// 将切片转化为链表
	n := len(sz)
	r := make([]ele, n+10) // 保管要排序的数据
	t := make([]*ele, 10)  // 记录各分段的段尾
	s := r[n:]             // 作为各分段的段头
	p := &r[0]             // 记录链表的头部
	for i := 0; i < n; i++ {
		r[i].data = sz[i]
		r[i].next = &r[i+1]
	}
	r[n-1].next = nil

	// 预制分成十段的链表,每段都有头尾(目前二者相同)
	initialize := func() {
		for i := 0; i < 9; i++ {
			t[i] = &s[i]
			s[i].next = &s[i+1]
		}
		t[9], s[9].next = &s[9], nil
	}

	// 将段中的预置的段头剔除出来,必须从后向前(请思考)
	separate := func() *ele {
		for i := 9; i > 0; i-- {
			t[i-1].next = s[i].next
		}
		return s[0].next
	}

	// 依次取出链表中元素顺序插入各段中
	insert := func(fac func(int) int) {
		for p != nil {
			q := p.next
			j := fac(p.data)
			p.next = t[j].next
			t[j].next = p
			t[j], p = p, q
		}
	}

	// 按照个位排序第一次
	initialize()
	insert(func(k int) int { return k % 10 })
	p = separate()

	// 按照十位排序第二次
	initialize()
	insert(func(k int) int { return k / 10 % 10 })
	p = separate()

	// 按照百位排序第三次
	initialize()
	insert(func(k int) int { return k / 100 % 10 })
	p = separate()

	// 从链表返回给数组
	for i := 0; p != nil; i, p = i+1, p.next {
		sz[i] = p.data
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	sz := make([]int, 30)
	for i := 0; i < 30; i++ {
		sz[i] = rand.Intn(90) + 10
	}
	fmt.Println(sz)
	RadixSort(sz)
	fmt.Println(sz)
}
展开阅读全文
加载中

作者的其它热门文章

打赏
0
1 收藏
分享
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部