计数排序算法-DEV365 开发者社区

本文说明了如何实现和使用计数排序算法。由于我是Java开发人员，因此示例将使用Java，但它适用于任何其他编程语言。如果您想摘要，只需滚动到摘要部分。

假设有一个给定的[1, 3, 1, 5]数组，需要按升序排序。很简单吗？

计数排序

这是wiki的伪代码，它提供了一种基本算法：

function CountingSort(input, hi)
    count ← array of hi + 1 zeros //1 

    for i = 0 to length(input) - 1 do //2
        j = key(input[i])
        count[j] = count[j] + 1

    for i = 1 to hi do //3
        count[i] = count[i] + count[i - 1]

    output ← array of same length as input //4

    for i = length(input) - 1 down to 0 do //5
        j = key(input[i])
        count[j] = count[j] - 1
        output[count[j]] = input[i]

    return output

不用担心每个单个步骤都会有一个解释，但首先，让我们陈述一些术语：
input-是给定的数组。
output-是结果排序的数组。
count-是一个用于计数的数组。
hi-是input中的最大元素。

第一部分。创建一个计数数组

创建填充有hi + 1长度的0（零）的count阵列。它将将每个元素的计数存储在数字上作为索引。例如，从input阵列中的3，其发生的计数将存储在count[3]单元格中。

现在，很明显，为什么我们需要从input数组中了解hi元素，以及为什么需要5 ^th index。

int[] countingSort(int[] input, int hi) {
    var count = new int[hi + 1]; //1

    //Rest of the code 
}

java默认情况下填充一个带有零的数组，但是对于其他语言，可能会有一些处理来准备count数组。

第二部分。计数元素数

接下来，使用count数组，所有元素都需要通过在input数组上循环来计算所有元素，它将帮助我们执行以下步骤。将[1, 3, 1, 5]作为input阵列，结果为[0, 2, 0, 1, 0, 1]。

这是Java的示例：

int[] countingSort(int[] input, int hi) {
    var count = new int[hi + 1]; //1

    for (var n : input) { //2
        count[n]++;
    }

    //Rest of code 
}

第三方。计算索引

这个时间循环在count数组上以计算索引，其中count[i] = count[i] + count[i - 1]（除了保持不变的0索引元素外，count[i] = count[i] + count[i - 1]。通过这样做，我们将知道每个元素需要放置在哪里（请参阅以下步骤）。例如，对于带有计数[0, 2, 0, 1, 0, 5]的input数组[1, 3, 1, 5]，索引阵列将为[0, 2, 2, 3, 3, 4]。

int[] countingSort(int[] input, int hi) {
    var count = new int[hi + 1]; //1

    for (var n : input) { //2
        count[n]++;
    }

    for (var i = 1; i < count.length; i++) { //3
        count[i] += count[i - 1];
    }

    //Rest of code
}

第四部分。创建输出数组

创建与原始长度相同长度的output数组。这里没什么特别的，但是以后会很重要。

int[] countingSort(int[] input, int hi) {
    var count = new int[hi + 1]; //1

    for (var n : input) { //2
        count[n]++;
    }

    for (var i = 1; i < count.length; i++) { //3
        count[i] += count[i - 1];
    }

    var output = new int[input.length]; //4

    //Rest of code

    return output;
}

第五部分。填充输出阵列

[0, 2, 2, 3, 3, 4]索引阵列来自上一步的数组意味着以下内容：每个元素可以用作元素本身作为独家端的范围，而上一个元素作为包容性开始（零索引元素将0作为包容性lo范围）：

元素0在范围内[0, 0)，零重复
元素1在范围内[0, 2)，两个重复
元素2在范围内[2, 2)，零重复
元素3在范围内[2, 3)，一个重复
元素4在范围内[3, 3)，零重复
元素5在范围内[3, 4)，一个重复

在这一点上，所有要形成output阵列的所有内容可用。在input数组上循环，将元素从其插入output数组中插入。

int[] countingSort(int[] input, int hi) {
    var count = new int[hi + 1]; //1

    for (var n : input) { //2
        count[n]++;
    }

    for (var i = 1; i < count.length; i++) { //3
        count[i] += count[i - 1];
    }

    var output = new int[input.length]; //4

    for (var i = input.length - 1; i >= 0; i--) { //5
        output[--count[input[i]]] = input[i];
    }

    return output;
}

这可能有点棘手，但没什么特别的。首先，input[i]返回input数组中的当前元素。 count[input[i]]返回该元素的独家最终范围。例如，对于数字5，它将是4。然后，--将其降低至3-> --count[input[i]]，现在具有包含性。最后，将元素设置为output阵列output[--count[input[i]]] = input[i]的位置。向后循环有助于保存稳定。这个术语将有一段。

可能的改进

好吧，这是一个足够好的实现，但是可以进行一些改进。

检查输入

如果input为空或空，或者仅包含一个元素怎么办？在这种情况下，我们无能或不应该做。

int[] countingSortImproved(int[] input) {
    if (input == null || input.length < 2) return input;
    //The rest of code
}

未知最大元素

如果我们不知道数组中的hi元素怎么办？那么count阵列的长度也未知。让我们自己找到它。

int[] countingSortImproved(int[] input) {
    if (input == null || input.length < 2) return input;

    //safe to do, since we know that the length is at least 2
    var hi = input[0]; 

    for (var i = 1; i < input.length; i++) {
        hi = Math.max(hi, input[i]);
    }

    var count = new int[hi + 1]; //1
    //The rest of code
}

已经排序的输入

如果已经对input数组进行了排序怎么办？最好先检查一下以避免进行很多操作。

int[] countingSortImproved(int[] input) {
    if (input == null || input.length < 2) return input;

    var hi = input[0]; 
    var sorted = true;
    for (var i = 1; i < input.length; i++) {
        hi = Math.max(hi, input[i]);
        sorted &= input[i - 1] <= input[i];
    }
    if (sorted) return input;

    var count = new int[hi  + 1]; //1
    //The rest of code
}

与查找hi一起进行检查，可以检查当前元素，如果它更大或等于上一个元素。 &=累积了所有测量值sorted。只有当返回的所有支票返回true时，input才可以返回。

大和/或负数

到目前为止一切都很好，但是如果有负数[-3, 2, 1]怎么办？或大数字[10 ³⁰ -1，10 ³⁰ -2，10 ³⁰]？算法将在第一种情况下失败，因为计数数组中没有-3索引。在第二种情况下，它将起作用，但count阵列将为10 ³⁰长。
为了解决这两个问题，可以引入轮班。让我们以我们的lo元素，同意这将是我们的0索引。
第一种情况：-3-> 0; 2-> 5; 1-> 4.
第二种情况：10 ³⁰ -2-> 0; 10 ³⁰ -1-> 1; 10 ³⁰ - > 2

更新的代码看起来像这样：

int[] countingSortImproved(int[] input) {
    if (input == null || input.length < 2) return input;

    var hi = input[0];
    var lo = input[0];
    var sorted = true;
    for (var i = 1; i < input.length; i++) {
        hi = Math.max(hi, input[i]);
        lo = Math.min(lo, input[i]);
        sorted &= input[i - 1] <= input[i];
    }
    if (sorted) return input;

    //now the count would fit in the [lo, hi] range  
    var count = new int[hi - lo + 1]; //1

    for (var n : input) { //2
        count[n - lo]++; //transform the index, -3 or 10^30-2 to 0;
    }

    for (var i = 1; i < count.length; i++) { //3
        count[i] += count[i - 1];
    }

    var output = new int[input.length]; //4

    for (var i = input.length - 1; i >= 0; i--) { //5
        //count index now input[i] - lo
        output[--count[input[i] - lo]] = input[i];
    }

    return output;
}

更新的步骤是1、3和5。

结合步骤4和5

好吧，让我们考虑以下input和count阵列：[3, 2, 3, 5]和[1, 2, 0, 1]，lo = 2。可以循环循环在count数组上，并添加与数量数量的数字一样多。因此，即使不再需要原始阵列。

2一次（索引0）
3两次，（索引1）
4零次，（索引2）
5一次，（索引3）

结果，

[2, 3, 3, 5]。但是请注意，这种变化使算法不是稳定。对于INT来说，这并不重要，但是如果某些对象进行分类并且至关重要，那么具有原始的对象，则此改进将无效。

int[] countingSortImprovedAndCombined(int[] input) { if (input == null || input.length < 2) return input; var hi = input[0]; var lo = input[0]; var sotred = true; for (var i = 1; i < input.length; i++) { hi = Math.max(hi, input[i]); lo = Math.min(lo, input[i]); sorted &= input[i - 1] <= input[i]; } if (sorted) return input; var count = new int[hi - lo + 1]; //1 for (var n : input) { //2 count[n - lo]++; } var output = new int[input.length]; //4 var index = 0; for (var i = 0; i < count.length; i++) { // 3 & 5 combined for (var j = 0; j < count[i]; j++) { output[index++] = i + lo; } } return output; }

问题可以解决

现在让我们考虑一些问题，而不是使用计数算法进行初始升序排序。

排序降序

要按降序排序，所有需要完成的就是变更步骤3计算索引。

原始：

for (var i = 1; i < count.length; i++) { //3 count[i] += count[i - 1]; }

更改：

for (var i = count.length - 2; i >= 0 ; i--) { //3 count[i] += count[i + 1]; }

仅计数count数组末端的索引。

查找最大发生

这里的要点是找到最大出现的数字。在这种情况下，我们需要的只是count阵列，使算法变得更加简单。

int countingSortImprovedMaxOccurrence(int[] input) { if (input.length < 2) return input[0]; var hi = input[0]; var lo = input[0]; for (var i = 1; i < input.length; i++) { hi = Math.max(hi, input[i]); lo = Math.min(lo, input[i]); } var count = new int[hi - lo + 1]; //1 var maxOccurrence = input[0]; for (var n : input) { //2 if (++count[n - lo] > count[maxOccurrence - lo]) { maxOccurrence = n; } } return maxOccurrence; }

第一个步骤是相同的，而3 ^rd，4 ^th和5 ^th不再需要。这里的小技巧是在计算计数过程中找到最大出现元素，并避免额外的循环。

删除重复

任务很简单，以及所需的排序删除重复项。可以修改count数组以存储boolean，因为如果至少出现一次，元素的计数总是为1。此外，需要对不止一次的元素进行计数，以使output数组具有适当的大小。

int[] countingSortImprovedDistinct(int[] input) { if (input == null || input.length < 2) return input; var hi = input[0]; var lo = hi; var sorted = true; for (var i = 1; i < input.length; i++) { hi = Math.max(hi, input[i]); lo = Math.min(lo, input[i]); sorted &= input[i - 1] <= input[i]; } if (sorted) return input; var count = new boolean[hi - lo + 1]; //1 var removed = 0; for (var n : input) { //2 if (count[n - lo]) { removed++; } else { count[n - lo] = true; } } var output = new int[input.length - removed]; //4 var outputIndex = 0; for (var i = 0; i < count.length; i++) { //5 if (count[i]) { output[outputIndex++] = i + lo; } } return output; }

可以通过适应或修改该算法来解决许多其他问题。

复杂性和特征

最大的限制之一是数字分布。我们解决了与之相关的几个问题，但是在下种情况下，使用计数排序效率低下。 [2147483647, -2147483648]（Java的最大和最小数字），尽管很明显，排序很简单，但是count阵列将非常巨大，甚至不适合int范围。因此，仅当hi - lo在[0, 2147483647)范围内，以前的实现才能起作用。

除非将步骤4和5组合在一起，否则该算法是稳定。稳定在分类算法的背景下，意味着最初处于正确位置的元素将不会在分类过程中从该位置移动。当割草是一个昂贵的操作时，这可能很重要。例如，如果在书架上进行分类，那就很棒了，不要把书本移到他们的位置。

默认情况下，它不是，但是如果修改以结合步骤4和5，则将是在场。现场意味着将修改原始数组以提供结果。由于结果正在创建新数组，因此不合适。如果以书架为类比，将建造一个新的书架，并充满旧书籍。

算法的空间复杂性是O(n+k)，其中k是计数数组的大小，而n是原始数组的大小。实现需要具有计数阵列和结果数组，使主要空间逐渐缩小。如果将步骤4和5组合在一起，则O(k)，因为不再需要结果数组。

时间复杂性再次为O(n+k)。首先，在计数数组上有一个循环来创建它，并将0设置为每个元素-k操作。然后循环循环输入数组以计数元素-n操作。计数数组的下一个循环，以计算索引-k操作。 n操作以创建结果数组。最后，在结果数组上循环以填充排序值-n操作。结果，有k + n + k + n + n = 3n + 2k并简化为O(n+k)。

概括

计数排序是具有Θ(n+k)时复杂性和O(n+k)空间复杂性的最佳排序算法之一。它由步骤组成：创建计数数组，输入中的计数元素，循环在计数数组中以计算索引count[i] += count[i-1]，查看输入数组向后浏览以填充输出数组减少索引。
它是稳定，但不是在场。可以修改为在场，但不能稳定。如果hi - lo明显大于数量的元素，则效率低下。

链接

https://en.wikipedia.org/wiki/Counting_sort
https://www.bigocheatsheet.com/
https://en.wikipedia.org/wiki/Category:Stable_sorts
https://en.wikipedia.org/wiki/In-place_algorithm
https://www.amazon.com/Algorithms-Java-Parts-1-4-Pts-1-4/dp/0201361205
https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X/ref=sr_1_1