7.8 基数排序

讨论待排序记录有多个关键字的排序问题。把这些关键字记为:K0,K1,Kr1K^0, K^1, K^{r-1},其中 K0K^0 为该记录中最高有效关键字,而 Kr1K^{r-1} 为最低有效关键字。记录 RiR_i 的关键字 KjK^j 记作 KijK^j_i

  • 「MSD (Most Significant Digit) 排序」 创建若干个“箱子”,首先按照最高有效关键字 K0K^0 来排序,得到的记录放入箱子,使得相同关键字的记录在同一个箱子,再在每个箱子里创建若干子箱,然后按照下一级有效关键字在每个箱子里单独排序。
  • 「LSD (Least Significant Digit) 排序」 创建若干个“箱子”,首先按照最低有效关键字 Kr1K^{r-1} 来排序,得到的记录放入箱子,使得相同关键字的记录在同一个箱子,然后把所有箱子的内容按顺序放在一起得到单个堆。再创建若干个箱子,然后按顺序以下一个最低有效关键字进行排序,继续放入箱子。重复这一过程直到把数据按最高有效关键字排序后为止。

通常,LSD 排序的开销要小于 MSD 排序的开销。它们排序的时间复杂度为 O(n)O(n)

例如,一个整数由若干位组成,且各位都是有次序的,从而使其最右边的数字位是最低有效位,而最左边的数字位是最高有效位。如果整数的范围是 0K9990 \leq K \leq 999,那么就可以使用 LSD 或 MSD 方法进行排序,此时有三个关键字 (K0,K1,K2K^0, K^1, K^2),其中 K0K^0 是百位上的数字,K1K^1 是十位上的数字,K2K^2 是个位上的数字。由于所有的关键字都属于 0Ki90 \leq K^i \leq 9 范围,所以对每个关键字的排序都只需 10 个箱子。在「基数排序」中,把排序关键字用基数 rr 分解为多个数位,对每位数字进行排序都需要 rr 个箱子。

现在来研究基数为 rr 的 LSD 排序算法。每个记录中都有一个链域,且输入序列被排序成一个动态链表。用队列来表示箱子,并用 front[i] 指向第 ii 个箱子的第一个记录,而用 rear[i] 指向第 ii 个箱子的最后一个记录。函数 radix_sort 用来实现基数为 rr 的 LSD 排序算法。

#define MAX_DIGIT 3 // 0 - 999
#define RADIX_SIZE 10
typedef struct list_node *list_pointer;
typedef struct list_node {
    int key[MAX_DIGIT];
    list_pointer link;
}

list_pointer radix_sort(list_pointer ptr)
{
    list_pointer front[RADIX_SIZE], rear[RADIX_SIZE];
    int i, j, digit;
    for (i = MAX_DIGIT-1; i >= 0; i--) {
        for (j = 0; j < RADIX_SIZE; j++)
            front[j] = rear[j] = NULL;
        while (ptr) {
            digit = ptr->key[i];
            if (!front[digit])
                front[digit] = ptr;
            else
                rear[digit] = ptr;
            rear[digit] = ptr;
            ptr = ptr->link;
        }
        ptr = NULL;
        for (j = RADIX_SIZE-1; j >= 0; j--)
            if (front[j]) {
                rear[j]->link = ptr;
                ptr = front[j];
            }
    }
    return ptr;
}

假定输入序列为 179, 208, 306, 93, 859, 984, 55, 9, 271, 33,且基数为 10。过程如下:

  1. 初始输入 179 -> 208 -> 306 -> 93 -> 859 -> 984 -> 55 -> 9 -> 271 -> 33
  2. 将个位数放入箱子
    front[0] -> NULL <- rear[0]
    front[1] -> 271 -> NULL <- rear[1]
    front[2] -> NULL <- rear[2]
    front[3] -> 93 -> 33 -> NULL <- rear[3]
    front[4] -> 984 -> NULL <- rear[4]
    front[5] -> 55 -> NULL <- rear[5]
    front[6] -> 306 -> NULL <- rear[6]
    front[7] -> NULL <- rear[7]
    front[8] -> 208 -> NULL <- rear[8]
    front[9] -> 179 -> 859 -> 9 -> NULL <- rear[9]
    
    处理结果: 217 -> 93 -> 33 -> 984 -> 55 -> 306 -> 208 -> 179 -> 859 -> 9
  3. 将十位数放入箱子
    front[0] -> 306 -> 208 -> 9 -> NULL <- rear[0]
    front[1] -> NULL <- rear[1]
    front[2] -> NULL <- rear[2]
    front[3] -> 33 -> NULL <- rear[3]
    front[4] -> NULL <- rear[4]
    front[5] -> 55 -> 859 -> NULL <- rear[5]
    front[6] -> NULL <- rear[6]
    front[7] -> 271 -> 179 -> NULL <- rear[7]
    front[8] -> 984 -> NULL <- rear[8]
    front[9] -> 93 -> NULL <- rear[9]
    
    处理结果: 306 -> 208 -> 9 -> 33 -> 55 -> 859 -> 271 -> 179 -> 984 -> 93
  4. 将百位数放入箱子
    front[0] -> 9 -> 33 -> 55 -> 93 -> NULL <- rear[0]
    front[1] -> 179 -> NULL <- rear[1]
    front[2] -> 208 -> 271 -> NULL <- rear[2]
    front[3] -> 306 -> NULL <- rear[3]
    front[4] -> NULL <- rear[4]
    front[5] -> NULL <- rear[5]
    front[6] -> NULL <- rear[6]
    front[7] -> NULL <- rear[7]
    front[8] -> 859 -> NULL <- rear[8]
    front[9] -> 934 -> NULL <- rear[9]
    
    处理结果: 9 -> 33 -> 55 -> 93 -> 179 -> 208 -> 271 -> 306 -> 859 -> 984

results matching ""

    No results matching ""