按线性时间排序

按线性时间排序

首先，让我们重新讨论计数排序的工作原理：

• 计算每个键在要排序的数组中存在的频率。这些计数被写入size数组

  k

  。
• 计算键计数的部分和。这给出了已排序数组中每个等键箱的起始位置。
• 将数组中的项目移到其最终位置，从而为每个项目增加相应仓位的起始位置。

现在的问题是如何就地执行最后一步。就地置换的标准方法是选择第一个元素，并将其与处于正确位置的元素交换。对交换的元素重复此步骤，直到我们击中属于第一个位置的元素（一个循环已完成）。然后，对第二，第三等位置的元素重复整个过程，直到处理完整个数组为止。

计数排序的问题在于最终位置不容易获得，而是通过增加最终循环中每个bin的起始位置来计算的。为了从不增加元素的起始位置两次，我们必须找到一种方法来确定某个位置的元素是否已经移动到那里。这可以通过跟踪每个垃圾箱的原始起始位置来完成。如果某个元素位于原始起始位置和箱中下一个元素的位置之间，则该元素已经被触摸。

这是C99中的一种实现，可以在其中运行，

O(n+k)

并且仅需要两个大小的数组即可

k

作为额外存储。最终的排列步骤不稳定。

#include <stdlib.h>void in_place_counting_sort(int *a, int n, int k){    int *start = (int *)calloc(k + 1, sizeof(int));    int *end   = (int *)malloc(k * sizeof(int));    // Count.    for (int i = 0; i < n; ++i) {        ++start[a[i]];    }    // Compute partial sums.    for (int bin = 0, sum = 0; bin < k; ++bin) {        int tmp = start[bin];        start[bin] = sum;        end[bin]   = sum;        sum += tmp;    }    start[k] = n;    // Move elements.    for (int i = 0, cur_bin = 0; i < n; ++i) {        while (i >= start[cur_bin+1]) { ++cur_bin; }        if (i < end[cur_bin]) { // Element has already been processed. continue;        }        int bin = a[i];        while (bin != cur_bin) { int j = end[bin]++; // Swap bin and a[j] int tmp = a[j]; a[j] = bin; bin = tmp;        }        a[i] = bin;        ++end[cur_bin];    }    free(start);    free(end);}

编辑： 这是

k

基于Mohit Bhura的方法仅使用单个数组大小的另一个版本。

#include <stdlib.h>void in_place_counting_sort(int *a, int n, int k){    int *counts = (int *)calloc(k, sizeof(int));    // Count.    for (int i = 0; i < n; ++i) {        ++counts[a[i]];    }    // Compute partial sums.    for (int val = 0, sum = 0; val < k; ++val) {        int tmp = counts[val];        counts[val] = sum;        sum += tmp;    }    // Move elements.    for (int i = n - 1; i >= 0; --i) {        int val = a[i];        int j   = counts[val];        if (j < i) { // Process a fresh cycle. Since the index 'i' moves // downward and the counts move upward, it is // guaranteed that a value is never moved twice. do {     ++counts[val];     // Swap val and a[j].     int tmp = val;     val  = a[j];     a[j] = tmp;     j = counts[val]; } while (j < i); // Move final value into place. a[i] = val;        }    }    free(counts);}