2016-06-17

Counting Sort 2 (计数排序 2)

Often, when a list is sorted, the elements being sorted are just keys to other values. For example, if you are sorting files by their size, the sizes need to stay connected to their respective files. You cannot just take the size numbers and output them in order, you need to output all the required file information.

However, if you are not concerned about any other information, then you can simply sort those numbers alone. This makes counting sort very simple. If you already counted the values in the list, you don’t need to access the original list again. This challenge involves a simple counting sort where the elements being sorted are all that matter.
通常，当一个列表被排序时，被排序的元素只是其他值的键。例如，当你基于文件大小对文件排序时，文件大小需要与文件关联在一起。你不能仅仅取文件大小然后按顺序输出，你需要输出所有的文件信息。

但是，如果你并不关心其他信息，那么你可以只是简单地对这些数字排序。这会使得计数排序变得非常简单。如果你已经对列表计数，你无需访问原列表。下面的任务是就是这种情况下的一个简单的计数排序。

Challenge（任务）

Given an unsorted list of integers, output the integers in order.

Hint: You can use your previous code that counted the items to print out the actual values in order.
给你一个未排序的整数列表，输出排序后的列表
提示：你可以使用前面的代码来输出排序后的实际数字

Input Format（输入格式）

There will be two lines of input:

the size of the list
space separated numbers that belong to the list
两行：
列表大小
列表中的整数以空格隔开
Output Format （输出格式）
Output all the numbers of the list in order.
输出排序后的列表
Constraints （约束条件）
100<=n<=10^6
0<=x<100

Sample Input（输入样例）

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

Sample Output（输出样例）

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

Explanation（解释）

In the output you can see the numbers sorted in ascending order. You can also see that numbers appearing multiple times are printed accordingly.
在输出里你空间所有数字以升序输出，并且多次出现的数字也相应地打印出来了。

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int a[100];
int main() {
    int n,val;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>val;
        a[val]++;
    }
    for(int val=0;val<100;val++){
        while (a[val]>0){
            cout<<val<<" ";
            a[val]--;
        }        
    }
    return 0;
}

总结

到这里本任务其实已经算完成了，但是为了与后面环节关联，我们可以将任务稍作修改：最后不仅仅是输出排序后的结果，而是先将排序后的数存储在一个新的列表b中,再输出。

那么我们需要对程序稍作调整：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int a[100],b[1000000];
int main() {
    int n,val;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>val;
        a[val]++;
    }
    for(int val=0,i=0;val<100;val++){
        while (a[val]>0){
            b[i]=val;            
            a[val]--;
            i++;
        }        
    }
    for(int i=0;i<n;i++){
        cout<<b[i]<<" ";
    }
    return 0;
}

Challenge（任务）

Input Format（输入格式）

Output Format （输出格式）

Constraints （约束条件）

Sample Input（输入样例）

Sample Output（输出样例）

Explanation（解释）

总结