计数排序，为什么要用累加

Question

我翻遍了很多网站的计数排序代码。他们正在使用计数的累积和，然后进一步进行数组索引。我想问他们为什么不使用普通数组打印：

如同 [count(origArray(i)) 中的 origArray(i) 的计数！=0]，遍历 count(origArray(i)) 并打印 i.

这是不是因为使用Counting sort的要点是NO COMPARISON，我的代码中有和0的比较。

查看此代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class CountingSort {
    public static void main(String... args) throws IOException {
        new CountingSort().sort();
    }

    private void sort() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        int max = 0;
        String data = "";
        while ((line = reader.readLine()) != null && line.length() != 0) {
            data += line;
        }
        String[] ip = data.split(" ");
        int[] intArray = new int[ip.length];
        for (int i = 0; i < ip.length; i++) {
            intArray[i] = Integer.parseInt(ip[i]);
            if (intArray[i] > max)
                max = intArray[i];
        }
        int[] count = new int[max+1];
        Arrays.fill(count, 0);
        for (int i = 0; i < intArray.length; i++) {
            ++count[intArray[i]];
        }
        for (int i = 0; i < max; i++) {
            if (count[i] != 0) {
                for (int j = 0; j < count[i]; j++)
                    System.out.print(" " + i);
            }
        }
    }

}

Answer 1

累计和是为了计算重复次数：您的数组中可能有值 200 的 3 倍。在这种情况下，count[200] 的值为 3。因此，您需要将其打印三次（代码中的最后一个 for 循环）。

在排序算法中，"comparison" 表示将数组的值相互比较。在这个算法中没有这样的比较。

该算法的复杂度为 O(n)，但如果要排序的值可能很大，则需要大量存储空间。

Answer 2

您共享的链接上的实现不会打印 System.out.print(" " + i)，因为它们认为 i 与正在排序的项目不同。如果你想对 chars 进行排序，这将是正确的，因为你需要一个转换。

由于您使用的是整数，因此您的实现没有任何问题。事实上，您最终得到了维基百科上提到的算法的一种变体：

If each item to be sorted is itself an integer, and used as key as well, then the second and third loops of counting sort can be combined; in the second loop, instead of computing the position where items with key i should be placed in the output, simply append Count[i] copies of the number i to the output.

Answer 3

在您的实施中，您试图从 count 数组生成排序输出。如果你想从未排序的整数数组中创建排序列表，那就太好了。

但是，现在我要讨论一个无法从 count 数组生成输出的问题场景。

假设我们有一个包含两个字段的 Data 列表（categoryID 和 itemName） .我们可以假设字段 categoryID 在 [0..10] 范围内。我们想通过Counting-Sort算法，根据categoryID做一个排序列表。样本输入和输出如下：

Unsorted Items -->
2  Computer
5  Shirt
3  Bier
0  Soap
2  Laptop
3  Vodka
0  Lotion
3  Whiskey


Sorted Items -->
0  Soap
0  Lotion
2  Computer
2  Laptop
3  Bier
3  Vodka
3  Whiskey
5  Shirt

现在我们可以轻松计算每个类别的项目数。但是根据这个计数信息，我们无法生成同时包含 categoryID 和 productName 的输出。

因此，计数排序使用了累加和的思想，实际上是计算一个item在输出数组中的最终索引的一种方式。这是此问题的解决方案。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Data
{
public:
    //let's assume category ID is in range [0..10]
    //Therefore, We can use counting sort for array of Data
    int category;
    string name;
    Data(){}
    Data(int id, string str)
    {
        category = id;
        name = str;
    }
};

vector<Data> Counting_Sort(vector<Data> A)
{
    int k = 10; //maximum category
    vector<int> C(k+1,0);
    for(int i=0; i<A.size(); i++)
    {
        C[ A[i].category ] = C[ A[i].category ] + 1;
    }

    for(int i=1; i<=k; i++)
    {
        C[i] = C[i-1] + C[i];
    }

    vector<Data> B(A.size() + 1);
    for(int i = A.size()-1; i>=0; i--)
    {
        B [ C [ A[i].category ] ] = A[i];
        C [ A[i].category ] = C [ A[i].category ] - 1;
    }

    vector<Data> ans(B.begin()+1, B.end());
    return ans;
}

void Show(vector<Data> vals)
{
    for(Data val:vals) cout<<val.category<<"  "<<val.name<<endl;
}

vector<Data> inputData()
{
    int numberOfItems = 8;
    string productNames[] = {"Computer", "Shirt", "Bier", "Soap", 
                             "Laptop", "Vodka", "Lotion", "Whiskey"};
    int categoryID[] = {2,5,3,0,2,3,0,3};
    vector<Data> inData;
    for(int i=0; i<numberOfItems; i++)
    {
        Data data(categoryID[i], productNames[i]);
        inData.push_back(data);
    }
    return inData;
}
int main()
{
    vector<Data> A = inputData();
    cout<<"Unsorted Items --> "<<endl;
    Show(A);
    vector<Data> ans = Counting_Sort(A);
    cout<<"\n\nSorted Items --> "<<endl;
    Show(ans);
    return 0;
}

希望对您有所帮助！

计数排序，为什么要用累加

Counting sort, why use cumulative

java

sorting

counting-sort