给出关键字序列{ 321,156,57,46,28,7,331,33,34,63 },按次位优先(LSD)链式基数排序进行两趟分配和收集的结果为:
时间: 2024-05-17 16:11:30 浏览: 150
关键字排序
首先,我们需要确定这些关键字中最大的数有几位。最大的数是 321,有三位,因此需要进行三次分配和收集。
第一次分配和收集:
根据个位数的大小分配到0-9的桶中:
Bucket 0:
Bucket 1: 331, 31, 61, 21
Bucket 2: 32
Bucket 3: 33
Bucket 4: 34, 4
Bucket 5: 156, 46
Bucket 6: 57
Bucket 7: 7
Bucket 8: 28
Bucket 9:
收集后得到关键字序列:
{ 331,31,61,21,32,33,34,4,156,46,57,7,28 }
第二次分配和收集:
根据十位数的大小分配到0-9的桶中:
Bucket 0:
Bucket 1: 21, 31, 32, 33, 34
Bucket 2: 46, 7, 57, 28
Bucket 3:
Bucket 4: 156
Bucket 5:
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9: 331, 61, 4
收集后得到关键字序列:
{ 21,31,32,33,34,46,7,57,28,156,331,61,4 }
第三次分配和收集:
根据百位数的大小分配到0-9的桶中:
Bucket 0: 4, 7, 21, 28, 31, 32, 33, 34, 46, 57, 61
Bucket 1:
Bucket 2:
Bucket 3:
Bucket 4:
Bucket 5:
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9: 156, 331
收集后得到关键字序列:
{ 4,7,21,28,31,32,33,34,46,57,61,156,331 }
阅读全文