MindMap Gallery Basic sorting algorithm
This is a mind map about basic sorting algorithms. The main contents are 1. Counting sort ⒉ Selection sort 3. Insertion sort 4. Score sorting 5. Minimum sum.
Edited at 2022-07-03 16:55:28Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Basic sorting algorithm
4. Ranking of results
Question: The exam is over, and what everyone is most concerned about is their own ranking. Now please help everyone rank. To simplify the question, the test subjects are only mathematics and Chinese.
Input and output description: Input: An integer n in the first line, representing the number of students. The next n lines have three numbers in each line, indicating a student's student number, math score, and Chinese score. Output: Sort these n students, first by total score from high to low, if the total scores are the same, then by math scores from high to low, if the math scores are also the same, sort by student number from small to large. (Because the total score is the same, the math score is the same, the Chinese score must be the same, 1<=n<=1000)
Example: enter: 4 1 95 97 2 100 96 3 98 96 4 99 95 Output: 2 196 100 96 4 194 99 95 3 194 98 96 1 192 95 97
Idea: Use function cmp to determine which student is in the front and which student is in the back. In fact, it is equivalent to a bubble sort.
Code demo: #include <bits/stdc .h> using namespace std; struct student //Contains the student's math scores, Chinese scores, total score and student number { int math; int chinese; int total; int id; }; student a[1010]; bool cmp(student x,student y) //Sort { if (x.total != y.total){ return x.total > y.total; } if (x.math != y.math){ return x.math > y.math; } return x.id < y.id; } int main() { int n; scanf("%d",&n); for (int i = 0;i < n;i ) { scanf("%d%d%d",&a[i].id,&a[i].math,&a[i].chinese); //Input a[i].total = a[i].math a[i].chinese; } for (int i = 0;i < n - 1;i) //Bubble sort { for (int j = 0;j < n - i - 1;j ) { if (cmp(a[j],a[j 1])) { swap(a[j],a[j 1]); } } } for (int i = n-1;i >= 0;i--) //output { printf("%d %d %d %d ",a[i].id,a[i].total,a[i].math,a[i].chinese); } return 0; }
5. Minimum sum
Question: Now there are n numbers from 0 to 9, and they need to be used to form two numbers. Both numbers cannot have leading 0s, so that the sum of the two numbers is the smallest.
Input and output description: Input: An integer n in the first line, indicating the number of numbers, and n numbers from 0 to 9 in the second line. Output: Output the minimum sum obtained. (2≤n≤16)
Example: enter: 4 3 0 2 1 Output: 33 Analysis: 10 23=33
Idea: Sort first, put the smallest number and the second smallest number together, then put 0, and finally put the remaining numbers. Insert the first number, then insert the second number, and repeat, so that you can get the minimum value.
Code demo: #include <bits/stdc .h> using namespace std; int a[20]; int main() { int n; scanf("%d",&n); for (int i = 0;i < n;i ) { scanf("%d",&a[i]); } for (int i = 0;i < n;i) //selection sort { int k = i; for (int j = i;j < n;j ) { if (a[j] < a[k]) { k = j; } } swap(a[i],a[k]); } if (a[0] == 0) //Replace the first number with a number that is not 0 { for (int i = 1;i<n;i) { if (a[i] > 0) { swap(a[i],a[0]); break; } } } if (a[1] == 0) //Replace the second number with a number that is not 0 { for (int i = 2;i < n;i ) { if (a[i] > 0) { swap(a[i],a[1]); break; } } } int num1 = 0, num2 = 0; //num1 is the value of the first number, num2 is the value of the second number for (int i = 0;i < n;i ) { if (i % 2 == 0)//When i is an even number, num1 is inserted into a[i] { num1 = num1 * 10 a[i]; } else //When i is an odd number, num1 is inserted into a[i] { num2 = num2 * 10 a[i]; } } printf("%d",num1 num2); //output return 0; }
3. Insertion sort
topic: Now please answer this question. Given an empty sequence, there are two ways to operate. 0 x: Indicates inserting a number with value x in the sequence 1 k: Ask what number is at the kth position in the sequence. The sequence remains sorted from small to large.
Input and output description: enter: The first line of input data is an integer m, which means there are m operations. Next m lines, the format of each line is "0 x" or "1 k", as described in the title. (m<=5000) Output: For each Q query, output the corresponding result. When Q asks, there must be a number in the sequence.
Example: enter: 5 0 2 0 1 1 2 0 0 1 1 Output: 2 0
Idea: It’s actually not difficult, just do what the question requires. If the first number is 0, insert it and add one to the length. The first number is 1. After sorting (it is recommended to use sort), just output the required number.
Code demo: #include <bits/stdc .h> using namespace std; const int N=5010; int a[N]; int main(){ int n,len=1; scanf("%d",&n); for (int i=1;i<=n;i) { int x; int k; scanf("%d%d",&x,&k);//Input if (x == 0)//Insert { a[len] = k; len ; } else//output { sort(a,a len 0); printf("%d ",a[k]); } } return 0; }
2.Select sort
topic: Sorting is the pre-processing part of many problems. In the previous question, the range of values was relatively small. By recording the number of times each value appeared, and then according to the value from small to large, the number of times the value appeared was output. This method is not suitable for situations where the numerical range is very large, because the array cannot be opened. You cannot create an array with a size of 100 million like A[100000000]. The total size of the array must be controlled within 30 million. In addition to counting sort, there are many sorting methods. Let's introduce a simple sorting algorithm, selection sort. The idea of selection sort is to get the number at each position from front to back. For the i-th position, among the positions [i 1, n], find a minimum value and record its position k. Swap the values of A[i] and A[k]. like: for(i=1;i<=n;i) {//Get the number at each position in turn k=i;//Assume that the number at this position does not move, which is the smallest one for(j=i 1;j<=n;j)//Find the position of the minimum value in the interval [i 1,n] if(A[j]<a[k])k=j; if(k!=i){//Exchange A[i] and A[k] t=A[i]; a[i]=A[k]; a[k]=t; } }
Input and output description: Input: An integer n in the first line, indicating the number to be sorted. The n elements in the second line represent the elements to be sorted. (1<=n<=1000) Output: Output n numbers, representing the sorted numbers.
Example: enter: 5 -1 2 1 4 3 Output: -1 1 2 3 4
Idea: Since the question has given us an example, we can refer to it. Notice! We have to keep enumerating until the sorting is completed, so we have to judge n * n times.
Code demo: #include <bits/stdc .h> using namespace std; const int N = 1010; int a[N]; int main() { int n; scanf("%d",&n); for (int i = 0;i < n;i ) { scanf("%d",&a[i]); } for (int i = 0;i < n-1;i)//Nested loop { for (int j = 0;j < n-1-i;j ) { if (a[j] > a[j 1]) swap(a[j],a[j 1]);//swap } } for (int i = 0;i < n;i ) { printf("%d ",a[i]); } return 0; }
1. Counting sort
Question: Input n numbers from 0 to 100 and output them from small to large.
Input and output description: Input: an integer n in the first line, no more than 100, and n integers from 0 to 100 in the second line. Output: Output an array, representing the sorted array.
Example: enter: 10 1 1 0 2 3 4 6 0 1 2 Output: 0 0 1 1 1 2 2 3 4 6
Idea: Very simple, everyone can use several methods: bucket sort, bubble sort, sort sort...
Code demonstration (sort sorting): #include <bits/stdc .h> using namespace std; int a[110]; int main() { int n; cin >> n; for (int i = 1;i <= n;i ) { cin >> a[i]; } sort(a,a n 1);//sort sorting for (int i = 1;i <= n;i ) { cout << a[i] << ' '; } return 0; }