c - 使用计数排序按升序对字符数组进行排序
问题描述
Input char a[10] = {'c','b','c','d','E','C','a','A','b','C'};
输出:A abb CC ccde
我得到了一个字符数组,我必须按升序对其进行排序,我必须使用计数排序来做到这一点
到目前为止我已经尝试过:
#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 之后放置一个等等。
解决方案
一种方法只是将大小加倍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
可以有一个更复杂char --> index
的,它的大小不会翻倍c[]
。这种映射倾向于假设只有字母 AZ。这样的映射可以使用辅助映射数组:
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
。
推荐阅读
- ruby-on-rails - 如果没有传入强参数,我如何更新当前模型中的参数?
- c# - 我应该如何在 C# 中命名支持属性?
- c# - c#将double转换为字符串问题
- django - 向表单添加了更多字段,但未显示更改
- javascript - 如何根据媒体查询更新样式组件的变量?
- ios - 如何从另一个类重新加载 ViewController?
- javascript - 我如何在 innerHTML 上使用 javascript 和 css 文件
- mysql - SQL 递归父子关系与 MySQL 5.5
- javascript - 如何处理使用 JQuery 提交的表单
- c# - 使用LINQ生成Highchart列表数据