c-使用计数排序按升序对字符数组进行排序

Question

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

输出：A A b b 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

一种方法只需将c[]大小加倍，并形成一个索引，其中所有偶数索引都是大写的，奇数索引都是小写的。

#if 1
#define RANGE (255*2 + 1)
#include <ctype.h>
#define CH_TO_INDEX(ch) 
(2*toupper((unsigned char)ch) + !!islower((unsigned char) ch))
#else
// Original
#define RANGE 255
#define CH_TO_INDEX(ch)    (ch)
#endif
void countingSort(char a[], char b[], int n) {
int i;
int c[RANGE + 1];
memset(c, 0, sizeof(c));
for (i = 0; i < n; i++) {
//c[a[i]] = c[a[i]] + 1;
c[CH_TO_INDEX(a[i])]++;
}
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];
b[c[CH_TO_INDEX(a[i])] - 1] = a[i];
// c[a[i]] = c[a[i]] - 1;
c[CH_TO_INDEX(a[i])]--;
}
}

输出

cbcdECaAbC
AabbCCccdE

---

可以具有不为c[]的两倍大小的更复杂的char --> index。这种映射倾向于假设只有字母A-Z。这种映射可以使用辅助映射阵列：

unsigned char map[256] - {
0, 1, 2, ...., 31, ' ', ... 'A', 'a', 'B', 'b', ... 'Z', 'z', 
ASCII characters after 'Z' and before 'a'
ASCII characters after 'z', .... 255 };

---

OP请求

Output : A a b b C C c c d e

但基于{'c', 'b', 'c', 'd', 'E', 'C', 'a', 'A', 'b', 'C'}，我认为OP想要

Output : A a b b C C c c d E

---

请注意，a[i] < 0时原始代码会失败。代码需要为负char重新工作。使用unsigned char重新编码。