标签: counting-sort

我正在阅读基数,计数和桶排序的定义,似乎所有这些都只是下面的代码:

public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}

我知道我不对,所以我错过了什么？如果您认为可以帮助解释Java或C,请显示代码

设计一个算法，对存在重复的n 个整数进行排序。不同数字的总数是k。你的算法应该有时间复杂度O(n + k*log(k))。预计时间足够了。对于k 的哪些值，算法变为线性？

我无法提出满足条件的整数排序算法，它必须是O(n + k*log(k))。我不是一个非常高级的程序员，但在这个人应该为xi列表中的所有数字提出一种算法之前，我遇到了问题0 ? xi ? m，该算法是 O(n+m)，其中 n 是列表中的元素数列表和 m 是列表中最大整数的值。我通过使用计数排序轻松解决了这个问题，但我在这个问题上很挣扎。对我来说最困难的k*log(k)条件是 ordo 表示法下的术语，如果n*log(n)相反，我将能够使用合并排序，对吗？但现在这是不可能的，所以任何想法都会非常有帮助。

提前致谢！

我在hackerrank遇到了一个问题. https://www.hackerrank.com/challenges/countingsort4

由于超时,我的第一次尝试通过了除最后一个之外的所有测试用例.在未能提出更高效的算法之后,我通过使用StringBuilder而不是直接连接字符串来改进代码.这使得运行时间从5秒到3.5秒不等.

我的问题是,还有其他方法可以改善运行时间吗？谢谢.

以下是我的代码.

public class Solution {

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

        int N = scanner.nextInt();
        scanner.nextLine();

        int[] oriNum = new int[N];        
        String[] oriStr = new String[N];
        int[] count = new int[100];
        int[] indices = new int[100];
        int[] output = new int[N];

        // save the originals and the count array
        for (int i = 0; i < N; i++) {
            oriNum[i] = scanner.nextInt();
            oriStr[i] = scanner.nextLine().trim();
            count[oriNum[i]]++;
        }

        // accumulate the count …

我需要有关以下计数排序实现的帮助。是不是因为x的值太大了？我遇到分段错误。gdb 是这样说的：

Program received signal SIGSEGV, Segmentation fault.
___chkstk_ms () at /usr/src/debug/gcc-5.4.0- 1/libgcc/config/i386/cygwin.S:146
146     /usr/src/debug/gcc-5.4.0-1/libgcc/config/i386/cygwin.S: No such file or directory.

这是代码片段，

void radix_sort::sort_array(int array[], int n)
{
    int arrayB[n];

    auto k = *std::max_element(&array[0], &array[n - 1]);
    auto m = *std::min_element(&array[0], &array[n - 1]);

    long int x = k - m + 1;
    int arrayC[x];

    for (auto i = 0; i < n; i++)
        arrayC[array[i] - m]++;

    for (long int i = 1; i < x; i++)
        arrayC[i] = arrayC[i] + …

如果我们知道数组中的所有元素都是由给定数字限定的,则计算排序是线性时间.如果我们采用一般数组,我们只能在线性时间扫描数组,找到数组中的最大值然后应用计数排序？

计数排序是平均时间复杂度为O(n+K)的排序算法，计数排序假设每个输入元素都是0到K范围内的整数。

为什么我们不能线性搜索未排序数组中的最大值，使其等于 K，然后对其应用计数排序？

计数排序基本上是将计数值存储在哈希表排序结构中，然后打印出这些值。

我采用的方法是：

1. 遍历输入数组并按以下方式存储总计数 count[arr[i]]++

2. 同样，遍历 count 数组并打印i(th)索引号，次数与 中的值一样多count[arr[i]]。这不是正确的方法吗？

在我阅读教程的大多数地方，他们将先前元素的计数总和存储在计数数组中，然后通过首先减少计数然后打印它来放置在排序数组中。

我的方法有问题吗？

谢谢！

这是我的计数排序的两个实现

在这个非常简单的实现中，我所做的就是计算元素出现的次数，并在输出数组中插入与出现次数相同的次数。实施1

public class Simple
{
    static int[] a = {5,6,6,4,4,4,8,8,8,9,4,4,3,3,4};

    public static void main(String[] args)
    {
        fun(a);
        print(a);
    }

    static void fun(int[] a)
    {
        int max = findMax(a);

        int[] temp = new int[max+1];
        for(int i = 0;i<a.length;i++)
        {
            temp[a[i]]++;
        }
        print(temp);

        //print(temp);
        int k = 0;
        for(int i = 0;i<temp.length;i++)
        {
            for(int j = 0;j<temp[i];j++)
                a[k++] = i;
        }
        print(a);
    }

    static int findMax(int[] a)
    {
        int max = a[0];
        for(int i= 1;i<a.length;i++)
        {
            if(a[i] > max)
                max = …

我在GeeksForGeeks上查看计数排序的代码上的计数排序代码，在算法的最后阶段，原始数组中的元素被插入到排序数组中的最终位置（倒数第二个 for 循环），输入数组以相反的顺序遍历。

我似乎无法理解为什么你不能从输入数组的开头到结尾，如下所示：

for i in range(len(arr)): 
        output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] 
        count_arr[arr[i] - min_element] -= 1

是否有一些我错过的以相反顺序进行的微妙原因？如果这是一个非常明显的问题，我深表歉意。我在这里也看到了以相同风格实现的计数排序。

任何评论都会有帮助，谢谢！

这是在 Javascript 中实现计数排序的好方法还是最佳方法？找不到标准的 JS 计数排序示例。

function countingSort(arr){
  var helper = []; // This helper will note how many times each number appeared in the arr
                   // Since JS arrary is an object and elements are not continuously stored, helper's Space Complexity minor that n
  for(var i = 0; i<arr.length; i++){
    if(!helper[arr[i]]){
        helper[arr[i]] = 1;
    }else{
        helper[arr[i]] += 1;
    }
  }

  var newArr = []; 
  for(i in helper){
    while(helper[i]>0){
        newArr.push(parseInt(i));
        helper[i]--;
    }
  }
  return newArr; 
}

var arr = [5,4,3,2,1,0];
console.log(countingSort(arr)); …