字符排序算法

Question

输入:BDCAbaxz

输出:AaBbCDxz

我的解决方案是直截了当的丑陋:

1. 快速排序输入,然后我们得到"ABCDabxz"

2. 分配一个与原始数组大小相同的临时数组,然后从两个子数组中取适当的元素(ptr1 - > A,ptr2 ---> a)

3. 将temp数组复制回原始数组

任何更快的对这个问题的算法？

Answer 1

是.

为其定义一个比较器qsort,首先为您提供所需的排序(因此,不要将其AB...YZab...yz用作排序顺序,而是强制执行AaBb...YyZz).

Answer 2

如果输入很长（>> 255），您可以进行计数排序。

char chars[256]; zeroed
while( *input)  // zero termination
    chars[*input++]++;

并像这样提取它

int pos = 0;
for(int i = 'A'; i<= 'Z'; i++)
{
    while( chars[i]-- ) 
        output(pos++] = (char)i;
    while( chars[i+'a'-'A']-- )
        output(pos++] = (char)i+'a'-'A';
}

在）