基数排序算法

winzhi

// Radix Sort
(*
先找出数组中最大元素，确定基数(几位数)；
然后对元素从最低位(个位)开始分类，依次放入 0~9 容器中，再按顺序取出；
后按高一位(十位)分类，取出；直至最高位；最后按顺序取出，排序结束。
*)
// 适用范围：正整数
//

#sort_temp := #Sort_IN;

#max := #sort_temp[0];
FOR #i := 0 TO #Length - 1 DO
    IF #sort_temp[#i] > #max THEN
        #max := #sort_temp[#i];     // 找出数组中的最大值
    END_IF;
END_FOR;

#exp := 1;
WHILE #max / #exp > 0 DO   // 最大数位数决定操作次数

    FOR #i := 0 TO 9 DO        // 清空容器
        FOR #j := 1 TO 10 DO
            #bucket[#i, #j] := 0;
        END_FOR;
    END_FOR;
    FOR #i := 0 TO 9 DO        // 清空计数器
        #num[#i] := 1;
    END_FOR;

    FOR #i := 0 TO #Length - 1 DO
        #no := (#sort_temp[#i] / #exp) MOD 10;       // 基数
        #bucket[#no, #num[#no]] := #sort_temp[#i];
        #num[#no] := #num[#no] + 1;                  // 相同基数的元素个数
    END_FOR;
    #k := 0;
    FOR #i := 0 TO 9 DO
        FOR #j := 1 TO 10 DO
            IF #bucket[#i, #j] > 0 THEN
                #sort_temp[#k] := #bucket[#i, #j];   // 按顺序取出
                #k := #k + 1;
            END_IF;
        END_FOR;
    END_FOR;
    #exp := #exp * 10;    // 更高位基数
END_WHILE;

#Sort_OUT := #sort_temp;