例子 R对排序码(ka1,k2,…,k1,k)有 例如:如果我们要对0到9999之间的整数 进行排序 畔王任鑫定录RpR051≤ 将四位数看作是由四个排序码决定,即 k;,ko)≤ 位,其中千位为最高 序码,个位为最低排序码。基数r=10。 (k;d1,k1d2,…,k1t,k1o) 可以按千、百、十、个位数字依次进行4 其中kd1称为最高排序码 次桶式排序 ako称为最低排序码 4趙分配排序后,整个序列就排好序了 北大脑张铭输写 真大物单张写 基数排序分为两类 m高位优先法(MsD,Most 黑桃S)>红心(H)> Significant Digit first) 方片(D)>梅花(C) 低位优先法(LsD, Least S3HJ C8 H9 S9 D3 CID7 Significant Digit first) 京大管息张铭编写 莉命究 北真大张写 高位优先法(MSD,Most S3 HJ C8 H9 S9 D3 CI D7 Significant Digit first) MSD方法(递归分治) 先对高位k4进行桶式排序,将序列分成 先按花色:C8C1D3D7HJH9S3S9 再披面值:CIC8D3D7H9HJS3s9 李后梦企烟藉次高位k进行桶式排 LSD方法 先按面值:C1s3D3p7C8s9H1J 誇褕熏毒个藉沓橥胥孱排蠃歌小 再按花色:ClC8D3D7H9HJS3S9 最斥存 桶依次连接在一起,成为 要求稳定排序! 这是一个分、分、…、分、收的过程 旗大血张写 ,命究 北真大脆张铭编写21 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 121 „ R对排序码(kd-1，kd-2，…，k1，k0 )有 序 „ 对于任意两个记录R i ，R j (0 ≤ i< j ≤ n-1)，都满足 (k i ,d-1，k i ,d-2， …，k i ,1，k i,0 ) ≤ (k j ,d-1，k j, d-2，…，k j,1，k j,0 ) „ 其中k d-1称为最高排序码 „ k 0称为最低排序码 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 122 例子 例如：如果我们要对0到9999之间的整数 进行排序 „ 将四位数看作是由四个排序码决定，即 千、百、十、个位，其中千位为最高排 序码，个位为最低排序码。基数r=10。 „ 可以按千、百、十、个位数字依次进行4 次桶式排序 „ 4趟分配排序后，整个序列就排好序了 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 123 基数排序分为两类 „ 高位优先法（MSD，Most Significant Digit first） „ 低位优先法（LSD，Least Significant Digit first） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 124 „ 黑桃(S) > 红心(H) > 方片(D) > 梅花(C) „ S3 HJ C8 H9 S9 D3 C1 D7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 125 S3 HJ C8 H9 S9 D3 C1 D7 „ MSD方法（递归分治） „ 先按花色：C8 C1 D3 D7 HJ H9 S3 S9 „ 再按面值：C1 C8 D3 D7 H9 HJ S3 S9 „ LSD方法 „ 先按面值：C1 S3 D3 D’7 C’8 H9 S’9 H’J „ 再按花色：C1 C’8 D3 D’7 H9 H’J S3 S’9 „要求稳定排序！ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 126 高位优先法（MSD，Most Significant Digit first） „ 先对高位kd-1进行桶式排序，将序列分成 若干个桶中 „ 然后对每个桶再按次高位kd-2进行桶式排 序，分成更小的桶 „ 依次重复，直到对k0排序后，分成最小 的桶，每个桶内含有相同的排序码(kd- 1，kd-2，…，k1 ，k0) „ 最后将所有的桶依次连接在一起，成为 一个有序序列 „ 这是一个分、分、…、分、收的过程