超排序——（桶排序 + 快排）

╰+哭是因爲堅強的太久メ 2022-07-12 11:41 169阅读 0赞

think:  
1题目名字叫做超排序，自己才疏学浅，依据查到的知识，阐述一下自己对超排序尚不成熟的想法，我们都知道快速排序速度快，但是遇到相同数据的时候不稳定，自己之前看到过一个数据时间复杂度那时可能达到O(N^2)，和之前的O(NlogN)差的挺大的，而桶排序是为数不多的时间复杂度达到O(N)的优秀算法，但是其对内存的要求可能就会比较高，快排和桶排排序都很优秀，但同样都存在这得失的条件，而将快排和桶排结合起来将会得到非常优秀的排序算法，这个题目只是初级的超排序题目，虽然下面代码中看上去基本和桶排序一样，但是其对数据的排序可以说是直接通过对题意的理解理解实现的，并没有很明显的其他排序算法的影子，但是去启迪我们可以考虑将其他的优秀排序算法例如快排结合起来，我在想是否可以通过一个结构体数组将快排与桶排结合起来，将桶排直接记录的数值直接作为数据域的一部分，例如(ans\[x\].Data++)的结构，可以深思考虑挖掘更深层次更多适合不同情况的实现方法

超排序  
Time Limit: 1000MS Memory Limit: 65536KB  
Problem Description

bLue 在跨年之际获得了一份小礼物，里面装了一串只包含大写字母和小写字母的字符串，如果你能帮 bLue 把这个字符串按照字典序排序（按 ASCII 码从小到大排序。大写字母的 ASCII 码小于小写字母的 ASCII 码），他会奖励你一个 Accepted。  
Input

输入数据有多组（数据组数不超过 50），到 EOF 结束。

对于每组数据，输入一行只包含大写字母和小写字母的字符串，且长度不超过 1000000。  
Output

对于每组数据，输出一行排序后的字符串。  
Example Input

HappyNewYear  
aaabAAbbBcdAB

Example Output

HNYaaeepprwy  
AAABBaaabbbcd

Hint

由于数据量较大，不推荐直接使用 cin, cout 输入输出。

另外，请确保最终结果是直接输出整个字符串，而非使用 printf(“%c”) 或 putchar() 等函数一个一个地输出字符，否则可能导致超时。  
Author  
「SDUT Round \#1 - Hello 2017 跨年大作战」bLue

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    char st1[1000004];
    int book[400];
    int main()
    {
        int i, j, t, x;
        while(scanf("%s", st1) != EOF)
        {
            t = 0;
            memset(book, 0, sizeof(book));
            int len = strlen(st1);
            for(i = 0; i < len; i++)
            {
                x = (int )st1[i];
                book[x]++;
            }
            for(i = 'A'; i <= 'Z'; i++)
            {
                for(j = 0; j < book[i]; j++)
                {
                    st1[t++] = i;
                }
            }
            for(i = 'a'; i <= 'z'; i++)
            {
                for(j = 0; j < book[i]; j++)
                {
                    st1[t++] = i;
                }
            }
            st1[t] = '\0';
            printf("%s\n", st1);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 264ms
    Take Memory: 1092KB
    Submit time: 2017-02-22 16:51:44
    ****************************************************/