标签: counting-sort

是否可以并行进行计数排序并实现 O(n/p) 运行时？

举个例子，我们有一个包含数百万个元素的数组，范围从 1 到 10。合并排序的运行时间不会超过 O(nlogn) 时间。应用于此问题的计数排序将在 O(n) 时间内运行。并行化计数排序可能很有趣。如果我们为每个处理器分配一个包含 n/p 个元素的子数组，并且每个处理器都有自己的大小为 9 的计数数组，那么累积元素计数的初始步骤应该花费 O(n/p) 时间。将所有计数数组合并为单个数组应该花费 O(p) 时间，因为您只迭代 p 个计数数组，每个数组的大小都是恒定的。

我一直无法完全思考计数排序的最后一步，其中元素按顺序排列。如果计数数组的元素是原子的，您可以将原始数组的 n/p 部分分配给各个处理器并实现一些并行化，但计数数组的各个元素会出现争用，这可能会大大减少并行化。如果输入数组都是 10，则所有处理器都将在计数数组的第 9 个元素上进行序列化，从而将算法效率降低到 O(n)。

您可以将 count 数组的子数组分配给 p 个处理器中的每一个，然后返回 O(n/p) 运行时，但前提是元素分布相当均匀。而且，在我们的示例中，您将被限制为 10 个处理器。如果元素分布不均，一个或多个处理器可能会承担更大比例的工作。例如，如果输入数组中的一半元素为 10，则一个处理器将不得不单步执行该数组的一半。最坏的情况是，数组全部为 10，单个处理器必须遍历整个数组，将运行时间降低到 O(n)。

也许您可以在多个处理器之间划分计数数组的各个元素。例如，如果输入数组中有 50 个 10，则计数数组的元素 9 将反映这一点。您可以让 5 个处理器将 10 个 10 写入输出数组中的正确位置。如果 count 数组的每个索引位置的元素少于 p 个，这又会转化为 O(n) 运行时，但它避免了元素值分布不均匀的问题。

是否可以在 O(n/p) 时间内进行计数排序？

我有一个计数排序，它应该为x > 0，它按降序对我的数组进行排序。然而，在考虑负数时，我的实现逻辑会崩溃，因为我正在处理辅助数组中的负索引values。我想以某种方式使用uint但我对它不是很熟悉。

我怎样才能克服这个使用计数排序。

static void countingSort(int[] arr)    
{
    int i, j, max = -1; // I think it falls apart about here 
    int[] values;

    for (i = 0; i < arr.Length; i++)
        if (arr[i] > max) max = arr[i];

    values = new int[max + 1];

    //Here it reaches for a negative index when i = 2,looking for -6.            
    for (i = 0; i < arr.Max(); i++)
        values[arr[i]]++; 

    i = 0; j …

与 Python 的排序相比，我的基数排序函数输出排序但错误的列表：

My radix sort: ['aa', 'a', 'ab', 'abs', 'asd', 'avc', 'axy', 'abid']
Python's sort: ['a', 'aa', 'ab', 'abid', 'abs', 'asd', 'avc', 'axy']

* 我的基数排序不做填充
* 它的机制是最低有效位 (LSB)
* 我需要利用每个单词的长度

以下是我的代码。

def count_sort_letters(array, size, col, base):
    output   = [0] * size
    count    = [0] * base
    min_base = ord('a')

    for item in array:
        correct_index = min(len(item) - 1, col)
        letter = ord(item[-(correct_index + 1)]) - min_base
        count[letter] += 1

    for i in range(base - 1):
        count[i + 1] += …

我正在阅读有关计数排序的算法，其中一个步骤是

for(i = 1 to k) 
   c[i] = c[i]+c[i-1];

为什么我们需要这一步？

为什么我们不能使用它

for(i = 0 to k)
    while(c[i]--)
        Output i/Use i as key.

我想到的一个问题是，我们是否需要数据本身（可能就像引用特定索引的字符串一样）。

但是之后，我们可以使用2D向量。在这种方法中，我们将数据从0到99进行排序有什么不好的地方。

int a[100];
for(int i = 0 ; i < 100; ++i)
    a[i] = 0;
string s;
vector<vector<string>> data(100);
int temp;
for(int i = 0 ; i < n ; ++i){
    cin>>temp;
    a[temp]++;
    getline(cin,s);
    data[temp].push_back(s);
}

for(int i = 0 ; i < 100; ++i){
    int current = 0;
    while(a[i]--){
        cout<<data[i][current]<<" ";
        ++current;
    }
}

以下是我对计数排序的尝试.我已经绘制了我的逻辑图,用口头表达,并彻底评论了我的代码.但是,我的代码会导致分段错误.我理解分段错误表示非法访问内存,因此这必然意味着我的一个索引值正试图访问数组范围之外的索引.但是,我无法弄清楚为什么会这样.

幸运的是,我的调试器突出显示了下面的行,我在评论中也注意到了这一点,其中发生了分段错误.尽管如此,我完全被难倒了.非常感谢任何帮助理解这个分段错误的性质,谢谢.

void sort(int values[], int n)
{

    //create array of finite size (65536)
    int countArray[INT_MAX];

    //create array to eventually store sorted values
    int sortedValues[n];

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }


    //starting index for sortedValues[]
    int sortedIndex = 0;

    //loop until we've reached the end of sortedValues[]
    while(sortedIndex < n) {

        //loop through each index value of countArray
        //j represents …

这是我的计数排序程序:

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int arr[] = new int[n];
        int b[] = new int[n+1];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int c[] = new int[100];
        for (int i = 1; i < 100; i++) {
            c[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            c[arr[i]] = c[arr[i]] + 1;
        }
        for (int i = 1; …

快速排序:

• 最坏情况o(n ^ 2)
• 平均情况O(nlogn)

计数排序:

• 在所有情况下o(n)

快速排序和计数排序都是稳定的算法.

如果存在这两个条件,为什么快速排序仍然比计数排序更好？