低位优先法(LSD, Least 9753885926458312 Significant digit first) 56789 ■从最低位k开始排序 2622314153598 对于排好的序列再用次低位k排 012356789 依次重复,直至对最高位k1排好序 后,整个序列成为有序 1x22 ■这是一个分、收;分、收;…; 分、收的过程 22263141535859889 比较简单,计算机常用 (a高位优先 北大脑张铭输写 23456 基数排序的实现 41312253 2697885859 ■基于顺序存储 6789 基于链式存储 22a4∞| b)低位优先 北真大张写 初始数组内容。97638889264B3122 基于顺序存储的基数排序 0123456789 只讨论LSD 第趣an21lll2 ■原始输入数组R的长度为n 23456789 基数为r cunt分配桶02344 排序码个数为d 真大带息学张铭端写22 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 127 低位优先法（LSD，Least Significant Digit first） „ 从最低位k0开始排序 „ 对于排好的序列再用次低位k1排 序； „ 依次重复，直至对最高位kd-1排好序 后，整个序列成为有序的 „ 这是一个分、收；分、收；…； 分、收的过程 „ 比较简单，计算机常用 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 128 97 53 88 59 26 41 58 31 22 0 1 2 3 4 5 6 7 8 9 0 1 2 3 45 6 7 8 9 22 26 31 41 53 58 59 88 97 (a)高位优先 26 22 31 41 53 59 58 88 22 26 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 129 97 53 88 59 26 41 58 31 22 0 1 2 3 4 5 6 7 8 9 41 31 22 53 26 97 88 58 59 0 1 2 3 4 5 6 7 8 9 22 26 31 41 53 58 59 88 97 (b)低位优先 41 31 22 53 26 97 88 58 59 22 26 31 41 53,58,59 88 97 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 130 基数排序的实现 „ 基于顺序存储 „ 基于链式存储 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 131 基于顺序存储的基数排序 只讨论LSD „ 原始输入数组R的长度为n „ 基数为r „ 排序码个数为d 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 132 初始数组内容： 97 53 88 59 26 41 58 31 22 0 1 2 3 4 5 6 7 8 9 第一趟：count 0 1 2 3 4 5 6 7 8 9 按count分配桶： 收集： 41 31 22 53 26 97 88 58 59 0 2 1 1 0 0 1 1 2 1 0 2 3 4 4 4 5 6 8 9