使用计数排序按升序排列字符数组

Question

Input char a[10] = {'c','b','c','d','E','C','a','A','b','C'};

输出：A a b b C C c c d e

我被赋予了一个字符数组，我必须按升序对其进行排序，而我必须使用计数排序来做到这一点

我到目前为止已经尝试过：

#include <stdio.h>
#include <stdlib.h>
#define RANGE 255


void countingSort(char a[], char b[], int n) // a = array, b = empty array, n = size
{
    int i;

    int c[RANGE +1];
    memset(c, 0, sizeof(c));


    for( i = 0; i< n; i++)
    {
        c[a[i]] = c[a[i]] + 1;
    }
    for(i = 1; i<RANGE; i++)
    {
        c[i] = c[i] + c[i-1];
    }
    for(i = n-1; i>=0; i--)
    {
        b[c[a[i]] - 1] = a[i];
        c[a[i]] = c[a[i]] - 1;
    }

}

int main()
{
    char a[10] = {'c','b','c','d','E','C','a','A','b','C'};
    int n = 10;
    char b[10];
    int i;
    for( i = 0; i<n;i++)
    {
        printf("%c",a[i]);
    }
    printf("\n");
    countingSort(a,b,n);
    for( i = 0; i<n;i++)
    {
        printf("%c",b[i]);
    }
    printf("\n");

    return 0;
}

我已经使用ASCII表对数组进行排序，并且我的输出是

ACCEabbccd

我设法按升序对数组进行排序，但是我不知道如何在A后面加上右号，依此类推。

Answer 1

您需要以某种方式知道您的A是大写字母，而a是小写字母。一种简单的方法是对其进行复制，然后将所有小写字符转换为大写字符（反之亦然），然后使用计数排序对副本进行排序。但是，在构建输出时，您需要查看原始数组并相应地放置正确的字符。

也不确定为什么要从n-1构造为0。需要从0构造为n。

void countingSort(char a[], char b[], int n) // a = array, b = empty array, n = size
{
    int i;

    int c[RANGE +1];
    memset(c, 0, sizeof(c));

    int cpy[n];
    for ( i = 0; i < n; i++ )
    {
      cpy[i] = a[i];
    }
    for ( i = 0; i < n; i++ )
    {
      if ( cpy[i] >= 97 && cpy[i] <= 122 )
      {
        cpy[i] = cpy[i] - 32;
      }
    }
    for( i = 0; i< n; i++)
    {
        c[cpy[i]] = c[cpy[i]] + 1;
    }
    for(i = 1; i<RANGE; i++)
    {
        c[i] = c[i] + c[i-1];
    }
    for(i = 0; i < n; i++ )
    {
        if ( a[i] >= 97 && a[i] <= 122 )
        {
          b[c[cpy[i]] - 1] = cpy[i] + 32;
        }
        else
        {
          b[c[cpy[i]] - 1] = cpy[i];
        }

        c[cpy[i]] = c[cpy[i]] - 1;
    }

}

[您可以在这里看到我复制了cpy的a，并将小写字母转换为大写字母，然后对cpy进行了排序。在构造时，我只是在a中查找以确定char是大写还是小写。