考研笔记

板子：计数排序与基数排序

两个都不靠比较元素大小来排序。计数排序先数出每个值出现几次，直接算出每个元素该放在哪里。基数排序从个位开始，每一趟按这一位「分配」到 10 个队列，再按 0～9 的顺序「收集」起来。

计数排序（★★）

void CountSort(int A[], int B[], int n, int k) {   // 元素取值在 [0, k)；结果放进 B
    int *C = (int *)calloc(k, sizeof(int));  // C[x]：先统计 x 出现了几次
    for (int i = 0; i < n; i++) C[A[i]]++;
    for (int x = 1; x < k; x++) C[x] += C[x - 1];   // 累加以后 C[x]：不大于 x 的元素个数
    for (int i = n - 1; i >= 0; i--) {       // 从后往前放，保证稳定
        B[C[A[i]] - 1] = A[i];               // 不大于 A[i] 的有 C[A[i]] 个，它放在下标 C[A[i]]-1
        C[A[i]]--;                           // 下一个相同的值，放在它前面一格
    }
    free(C);
}
 
void cmpCountSort(int a[], int b[], int n) { // 教材试题解析版：两两比较来计数
    int *count = (int *)calloc(n, sizeof(int));   // count[i]：比 a[i] 小的元素个数
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] <= a[j]) count[j]++;    // 带等号：相等时算后面那个大，保证稳定
            else count[i]++;
    for (int i = 0; i < n; i++) b[count[i]] = a[i];   // count[i] 正好是 a[i] 在结果中的下标
    free(count);
}

复杂度：CountSort 时间 ，空间 ，稳定。cmpCountSort 时间 ，比较次数是 。

基数排序（★）

void RadixSort(LinkList L, int d) {          // 带头结点的单链表；关键字是非负整数，最多 d 位
    LNode *front[10], *rear[10];             // 10 个队列（基数 r = 10）的队头、队尾指针
    for (int p = 0, base = 1; p < d; p++, base *= 10) {   // 从个位开始，一共 d 趟
        for (int r = 0; r < 10; r++) front[r] = rear[r] = NULL;
        LNode *s = L->next;
        while (s != NULL) {                  // 分配：每个结点按当前这一位，接到对应队列的队尾
            LNode *nx = s->next;             // 先记下后继，s 马上要被摘下来
            int r = s->data / base % 10;     // 取出当前这一位
            s->next = NULL;
            if (front[r] == NULL) front[r] = rear[r] = s;
            else { rear[r]->next = s; rear[r] = s; }
            s = nx;
        }
        LNode *tail = L;                     // 收集：按 0～9 的顺序，把非空队列首尾相接
        for (int r = 0; r < 10; r++)
            if (front[r] != NULL) {
                tail->next = front[r];
                tail = rear[r];
            }
        tail->next = NULL;
    }
}

复杂度：时间 ，空间 （只有 个队头、队尾指针），稳定。

关键边界

代码为什么
计数排序从后往前放相同的值里，后出现的先放到靠后的位置，原来的相对次序就保持不变，所以稳定
B[C[A[i]] - 1] 要减 1C[x] 是「不大于 的个数」，是个数不是下标
cmpCountSort 的 <=一个等号决定稳定与否。不带等号的话，相等时前面元素的 count 加 1，它会排到后面去
基数排序接到队尾，按 0～9 收集每一趟都必须稳定，否则高位那一趟会打乱低位已经排好的次序，结果就错了
基数排序从个位开始这是最低位优先（LSD）。最后一趟按最高位排，高位相同的元素保持低位已经排好的次序

易错点

  • 基数排序的空间是 ，不是 ：链表结点本来就在，额外用的只有 个队列的指针。用数组实现的话，要额外开一个长度为 的数组。
  • 基数排序是唯一一个不基于比较的排序（考纲范围内）。计数排序是教材 * 选学内容。
  • 计数排序只适合值域不大的整数， 很大时空间开销太大。

链接

反向链接