易语言基数排序

基数排序、计数排序、 桶排序区别

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

基数排序:根据键值的每位数字来分配桶;
计数排序:每个桶只存储单一键值;
桶排序:每个桶存储一定范围的数值;

基数排序图文说明

通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616},它的示意图如下:

511遇见

在上图中,首先将所有待比较树脂统一为统一位数长度,接着从最低位开始,依次进行排序。
1. 按照个位数进行排序。
2. 按照十位数进行排序。
3. 按照百位数进行排序。
排序后,数列就变成了一个有序序列。

511遇见

基数排序

这里我们优化了基数排序,可以根据数列的个数最大值和最小值自动合理分配桶子。
.版本 2

.子程序 radixsort, , , radixsort
.参数 array, 整数型, 数组
.局部变量 dev, 整数型
.局部变量 j, 整数型
.局部变量 k, 整数型
.局部变量 kk, 整数型
.局部变量 m, 整数型
.局部变量 n, 整数型
.局部变量 Bucketarray, 整数型, , "1,1"
.局部变量 maximum
.局部变量 minimum
.局部变量 d
.局部变量 total
.局部变量 i, 整数型, , , Bucketarray

total = 取数组成员数 (array)
maximum = array [1]
.计次循环首 (total, i)
.判断开始 (array [i] > maximum)
maximum = array [i]
.判断 (array [i] < minimum)
minimum = array [i]
.默认
.判断结束
.计次循环尾 ()
d = maximum - minimum + 1
重定义数组 (Bucketarray, 假, d, d)
dev = 10
j = 0
kk = 1
k = 1
.变量循环首 (1, total, 1, n)
.变量循环首 (1, 10, 1, m)
Bucketarray [n] [m] = -1
.变量循环尾 ()
.变量循环尾 ()
.判断循环首 (kk > 0)
kk = maximum ÷ dev
dev = dev × 10
j = j + 1
.判断循环尾 ()
dev = 10
.判断循环首 (j > 0)
.变量循环首 (1, total, 1, kk)
m = array [kk] ÷ k % dev + 1
Bucketarray [kk] [m] = array [kk]
.变量循环尾 ()
n = 1
.变量循环首 (1, 10, 1, kk)
.变量循环首 (1, total, 1, m)
.如果真 (Bucketarray [m] [kk] > 0)
array [n] = Bucketarray [m] [kk]
Bucketarray [m] [kk] = -1
n = n + 1
.如果真结束

.变量循环尾 ()
.变量循环尾 ()
j = j - 1
k = k × 10
.判断循环尾 ()


发布日期:

所属分类: 易语言 标签: