【重温基础算法】内部排序之基数排序法

内部排序之基数排序法

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

一般情况下，假如有 n n n个记录的序列 { R 1 , R 2 , . . . , R n } \{R_1,R_2,...,R_n\} {R1​,R2​,...,Rn​} 且每个记录 R i R_i Ri​中含有 d d d个关键字 ( k i 0 , k i 1 , . . . , k i d − 1 ) (k_i^0,k_i^1,...,k_i^{d-1}) (ki0​,ki1​,...,kid−1​)，则称序列对关键字 K 0 , K 1 , K 2 , . . . , K d − 1 K^0,K^1,K^2,...,K^{d-1} K0,K1,K2,...,Kd−1有序指的是：对于序列中任意两个记录 R i R_i Ri​和 R j ( 1 ≤ i ≤ j ≤ n ) R_j(1\leq i \leq j \leq n) Rj​(1≤i≤j≤n)都满足下列有序关系： ( K i 0 , K i 1 , . . . , K i d − 1 ) < ( K j 0 , K j 0 , . . . , K j d − 1 ) (K_i^0,K_i^1,...,K_i^{d-1}) < (K_j^0,K_j^0,...,K_j^{d-1}) (Ki0​,Ki1​,...,Kid−1​)