Quicksort In-Place
原地快数排序
The previous version of Quicksort was easy to understand, but it was not optimal. It required copying the numbers into other arrays, which takes up space and time. To make things faster, one can create an “in-place” version of Quicksort, where the numbers are all sorted within the array itself.
前面那个版本的快速排序很容易理解，但却不是最佳的。它需要将数字拷贝到其他数组，这需要花费空间和时间。为了更快速，可以建立一个“原地”版本的快排，数字在数组内部实现排序。
Challenge （任务）
Create an in-place version of Quicksort. You need to follow Lomuto Partitioningmethod.
建立一个原地版本的快排，你需要采用Lomuto Partitioning的方法。
Guideline （指引）
Instead of copying the array into multiple sub-arrays, use indices to keep track of the different sub-arrays. You can pass the indices to a modified partition method. The partition method should partition the sub-array and then return the index location where the pivot gets placed, so you can then call partition on each side of the pivot.
- Always select the last element in the ‘sub-array’ as a pivot.
- Partition the left side and then the right side of the sub-array.
- Print out the whole array at the end of every partitioning method.
An array of length 1 or less will be considered sorted, and there is no need to sort or to print them.
Since you cannot just create new sub-arrays for the elements, partition method will need to use another trick to keep track of which elements are greater and which are lower than the pivot.
与原来将数组中的元素拷贝到几个子数组中不同，使用标记标识不同的子数组。你可以将标记传递给修改后的分区函数。分区函数需要分出子数组并返回基准的下标，然后你可以对基准两边继续调用分区操作。从始至终选择子数组中的最后一个元素为基准
- 先对左边的进行分区然后对右边的分区
- 每次分区后输出整个数组
长度小于等于1的数组认为是有序的，无需排序或打印
既然你不能另外新开子数组来存储元素，分区函数就需要另外一个技巧来标识哪些元素大于基准哪些元素小于基准。The In-place Trick （原地技巧）
If an element is lower than the pivot, you should swap it with a larger element on the left-side of the sub-array.
- Greater elements should remain where they are.
- At the end of the partitioning method, the pivot should be swapped with the first element of the right partition, consisting of all larger elements, of the sub-array.
- To ensure that you don’t swap a small element with another small element, use an index to keep track of the small elements that have already been swapped into their “place”.
- 如果元素小于基准，你需要将它与子数组左边的一个较大元素交换。
- 较大的元素维持原地不变
- 分区操作结束，基准需要与子数组中的右边分区（包含所有较大元素）的第一个元素交换
- 为了确保你不会交换两个较小的元素，使用一个标记标识所有已经通过交换放在正确位置的较小元素
Input Format （输入格式）
There will be two lines of input:
- n the size of the array
- ar the numbers of the array
两行 - 数组大小n
- 数组ar中的数
Output Format （输出格式）
Print the entire array on a new line at the end of every partitioning method.
每行打印每次分区结束后的整个数组Constraints （约束条件）
1<=n<=5000
-10000<=x<=10000
There are no duplicate numbers.
没有重复的数Sample Input（输入样例）
7
1 3 9 8 2 7 5
Sample Output（输出样例）
1 3 2 5 9 7 8
1 2 3 5 9 7 8
1 2 3 5 7 8 9
Explanation （解释）
5 is initally selected as the pivot, and the array is partitioned as shown in the diagram. The left side is partitioned next with 2 as the pivot. Finally, the right side is partitioned with 8 as the pivot. The entire array is now sorted.
5是最初的基准，数组分区如图所示。接下来左边以2为基准，最后，右边以8为基准。此时整个数组排序结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38int ar[5000]; int n;
void swap(int &a,int &b){
int t=a;
a=b;
b=t;
}
int partition(int *ar,int p,int r){
int x=ar[r];
int i=p-1;
for(int j=p;j<r;j++){
if (ar[j]<x){
i++;
swap(ar[i],ar[j]);
}
}
swap(ar[r],ar[++i]);
extern int n;
for(int i=0;i<n;++i){
cout<<ar[i]<<" ";
}
cout<<endl;
return i;
}
void quicksort(int *ar,int p,int r){
if (p<r){
int q=partition(ar,p,r);
quicksort(ar,p,q-1);
quicksort(ar,q+1,r);
}
}
int main() {
cin>>n;
for(int i=0;i<n;i++){
cin>>ar[i];
}
quicksort(ar,0,n-1);
return 0;
}
Quicksort 2 - Sorting
In the previous challenge, you wrote a partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number. This means you ‘sorted’ half the array with respect to the other half. Can you repeatedly use partition to sort an entire array?
在前面的任务里，你写了一个将数组分成两个子数组的分区函数，这两个子数组其中一个里的所有元素都小于一个给定的数，另一个则大于该数。这意味着相对于另一半，你“排序”了一半的数组。你能重复利用分区来排序整个数组吗？
Guideline （指引）
In Insertion Sort, you simply went through each element in order and inserted it into a sorted sub-array. In this challenge, you cannot focus on one element at a time, but instead must deal with whole sub-arrays, with a strategy known as “divide and conquer”.
When partition is called on an array, two parts of the array get ‘sorted’ with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.
Can you repeatedly call partition so that the entire array ends up sorted?
在插入排序中，你只需简单的地按序检查每一个元素然后将其插入到已排序的子数组中。在本次任务中，你不能仅仅每次只关注一个元素，相反地必须使用“分治”的策略来处理整个子数组。
当对一个数组进行分区操作时，数组的两部分对彼此来说已经“有序”了。如果对于每个子数组再进行分区操作，原数组将分成四部分。这个过程可以一直重复直到子数组变得很小。请注意这一点：当仅对其中的一个数进行分区操作时，这些数其实已经有序了。
你能重复调用分区函数使得最终整个数组有序吗？
Print Sub-Arrays （打印子数组）
In this challenge, print your array every time your partitioning method finishes, i.e. whenever two subarrays, along with the pivot, is merged together.
The first element in a sub-array should be used as a pivot.
Partition the left side before partitioning the right side.
The pivot should be placed between sub-arrays while merging them.
Array of length 1 or less will be considered sorted, and there is no need to sort or to print them.
在本次任务中，每次分区结束后打印你的数组。
子数组中的第一个元素作为基准。
先对左边的分区，再对后边的分区。
基准应在合并左右两个子数组时放与两者之间。
数组长度小于等于1的视为有序，不需排序或打印
Note （注意）
Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.
For example: Partition about the first element for the array A[]={5, 8, 1, 3, 7, 9, 2} will be {1, 3, 2, 5, 8, 7, 9}
当围绕基准元素分区时，请保持左右分区中元素原先的前后顺序。
例如：对数组A[]={5, 8, 1, 3, 7, 9, 2} 的第一个元素进行分区的结果该是{1, 3, 2, 5, 8, 7, 9}
Input Format （输入格式）
There will be two lines of input:
- n the size of the array
- ar the n numbers of the array
两行：
-数组大小n
-数组中的n个元素Output Format （输出格式）
Print every partitioned sub-array on a new line.
每次分区后的结果在新的一行输出Constraints （约束条件）
1<=n<1000
-1000<=x<=1000
Each number is unique.
Sample Input（输入样例）
7
5 8 1 3 7 9 2
Sample Output（输出样例）
2 3
1 2 3
7 8 9
1 2 3 5 7 8 9
Explanation （解释）
This is a diagram of Quicksort operating on the sample array:
下面是样例的一个快排示意图
Task （任务）
The method quickSort takes in a parameter, ar, an unsorted array. Use the Quicksort algorithm to sort the entire array.
函数quickSort有一个未排序的数组ar作参数。使用快排算法对数组排序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47int partition(vector <int> &arr,int p,int r){
vector <int> left,right;
int x=arr[p];
for (int j=p+1;j<=r;j++){
if (arr[j]<x){
left.push_back(arr[j]);
}else{
right.push_back(arr[j]);
}
}
for(int i=0;i<left.size();i++){
arr[i+p]=left[i];
}
int q=p+left.size();
arr[q]=x;
for(int i=0;i<right.size();i++){
arr[i+q+1]=right[i];
}
return q;
}
void quickSort(vector <int> &arr,int p,int r) {
if (p<r){
int q=partition(arr,p,r);
quickSort(arr,p,q-1);
quickSort(arr,q+1,r);
//print sub-array
for(int i=p;i<=r;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
int main()
{
int n;
cin >> n;
vector <int> arr(n);
for(int i = 0; i < (int)n; ++i) {
cin >> arr[i];
}
quickSort(arr,0,n-1);
return 0;
}
总结：
分成left,right,equal三部分会很清楚，但实际排序时没必要建立left,right数组，完全可以实现就地(in-place)排序,否则如上面的代码显示的一个浪费O(n)的空间，另外还要额外合并的时间(merge),而就地排序这两个问题都可以解决
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
void swap(int &a,int &b){
int t=a;
a=b;
b=t;
}
int partition(vector <int> &arr,int p,int r){
int x=arr[p];
int i=p;
for (int j=p+1;j<=r;j++){
if (arr[j]<x){
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[p],arr[i]);
return i;
}
void quickSort(vector <int> &arr,int p,int r) {
if (p<r){
int q=partition(arr,p,r);
quickSort(arr,p,q-1);
quickSort(arr,q+1,r);
}
}
int main()
{
int n;
cin >> n;
vector <int> arr(n);
for(int i = 0; i < (int)n; ++i) {
cin >> arr[i];
}
quickSort(arr,0,n-1);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
Quicksort 1 - Partition
The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with an average case performance of O(n^2). In these next few challenges, we’re covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort).
在前面的任务中提及的插入排序，是一种很简单直观的排序算法，其平均算法复杂度为O(n^2).在接下来的一些任务中，我们将涉及到一种分治的算法成为快速排序（又称分区排序）。
Step 1: Divide （第一步：分解）
Choose some pivot element, p, and partition your unsorted array,ar , into three smaller arrays:left ,right , and equal, where each element in left<p, each element in right>p, and each element in equal=p.
选择某个基准元素p，然后将你待排序的数组ar分成三个小的数组left，right，equal，所有其中的元素满足：left<p,right>p,equal=p
Challenge (任务)
Given ar and p=ar[0] , partition ar into left,right , and equal using the Divide instructions above. Then print each element in left followed by each element in equal, followed by each element in right on a single line. Your output should be space-separated.
Note: There is no need to sort the elements in-place; you can create two lists and stitch them together at the end.
给你数组ar和p=ar[0],使用上面的分解指令将ar分成left，right，equal。然后依次打印left，equal，right中的元素，用空格隔开。
Input Format（输入格式）
The first line contains n (the size of ar).
The second line contains n space-separated integers describing ar (the unsorted array). The first integer (corresponding to ar[0]) is your pivot element,p.
第一行为n
第二行为n个空格隔开的ar中的整数，p=ar[0]
Constraints（约束条件）
- 1<=n<=1000
- -1000<=x<=1000,x in ar
All elements will be unique.
Multiple answer can exists for the given test case. Print any one of them.
所有元素唯一，答案不唯一，可以打印其中任何一个Output Format（输出格式）
On a single line, print the partitioned numbers (i.e.: the elements in left, then the elements in equal, and then the elements in right). Each integer should be separated by a single space.
一行，输出分区后的数字
Sample Input（输入样例）
5
4 5 3 7 2
Sample Output（输出样例）
3 2 4 5 7
Explanation（解释）
ar=[4,5,3,7,2]
Pivot: p=ar[0]=4.
left={};equal{4} ;right={}
ar[1]=5>=p, so it’s added to right.
left={};equal{4} ;right={5}
ar[2]=3<=p, so it’s added toleft.
left={3};equal{4} ;right={5}
ar[3]=7>=p, so it’s added to right.
left={3};equal{4} ;right={5,7}
ar[4]=2<=p, so it’s added to left.
left={3,2};equal{4} ;right={5,7}
We then print the elements of left, followed by equal, followed by right, we get: 3 2 4 5 7.
This example is only one correct answer based on the implementation shown, but it is not the only correct answer (e.g.: another valid solution would be 2 3 4 5 7).
这只是其中一个正确的答案（答案还可能是2 3 4 5 7）
1 | void partition(vector <int> ar) { |
The Full Counting Sort
完整的计数排序
In this challenge you need to print the data that accompanies each integer in a list. In addition, if two strings have the same integers, you need to print the strings in their original order. Hence, your sorting algorithm should be stable, i.e. the original order should be maintained for equal elements.
Insertion Sort and the simple version of Quicksort were stable, but the faster in-place version of Quicksort was not (since it scrambled around elements while sorting).
In cases where you care about the original order, it is important to use a stable sorting algorithm. In this challenge, you will use counting sort to sort a list while keeping the order of the strings (with the accompanying integer) preserved.
在本次任务中你将列表中与整数相关的数据。另外，如果两个字符串对应的整数相同，那么你需要按原来字符串出现的顺序打印它们。因此，你的排序算法必须是稳定的。意即，对于相同的元素必须维持其原来的先后顺序。
Challenge （任务）
In the previous challenge, you created a “helper array” that contains information about the starting position of each element in a sorted array. Can you use this array to help you create a sorted array of the original list?
Hint: You can go through the original array to access the strings. You can then use your helper array to help determine where to place those strings in the sorted array. Be careful about being one off.
Details and a Twist
You will be given a list that contains both integers and strings. Can you print the strings in order of their accompanying integers? If the integers for two strings are equal, ensure that they are print in the order they appeared in the original list.
The Twist - Your clients just called with an update. They don’t want you to print the first half of the original array. Instead, they want you to print a dash for any element from the first half.
在上一任务中，你创建了一个辅助数组，其中包含排序后数组中每个元素的起始位置信息。你能否利用此数组获得原列表的排序后的数组呢？
提示：你可以遍历原数组来访问获取字符串。你可以利用你的辅助数组来帮助你确定将字符串放到排序后的数组中的具体位置。注意记得减1.
细节和Twist：
给你一个包含整数和字符串的列表。你能按照整数的排序顺序打印出对应的字符串吗？如果两个整数一样，那么按照原来列表中出现的顺序打印。
Twist：你的客户刚刚电话要求更新要求。他们不希望你打印原列表的前半部分。相反的，他们希望你将前半部分的任何一个元素用破折号“-”替换。
Input Format （输入格式）
- n, the size of the list ar.
- n lines follow, each containing an integer x and a string s.
- 列表大小n
- 接下来n行，每行包含一个整数x和一个字符串s
Output Format （输出格式）
Print the strings in their correct order.
按正确的顺序打印字符串Constraints （约束条件）
100<=n<=10^6
0<=x<100
n is even
1<=length(s) <=10
n是偶数
The characters in every string in lowercase.
字符串中所有字符为小写
Sample Input(输入样例)
20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
Sample Output（输出样例）
1 | - - - - - to be or not to be - that is the question - - - - |
Explanation （解释）
Below is the list in the correct order. The strings of each number were printed above for the second half of the array. Elements from the first half of the original array were replaced with dashes.
下面是正确的排序。
0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh
1 | int c[100],a[1000001]; |
Counting Sort 3 (计数排序 3)
In the previous challenge, it was easy to print all the integers in order, since you did not have to access the original list. Once you had obtained the frequencies of all the integers, you could simply print each integer in order the correct number of times. However, if there is other data associated with an element, you will have to access the original element itself.
In the final counting sort challenge, you are required to print the data associated with each integer. This means, you will go through the original array to get the data, and then use some “helper arrays” to determine where to place everything in a sorted array.
If you know the frequencies of each element, you know how many times to place it, but which index will you start placing it from? It will be helpful to create a helper array for the “starting values” of each element.
在前面的任务里，将列表中的整数按序输出是很简单的，因为你不需要访问原列表。一旦你获得了所有整数的出现频率，你就可以简单地按序打印每个整数的次数。但是，如果有其他数据跟每个元素有关联，那么你就必须访问原来的元素本身了。
在最后这个任务里，你被要求打印与整数关联的数据。这意味着你需要回到原列表取获取数据，并且使用一些“辅助数组”来确定在哪里将所有数据按序存放。
如果你知道每个元素的出现频率，你知道这样的元素需要存储多少次，但是，从哪个位置开始存储呢？所以在这里建立一个辅助数组储存每个元素的“起始位置”将会非常有帮助。
Challenge （任务）
You will be given a list that contains both integers and strings. In this challenge you just care about the integers. For every value i from 0 to 99, can you output L, the number of elements that are less than or equal to i?
给你一个列表，包含整数和字符串。本任务你只需关注整数。对于每个整数i，能否输出小于等于i的数的个数L？
Input Format （输入格式）
- n, the size of the list ar.
- n lines follow, each containing an integer x and a string s.
- 列表大小n
- 接下来n行，每行一个整数x和一个字符串s
Output Format （输出格式）
Output L for all numbers from 0 to 99 (inclusive).
输出0～99这些数的LConstraints （约束条件）
100<=n<=10^6
0<=x<100
length of string<=10
Sample Input（样例输入）
10
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
Sample Output（样例输出）
1 3 5 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
Explanation （解释）
0 appears 1 time, so the 0th number is 1.
0 and 1 combined appear 3 times, so the next number is 3.
This continues for the rest of the list, until no more new numbers appear.
0出现1次，所以小于等于1的有1个，0和1共出现3次，所以小于等于2的有3个…
1 |
|
总结
同样基于后续任务及题目中提及的辅助数组概念，将程序调整如下，生成辅助数组L然后输出1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int a[100],L[100];
int main() {
int n;
cin>>n;
for(int i=0,val;i<n;i++){
string str;
cin>>val>>str;
a[val]++;
}
int s=0;
for(int val=0;val<100;val++){
s+=a[val];
L[val]=s;
cout<<s<<" ";
}
return 0;
}
Counting Sort 1
Comparison Sorting
Quicksort usually has a running time of n*log(n) , but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n×log(n) (worst-case) running time, since n×log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).
Alternative Sorting
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.
Challenge
Given a list of integers, can you count and output the number of times each value appears?
Hint: There is no need to sort the data, you just need to count it.
Input Format
There will be two lines of input:
- the size of the list
- space-separated numbers that make up the list
Output Format
Output the number of times every number from to (inclusive) appears on the list.
Constraints
100<=n<=10^6
0<=x<100 (x is integer)
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
0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2
Explanation
The output states that 0 appears 0 times, 1 appears 2 times, 2 appears 0 times, and so on in the given input array.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 i=0;i<100;i++){
cout<<a[i]<<" ";
}
return 0;
}
计数排序 1
比较排序
Quicksort usually has a running time of , but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n×log(n)(worst-case) running time, since represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).
快速排序运行时间为n×log(n),有没有再快一点的排序算法呢？通常来说是不可能的。大多数的排序算法属于比较型排序，意即，通过元素间两两比较来实现一组数的排序。比较排序的运行时间（最坏情况）无法比n×log(n)更快，因为 n×log(n) 是确定一组数中每个数最终排序位置的最小比较次数。具体细节可以参看这些笔记
其他排序
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.
但是，对于某些特定输入，使用非比较的排序算法可能更为有效。这有可能实现线性时间内的排序。接下来的任务将涉及计数排序，一种当所有元素的取值都比较小，如处于一个较小的数据范围内的整数时的快速的排序方法。我们先来完成一个简单的任务：计数。
任务
Given a list of integers, can you count and output the number of times each value appears?
Hint: There is no need to sort the data, you just need to count it.
给你一组整数，你能统计并输出每个数出现的次数吗？
提示：没必要对数据排序，你仅需要做统计
输入格式
There will be two lines of input:
- the size of the list
- space-separated numbers that make up the list
Output Format
Output the number of times every number from to (inclusive) appears on the list.
输入有两行：
-这组数的个数n
-以空格隔开的这组数约束
100<=n<=10^6
0<=x<100 (x为整数)
输入样例
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
输出样例
0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2
解释
The output states that 0 appears 0 times, 1 appears 2 times, 2 appears 0 times, and so on in the given input array.
输出显示0出现0次，1出现2次，2出现0次，…
1 |
|
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.
在输出里你空间所有数字以升序输出，并且多次出现的数字也相应地打印出来了。
1 |
|
总结
到这里本任务其实已经算完成了，但是为了与后面环节关联，我们可以将任务稍作修改：最后不仅仅是输出排序后的结果，而是先将排序后的数存储在一个新的列表b中,再输出。
那么我们需要对程序稍作调整：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}