2001 -- 12 --31
华中科技大学计算机学院 (12)数据结构
10.4 归并排序基本思想把 k(k≥2) 个有序子文件合并在一起，形成一个新的有序文件。
同时归并 k个有序子文件的排序过程称为 k-路归并排序。
2-路归并排序 ---归并 2个有序子文件的排序。
例,将有序文件 A和 B归并为有序文件 C。
A＝ (2,10,15,18,21,30)
B＝ (5,20,35,40)
按从小至大的次序从 A或 B中依次取出 2,5,10,15,...,40,
顺序归并到 C中,得,
C＝ (2,5,10,15,18,20,21,30,35,40)
一般地,2-路归并 过程为：
假定文件 r[low..high]中的相邻子文件 (子表 )
(r[low],r[low+1],...,r[mid])和 (r[mid+1],...,r[high])
为有序子文件,其中,low≤mid<high 。
将这两个相邻有序子文件归并为有序文件 y[low..high],即：
(y[low],y[low+1],...,y[high])
06
08
15
40
07
09
20
22
r[9..16]
9
10
11
12
13
14
15
16
06
07
08
09
15
20
22
40
y[9..16]
9
10
11
12
13
14
15
16
2-路归并 有序文件 (表 )
i→
j→
k→
例有序子表有序子表将 两个有序子文件归并为有一个有序文件的算法
void merge(r,y,low,mid,high)
RecType r[],y[]； int low,mid,high；
{ int k=i=low,j=mid+1；
while (i<=mid && j<=high)
{ if (r[i].key<=r[j].key)
{ y[k]=r[i]； //归并前一个子文件的记录
i++； }
else
{ y[k]=r[j]； //归并后一个子文件的记录
j++； }
k++；
}
while (j<=high) //归并后一个子文件余下的记录
{ y[k]=r[j]； j++； k++；
}
while (i<=mid) //归并前一个子文件余下的记录
{ y[k]=r[i]；
i++； k++；
}
} // merge
2-路归并排序假定文件 (r[1],r[2],...,r[n])中记录是随机排列的,进行
2-路归并排序,首先把它划分为长度均为 1的 n个有序子文件,
然后对它们逐步进行 2－路归并排序 。 其步骤如下：
第 1趟,从 r[1..n]中的第 1个和第 2个有序子文件开始,调用算法 merge,每次归并两个相邻子文件,归并结果放到 y[1..n]中 。
在 y中形成?n/2? 个长度为 2的有序子文件 。 若 n为奇数,则 y中最后一个子文件的长度为 1。
第 2趟,把 y[1..n]看作输入文件,将?n/2? 个有序子文件两两归并,归并结果回送到 r[1..n]中,在 r中形成n/2?/2?个长度为 4的有序子文件 。 若 y中有奇数个子文件,则 r中最后一个子文件的长度为 2。
......
共计经过?log2n? 趟 归并,最后得到 n个记录的有序文件 。
例 1,对 8个记录作 2路归并排序,共进行?log28?＝ 3 趟归并 。
06
44
20
10
02
20
08
07
１
２
３
４
５
６
７
８
r[1..８ ]
06
44
10
20
02
20
07
08
１
２
３
４
５
６
７
８
y[1..８ ]
06
10
20
44
02
07
08
20
１
２
３
４
５
６
７
８
r[1..８ ]
02
06
07
08
10
20
20
44
１
２
３
４
５
６
７
８
y[1..８ ]
第 1趟 第 3趟第 2趟例 2,对 11个记录作 2-路归并排序,进行?log211?＝ 4趟归并。
06
44
20
10
02
20
08
07
05
32
14
1
2
3
4
5
6
7
8
9
10
11
r[1..11]
06
44
10
20
02
20
07
08
05
32
14
y[1..11]
06
10
20
44
02
07
08
20
05
14
32
r[1..11]
02
06
07
08
10
20
20
44
05
14
32
y[1..11]
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11
02
05
06
07
08
10
14
20
20
32
44
r[1..11]
1
2
3
4
5
6
7
8
9
10
11
第 1趟 第 3趟第 2趟 第 4趟一趟归并排序算法,
// s为子文件的长度,将 r中的子文件归并到 y中
void mergepass(RecType r[],RecType y[],int s)
{ int i=1；
while(i+2*s-1<=ｎ ) //两两归并长度均为 s的子文件
{ merge(r,y,i,i+s-1,i+2*s-1)；
i=i+2*s；
}
if (i+s-1<n) //最后两个子长度为 s和长度不足 s的文件
merge(r,y,i,i+s-1,n)；
else
while(i<=n) //复制最后一个子文件,长度 ≤ s
{ y[i]=r[i]；
i++；
}
}
对 文件 r[1..n]归并排序的算法 (调用算法 mergepass)
void mergesort(RecType r[],int n)
{
RecType y[n+1］ ；
int s=1； //子文件初始长度为 1
while (s<n)
{ mergepass(r,y,s)； //将 r[1..n]归并到 y[1..n]
s=2*s； //修改子文件长度
mergepass(y,r,s)； //将 y[1..n]归并到 r[1..n]
s=2*s； //修改子文件长度
}
}
算法分析
● 对 n个记录的文件进行归并排序,共需?log2n?
趟,每趟 所需比较关键字的次数不超过 n,共比较
O(nlog2n)次 。
● 每趟移动 n个记录,共 移动 O(nlog2n)个记录 。
● 归并排序需要一个大小为 n的辅助空间 y[1..n]。
● 归并排序是 稳定 的 。
10.5 交换排序
10.5.1 冒泡排序基本思想,设待排序的文件为 r[1..n]
第 1趟 (遍 )：从 r[1]开始,依次比较两个相邻记录的关键字
r[i].key和 r[i+1].key,若 r[i].key>r[i+1].key,则交换记录
r[i]和 r[i+1]的位置；否则,不交换。
(i=1,2,...n-1)
第 1趟之后,n个关键字中最大的记录移到了 r[n]的位置上。
第 2趟,从 r[1]开始,依次比较两个相邻记录的关键字
r[i].key和 r[i+1].key,若 r[i].key>r[i+1].key,则交换记录
r[i]和 r[i+1]的位置；否则,不交换。
(i=1,2,...n-2)
第 2趟之后,前 n-1个关键字中最大的记录移到了 r[n-1]的位置上。
......
作完 n-1趟,或者不需再交换记录时为止。
例,第 1趟 第 2趟 第 3趟 第 4趟
┌─────────┐ ┌─┐ ┌─┐ ┌─┐
k1= 43 21 21 21 21 21 21 21 21 15 15 15
k2= 21 43 43 43 43 43 43 15 15 21 21 21
k3= 89 89 89 15 15 15 15 28 28 28 28 28
k4= 15 15 15 89 28 28 28 43 43 43 43 43
k5= 28 28 28 28 89 43 43 43 43 43 43 43
k6= 43 43 43 43 43 89 89 89 89 89 89 89
比较次数 =5＋ 4＋ 3＋ 2＝ 14
交换记录的次数 =3+2+1=6，移动记录次数 =3*6=18
算法分析
● 最好情况,待排序的文件已是有序文件，只需要进行 1趟排序,共计比较关键字的次数为
n－ 1
不交换记录 。
● 最坏情况,要经过 n-1趟排序，所需总的比较关键字的次数为
(n-1)+(n-2)+...+1＝ n(n-1)/2
交换记录的次数最多为
(n-1)+(n-2)+...+1＝ n(n-1)/2
移动记录次数最多为
3n(n-1)/2 。
● 只需要少量中间变量作为辅助空间。
● 算法是 稳定 的。
冒泡排序算法
// 对 n个整数按递增次序作冒泡排序
Void bubble1(int a[],int n)
{ int i,j,temp；
for(i=0； i<n-1； i++) //作 n-1趟 排序
for(j=0； j<n-1-i； j++)
if (a[j]>a[j+1])
{ temp=a[j]； //交换记录
a[j]=a[j+1]；
a[j+1]=temp；
}
for(i=0； i<n； i++)
printf("%d",a[i])； //输出排序后的元素
}
改进的冒泡排序算法
void bubblesort(RecType r[],int n)
{ int i,j,swap； RecType temp；
j=1； //置比较的趟数为 1
do{ swap=0； //置交换标志为 0
for (i=1； i<=n-j； i++)
{ if (r[i].key>r[i+1].key)
{ temp=r[i]； //交换记录 `
r[i]=r[i+1]；
r[i+1]=temp；
swap=1； //置交换标志为 1
}
j++； //作下一趟排序
}
} while (j<n && swap)；
} //未作完 n-1趟,且标志为 1
10.5.2 快速排序基本思想：首先在 r[1..n]中，确定一个 r[i],经过比较和移动,将 r[i]放到 "中间 "某个位置上，使得 r[i]左边所有记录的关键字小于等于 r[i].key,r[i]右边所有记录的关键字大于等于 r[i].key。 以 r[i]为界,将文件划分为左、右两个子文件 。
用同样的方法分别对这两个子文件进行划分,得到 4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,
便得到原文件的有序文件。
例,给定文件 (20,05,37,08,63,12,59,15,44,08)，选用第 1个元素 20进行划分,
20 05 37 08 63 12 59 15 44 08
↑ ↑
20
x
i j
例
08 05 37 08 63 12 59 15 44 08
↑ ↑
20
x
08 05 37 08 63 12 59 15 44 08
↑ ↑ ↑ ↑
20
x
i j
i j
08 05 37 08 63 12 59 15 44 37
↑ ↑ ↑ ↑
20
x
i j
08 05 15 08 63 12 59 15 44 37
↑ ↑
20
x
i j
08 05 15 08 63 12 59 15 44 37
↑ ↑ ↑ ↑
20
x
i j
08 05 15 08 63 12 59 63 44 37
↑ ↑ ↑ ↑
20
x
i j
08 05 15 08 12 12 59 63 44 37
↑
20
x
ij
↑
08 05 15 08 12 20 59 63 44 37
↑
20
x
i j
↑左子文件 右子文件例
void quksort(RecType r[],int low,int high)
{ RecType x； int i,j；
if (low<high) //有两个以上记录
{ i=low； j=high； x=r[i]； //保存记录到变量 x中
do { //此时 i指示位置可用
while (i<j && r[j].key>=x.key)
j--； //j从右向左端扫描通过 key不小于 x.key的元素
if (i<j) //i,j未相遇
{ r[i]=r[j]； i++； //此时 j指示位置可用
while(i<j && r[i].key<=x.key)
i++； //i从左向右端扫描通过 key不大于 x.key的元素
if (i<j)
{ r[j]=r[i]； j--； }
}
} while (i!=j)； //i,j未相遇
}
//划分结束,i经过的是 key不大于 x.key的元素；
j经过的是 key不小于 x.key的元素 。
i,j至少有一个指示的位置可用
r[i]=x；
quksort(r,low,i-1)； //递归处理左子文件
quksort(r,i+1,high)； //递归处理右子文件
}
}
对文件 r[1..n]快速排序：
void quicksort(RecType r[],int n)
{ quksort(r,1,n)；
}
算法分析
● 就平均速度而言，快速排序是已知内部排序方法 中最好的一种排序方法,其时间复杂度为 O(nlog(n))。
● 但是,在最坏情况下 （ 基本有序时 ）,快速排序所需的比较次数 和冒泡排序的比较次数相同,其时间复杂度为 O(n2)。
● 快速排序需要一个栈作辅助空间,用来实现递归 处理左,
右子文件 。 在最坏情况下,递归深度为 n,因此 所需栈的空间大小为 O(n)数量级 。
● 快速排序是不稳定的。
10.6 基数排序前面的各种排序算法中，需要进行关键字间的比较。
基数排序不同于前面的各种算法，仅分析关键字自身每位的值，通过分配、回收进行处理。
本算法假定记录的关键字为整型（实际并不限制）。
基数排序有两种方法：
（ 1）首先根据最高有效位进行排序，然后根据次高有效位进行排序，直到根据最低有效位进行排序，产生一个有序序列。
（ 2）首先根据最低有效位进行排序，然后根据次低有效位进行排序，直到根据最高有效位进行排序，产生一个有序序列。
76
82
16
57
45
46
11
22
q[0]
q[1]
q[2]
q[3]
q[4]
q[5]
q[6]
q[7]
q[8]
q[9]
10个队列
76
82
16
57
45
46
11
22
原始序列第一次分配
11
82
22
45
76
16
46
57
q[0]
q[1]
q[2]
q[3]
q[4]
q[5]
q[6]
q[7]
q[8]
q[9]
10个队列
57
82
16
76
45 46
11
22
第一次收集结果第二次分配
11
16
22
45
46
57
76
82
第二次收集结果算法分析：
（ 1）设数字有效位为 d位，需要 d趟分配、回收。
（ 2）每趟分配运算时间 O(n)
（ 3） 收集：基数为 rd,即 rd个队列。
从 rd个队列中收集，运算时间 O(rd)
（ 4）一趟分配、回收运算时间
O(n+rd),时间复杂度 O(d*(n+rd))
（ 5）基数排序是稳定的。
（ 6）辅助空间：每个队列首尾 2个指针，共 2rd个指针； n个记录需要 n个指针域。
华中科技大学计算机学院 (12)数据结构
10.4 归并排序基本思想把 k(k≥2) 个有序子文件合并在一起，形成一个新的有序文件。
同时归并 k个有序子文件的排序过程称为 k-路归并排序。
2-路归并排序 ---归并 2个有序子文件的排序。
例,将有序文件 A和 B归并为有序文件 C。
A＝ (2,10,15,18,21,30)
B＝ (5,20,35,40)
按从小至大的次序从 A或 B中依次取出 2,5,10,15,...,40,
顺序归并到 C中,得,
C＝ (2,5,10,15,18,20,21,30,35,40)
一般地,2-路归并 过程为：
假定文件 r[low..high]中的相邻子文件 (子表 )
(r[low],r[low+1],...,r[mid])和 (r[mid+1],...,r[high])
为有序子文件,其中,low≤mid<high 。
将这两个相邻有序子文件归并为有序文件 y[low..high],即：
(y[low],y[low+1],...,y[high])
06
08
15
40
07
09
20
22
r[9..16]
9
10
11
12
13
14
15
16
06
07
08
09
15
20
22
40
y[9..16]
9
10
11
12
13
14
15
16
2-路归并 有序文件 (表 )
i→
j→
k→
例有序子表有序子表将 两个有序子文件归并为有一个有序文件的算法
void merge(r,y,low,mid,high)
RecType r[],y[]； int low,mid,high；
{ int k=i=low,j=mid+1；
while (i<=mid && j<=high)
{ if (r[i].key<=r[j].key)
{ y[k]=r[i]； //归并前一个子文件的记录
i++； }
else
{ y[k]=r[j]； //归并后一个子文件的记录
j++； }
k++；
}
while (j<=high) //归并后一个子文件余下的记录
{ y[k]=r[j]； j++； k++；
}
while (i<=mid) //归并前一个子文件余下的记录
{ y[k]=r[i]；
i++； k++；
}
} // merge
2-路归并排序假定文件 (r[1],r[2],...,r[n])中记录是随机排列的,进行
2-路归并排序,首先把它划分为长度均为 1的 n个有序子文件,
然后对它们逐步进行 2－路归并排序 。 其步骤如下：
第 1趟,从 r[1..n]中的第 1个和第 2个有序子文件开始,调用算法 merge,每次归并两个相邻子文件,归并结果放到 y[1..n]中 。
在 y中形成?n/2? 个长度为 2的有序子文件 。 若 n为奇数,则 y中最后一个子文件的长度为 1。
第 2趟,把 y[1..n]看作输入文件,将?n/2? 个有序子文件两两归并,归并结果回送到 r[1..n]中,在 r中形成n/2?/2?个长度为 4的有序子文件 。 若 y中有奇数个子文件,则 r中最后一个子文件的长度为 2。
......
共计经过?log2n? 趟 归并,最后得到 n个记录的有序文件 。
例 1,对 8个记录作 2路归并排序,共进行?log28?＝ 3 趟归并 。
06
44
20
10
02
20
08
07
１
２
３
４
５
６
７
８
r[1..８ ]
06
44
10
20
02
20
07
08
１
２
３
４
５
６
７
８
y[1..８ ]
06
10
20
44
02
07
08
20
１
２
３
４
５
６
７
８
r[1..８ ]
02
06
07
08
10
20
20
44
１
２
３
４
５
６
７
８
y[1..８ ]
第 1趟 第 3趟第 2趟例 2,对 11个记录作 2-路归并排序,进行?log211?＝ 4趟归并。
06
44
20
10
02
20
08
07
05
32
14
1
2
3
4
5
6
7
8
9
10
11
r[1..11]
06
44
10
20
02
20
07
08
05
32
14
y[1..11]
06
10
20
44
02
07
08
20
05
14
32
r[1..11]
02
06
07
08
10
20
20
44
05
14
32
y[1..11]
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11
02
05
06
07
08
10
14
20
20
32
44
r[1..11]
1
2
3
4
5
6
7
8
9
10
11
第 1趟 第 3趟第 2趟 第 4趟一趟归并排序算法,
// s为子文件的长度,将 r中的子文件归并到 y中
void mergepass(RecType r[],RecType y[],int s)
{ int i=1；
while(i+2*s-1<=ｎ ) //两两归并长度均为 s的子文件
{ merge(r,y,i,i+s-1,i+2*s-1)；
i=i+2*s；
}
if (i+s-1<n) //最后两个子长度为 s和长度不足 s的文件
merge(r,y,i,i+s-1,n)；
else
while(i<=n) //复制最后一个子文件,长度 ≤ s
{ y[i]=r[i]；
i++；
}
}
对 文件 r[1..n]归并排序的算法 (调用算法 mergepass)
void mergesort(RecType r[],int n)
{
RecType y[n+1］ ；
int s=1； //子文件初始长度为 1
while (s<n)
{ mergepass(r,y,s)； //将 r[1..n]归并到 y[1..n]
s=2*s； //修改子文件长度
mergepass(y,r,s)； //将 y[1..n]归并到 r[1..n]
s=2*s； //修改子文件长度
}
}
算法分析
● 对 n个记录的文件进行归并排序,共需?log2n?
趟,每趟 所需比较关键字的次数不超过 n,共比较
O(nlog2n)次 。
● 每趟移动 n个记录,共 移动 O(nlog2n)个记录 。
● 归并排序需要一个大小为 n的辅助空间 y[1..n]。
● 归并排序是 稳定 的 。
10.5 交换排序
10.5.1 冒泡排序基本思想,设待排序的文件为 r[1..n]
第 1趟 (遍 )：从 r[1]开始,依次比较两个相邻记录的关键字
r[i].key和 r[i+1].key,若 r[i].key>r[i+1].key,则交换记录
r[i]和 r[i+1]的位置；否则,不交换。
(i=1,2,...n-1)
第 1趟之后,n个关键字中最大的记录移到了 r[n]的位置上。
第 2趟,从 r[1]开始,依次比较两个相邻记录的关键字
r[i].key和 r[i+1].key,若 r[i].key>r[i+1].key,则交换记录
r[i]和 r[i+1]的位置；否则,不交换。
(i=1,2,...n-2)
第 2趟之后,前 n-1个关键字中最大的记录移到了 r[n-1]的位置上。
......
作完 n-1趟,或者不需再交换记录时为止。
例,第 1趟 第 2趟 第 3趟 第 4趟
┌─────────┐ ┌─┐ ┌─┐ ┌─┐
k1= 43 21 21 21 21 21 21 21 21 15 15 15
k2= 21 43 43 43 43 43 43 15 15 21 21 21
k3= 89 89 89 15 15 15 15 28 28 28 28 28
k4= 15 15 15 89 28 28 28 43 43 43 43 43
k5= 28 28 28 28 89 43 43 43 43 43 43 43
k6= 43 43 43 43 43 89 89 89 89 89 89 89
比较次数 =5＋ 4＋ 3＋ 2＝ 14
交换记录的次数 =3+2+1=6，移动记录次数 =3*6=18
算法分析
● 最好情况,待排序的文件已是有序文件，只需要进行 1趟排序,共计比较关键字的次数为
n－ 1
不交换记录 。
● 最坏情况,要经过 n-1趟排序，所需总的比较关键字的次数为
(n-1)+(n-2)+...+1＝ n(n-1)/2
交换记录的次数最多为
(n-1)+(n-2)+...+1＝ n(n-1)/2
移动记录次数最多为
3n(n-1)/2 。
● 只需要少量中间变量作为辅助空间。
● 算法是 稳定 的。
冒泡排序算法
// 对 n个整数按递增次序作冒泡排序
Void bubble1(int a[],int n)
{ int i,j,temp；
for(i=0； i<n-1； i++) //作 n-1趟 排序
for(j=0； j<n-1-i； j++)
if (a[j]>a[j+1])
{ temp=a[j]； //交换记录
a[j]=a[j+1]；
a[j+1]=temp；
}
for(i=0； i<n； i++)
printf("%d",a[i])； //输出排序后的元素
}
改进的冒泡排序算法
void bubblesort(RecType r[],int n)
{ int i,j,swap； RecType temp；
j=1； //置比较的趟数为 1
do{ swap=0； //置交换标志为 0
for (i=1； i<=n-j； i++)
{ if (r[i].key>r[i+1].key)
{ temp=r[i]； //交换记录 `
r[i]=r[i+1]；
r[i+1]=temp；
swap=1； //置交换标志为 1
}
j++； //作下一趟排序
}
} while (j<n && swap)；
} //未作完 n-1趟,且标志为 1
10.5.2 快速排序基本思想：首先在 r[1..n]中，确定一个 r[i],经过比较和移动,将 r[i]放到 "中间 "某个位置上，使得 r[i]左边所有记录的关键字小于等于 r[i].key,r[i]右边所有记录的关键字大于等于 r[i].key。 以 r[i]为界,将文件划分为左、右两个子文件 。
用同样的方法分别对这两个子文件进行划分,得到 4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,
便得到原文件的有序文件。
例,给定文件 (20,05,37,08,63,12,59,15,44,08)，选用第 1个元素 20进行划分,
20 05 37 08 63 12 59 15 44 08
↑ ↑
20
x
i j
例
08 05 37 08 63 12 59 15 44 08
↑ ↑
20
x
08 05 37 08 63 12 59 15 44 08
↑ ↑ ↑ ↑
20
x
i j
i j
08 05 37 08 63 12 59 15 44 37
↑ ↑ ↑ ↑
20
x
i j
08 05 15 08 63 12 59 15 44 37
↑ ↑
20
x
i j
08 05 15 08 63 12 59 15 44 37
↑ ↑ ↑ ↑
20
x
i j
08 05 15 08 63 12 59 63 44 37
↑ ↑ ↑ ↑
20
x
i j
08 05 15 08 12 12 59 63 44 37
↑
20
x
ij
↑
08 05 15 08 12 20 59 63 44 37
↑
20
x
i j
↑左子文件 右子文件例
void quksort(RecType r[],int low,int high)
{ RecType x； int i,j；
if (low<high) //有两个以上记录
{ i=low； j=high； x=r[i]； //保存记录到变量 x中
do { //此时 i指示位置可用
while (i<j && r[j].key>=x.key)
j--； //j从右向左端扫描通过 key不小于 x.key的元素
if (i<j) //i,j未相遇
{ r[i]=r[j]； i++； //此时 j指示位置可用
while(i<j && r[i].key<=x.key)
i++； //i从左向右端扫描通过 key不大于 x.key的元素
if (i<j)
{ r[j]=r[i]； j--； }
}
} while (i!=j)； //i,j未相遇
}
//划分结束,i经过的是 key不大于 x.key的元素；
j经过的是 key不小于 x.key的元素 。
i,j至少有一个指示的位置可用
r[i]=x；
quksort(r,low,i-1)； //递归处理左子文件
quksort(r,i+1,high)； //递归处理右子文件
}
}
对文件 r[1..n]快速排序：
void quicksort(RecType r[],int n)
{ quksort(r,1,n)；
}
算法分析
● 就平均速度而言，快速排序是已知内部排序方法 中最好的一种排序方法,其时间复杂度为 O(nlog(n))。
● 但是,在最坏情况下 （ 基本有序时 ）,快速排序所需的比较次数 和冒泡排序的比较次数相同,其时间复杂度为 O(n2)。
● 快速排序需要一个栈作辅助空间,用来实现递归 处理左,
右子文件 。 在最坏情况下,递归深度为 n,因此 所需栈的空间大小为 O(n)数量级 。
● 快速排序是不稳定的。
10.6 基数排序前面的各种排序算法中，需要进行关键字间的比较。
基数排序不同于前面的各种算法，仅分析关键字自身每位的值，通过分配、回收进行处理。
本算法假定记录的关键字为整型（实际并不限制）。
基数排序有两种方法：
（ 1）首先根据最高有效位进行排序，然后根据次高有效位进行排序，直到根据最低有效位进行排序，产生一个有序序列。
（ 2）首先根据最低有效位进行排序，然后根据次低有效位进行排序，直到根据最高有效位进行排序，产生一个有序序列。
76
82
16
57
45
46
11
22
q[0]
q[1]
q[2]
q[3]
q[4]
q[5]
q[6]
q[7]
q[8]
q[9]
10个队列
76
82
16
57
45
46
11
22
原始序列第一次分配
11
82
22
45
76
16
46
57
q[0]
q[1]
q[2]
q[3]
q[4]
q[5]
q[6]
q[7]
q[8]
q[9]
10个队列
57
82
16
76
45 46
11
22
第一次收集结果第二次分配
11
16
22
45
46
57
76
82
第二次收集结果算法分析：
（ 1）设数字有效位为 d位，需要 d趟分配、回收。
（ 2）每趟分配运算时间 O(n)
（ 3） 收集：基数为 rd,即 rd个队列。
从 rd个队列中收集，运算时间 O(rd)
（ 4）一趟分配、回收运算时间
O(n+rd),时间复杂度 O(d*(n+rd))
（ 5）基数排序是稳定的。
（ 6）辅助空间：每个队列首尾 2个指针，共 2rd个指针； n个记录需要 n个指针域。
