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

• 计算每个键在要排序的数组中存在的频率。这些计数被写入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);
}