c - 使用计数排序对给定数组进行排序

问题描述

这是代码：

    #include<stdio.h>
    int main(){
       int input[20],output[20],n,i,element,max;
       printf("Enter the no of elements");
       scanf("%d ",&n);
       for(i = 1;i<=n;i++){
         scanf("%d",&input[i]);
       }
       max = input[1];
    
       for(i=1;i<=n;i++){
         if(max<input[i]){
            max = input[i];
         }
       } 
    
      int c[max + 1];
      memset(c,0,sizeof(c));

      for(i=1;i<=n;i++){
         c[input[i]]++ ;
      }
      for(i = 1;i<=max;i++){ 
        c[i] = c[i] + c[i-1];
      }
    
      for(i = 1;i<=max;i++){
        output[c[input[i]]] = input[i];
        c[input[i]]--;
      }         
      for (i = 1; i < n; i++) {
        input[i] = output[i];
      }
      for (i = 1; i <= n; ++i) {
        printf("%d ", input[i]);
      }

      return 0;
}

这适用于某些情况，但不适用于某些情况。谁能告诉我我做错了什么？例如：输入元素的数量：7 输入：3 2 5 16 3 2 输出：1 4223016 2 3 3 5 2（此处不起作用）

标签： calgorithmsorting

首先，你的问题前后矛盾。您提供n=7但仅传递了 6 个数字作为输入。

其次，实施中需要进行一些更改：

对于您的代码中的以下代码段：

for(i = 1;i<=max;i++){
    output[c[input[i]]] = input[i];
    c[input[i]]--;
}

循环应该从 1 持续到 n：for(i = 1;i<=n;i++)

对于以下代码段：

for (i = 1; i < n; i++) {
    input[i] = output[i];
}

循环应该从 1 持续到 n: for(i = 1;i<=n;i++)。

看看下面的正确实现：

#include<stdio.h>

int main(){

    int input[20],output[20],n,i,element,max;
    
    printf("Enter the no of elements");
    scanf("%d ",&n);
    
        for(i = 1;i<=n;i++){
            scanf("%d",&input[i]);
        }
    
    max = input[1];
    
        for(i=1;i<=n;i++){
            if(max<input[i]){
                max = input[i];
            }
        }     
    
    int c[max + 1];

    memset(c,0,sizeof(c));

    for(i=1;i<=n;i++){
        c[input[i]]++ ;
    }

    for(i = 1;i<=max;i++){ 
        c[i] = c[i] + c[i-1];
    }

    for(i = 1;i<=n;i++){
        output[c[input[i]]] = input[i];
        c[input[i]]--;
    }

    for (i = 1; i <= n; i++) {
        input[i] = output[i];
    }
    
    for (i = 1; i <= n; ++i) {
        printf("%d ", input[i]);
    }

    return 0;
}

输入：

7
3 2 5 16 3 2 8000

输出：

2 2 3 3 5 16 8000

PS：此算法不适用于负数。您可以考虑如何处理负数。

c - 使用计数排序对给定数组进行排序

问题描述

解决方案

推荐阅读