桶排序算法

winzhi

// Bucket Sort
(*
观察分析待排序数列的范围和特点，将数列按大小范围分为若干个桶；
元素依次放入桶中；再对每个桶单独进行排序，可以用之前的排序算法；
最后按顺序输出各个桶中的各个元素，排序完毕。
*)
// 适用范围：较为均匀分布的序列
// 特例：计数排序、基数排序

#sort_temp := #Sort_IN;

#tmin := #sort_temp[1];
#tmax := #sort_temp[1];
FOR #i := 1 TO #SIZE DO                 // 求最大值、最小值  
    IF #sort_temp[#i] > #tmax THEN
        #tmax := #sort_temp[#i];
    END_IF;
    IF #sort_temp[#i] < #tmin THEN
        #tmin := #sort_temp[#i];
    END_IF;
END_FOR;

// 桶的范围
//
#diff := (#tmax - #tmin) / #GROUP;
#sep[1] := #tmin;
#sep[10] := #tmax;
FOR #i := 1 TO 8 DO
    IF #i MOD 2 = 1 THEN
        #sep[#i + 1] := #sep[#i] + #diff;
    ELSE
        #sep[#i + 1] := #sep[#i] + 1;
    END_IF;
END_FOR;

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

// 元素放入桶中
//
FOR #i := 1 TO #SIZE DO
    FOR #j := 1 TO 10 BY 2 DO
        IF #sort_temp[#i] >= #sep[#j] AND #sort_temp[#i] <= #sep[#j + 1] THEN
            #no := (#j + 1) / 2;   // 桶编号：1~5
            #bucket[#no, #num[#no]] := #sort_temp[#i];
            #num[#no] := #num[#no] + 1;
        END_IF;
    END_FOR;
END_FOR;

// 每个桶，采用选择排序法，升序排列
//
FOR #i := 1 TO #GROUP DO
    FOR #j := 1 TO 10 DO
        #sel_sort_i[#j] := #bucket[#i, #j];
    END_FOR;
    "72_选择排序算法"(Asc_Des := TRUE,
                Sort_IN := #sel_sort_i,
                Sort_OUT => #sel_sort_o);
    FOR #j := 1 TO 10 DO
        #bucket[#i, #j] := #sel_sort_o[#j];
    END_FOR;
END_FOR;

// 将桶中元素，依次按顺序取出
#k := 1;
FOR #i := 1 TO #GROUP 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;

#Sort_OUT := #sort_temp;