In the second part, let's write some wonderful sorting operations.

1, Bucket sorting

When we sort a string of numbers, what method should we use? There are many kinds, bubble sort, bucket sort, quick sort, sort The first one is to introduce bucket sorting.

What is bucket sorting?

We now have six numbers 6 5 7 9 1 4. We're going to sort him? What can I do?

First of all, we found that our numbers are within ten, just like a person holding six cards. Then there are ten empty barrels in front of us. It is marked with 1-10 in order. Next, we put each card into the corresponding empty bucket, and then walk back from 1. If there are cards in the bucket, we will take them out and put them on the top of the previous card. Finally, the cards in our hands are arranged in order. This is the simple idea of simplified bucket sorting. Does it feel very simple? That is, the items are put into the container, and then the container is marked in order. When we take out the items in the order of the container, it is naturally arranged in order.

Think about it. I'm going to post code.

#include<stdio.h>
#include<string. h> / / initialize the header file to be added to the array

int main()
{
	int a[1001];
	memset(a,0,sizeof(a));/*When writing bucket sorting, if you define the array in main, don't forget to initialize.
If it is defined outside the main function, it is a global variable array, which does not need to be initialized. It has automatically defaulted to the value of the array as 0*/
	int n,m;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&m);
		a[m]++;
	}for(int i=0;i<=1000;i++){
		for(int j=1;j<=a[i];j++){
			printf("%d ",i);//Output the bucket number in sequence
		}
	}return 0;
} 

The time complexity of bucket sorting is O(M+N). This m is the number of arrays, and this N is the maximum value in the 1-array. But ha, bucket sorting can only complete sorting, but it can not exchange all information between two locations.  

2, Bubble sorting

So is there any defect in the sorting of the above bucket, otherwise our bubble sorting has no room to appear, isn't it. Of course, bucket sorting is really a waste of space. Hey? You ask why.

Then take a chestnut, you see. If our array is 2 5 7 6 4 8, it's OK. If it's 1 5456456456456156756456 21 54 5 4 6, does our bucket number need to be large, and does our array also need to be large? Does it cost too much space, and does it become a paragraph error without paying attention? Then the next step is our most classic bubble sorting.

How is bubble sorting implemented? Bubble sorting, in my opinion, is like a small fish spitting bubbles. The numbers to be sorted are exchanged one by one. Take it up and go up. We start with the first number and go back. If we sort from small to large, we need to change his position and comparison conditions. For example, 1 5 6 4 7 8, if you want to sort from small to large, 1 will be compared in turn. When you find that the following number is smaller than him, you will exchange. Obviously, 1 does not need to exchange, so go down, 5, look back, look for 6 first, do not need to exchange, and then go back. When you find 4, you need to exchange with 4, and then go back, If you find that you don't need to exchange, you go back to the previous position and find 6. Repeat the method of finding the position in 5 above, and so on, you can arrange 6. If the numbers are in a row, do you exchange positions like bubbles spit out by a small fish? Bubble sorting, every time you find the final position of a number, you can finally put all the numbers in the order they should be placed.

Next, code implementation.

#include<stdio.h>

int a[100000]
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}for(int i=1;i<=n-1;i++){
		for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1]){/*In this way, the order is from small to large. If the previous one is larger than the latter one, proceed
 Exchange.*/
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;//The two data are exchanged
			}
		}
	}for(int i=1;i<=n;i++){
		scanf("%d",a[i]);
	}return 0; 
}

This is a simple array to sort. What if you add something else? Do strings or other data need to be exchanged with the data that should be sorted? It's very simple. We store the things to be sorted directly into the structure.

#include<stdio.h>
struct student{
	char name[100];
	int score;
}a[100];

int main()
{
	int n;
	scanf("%d",&n);
	student temp; 
	for(int i=1;i<=n;i++){
		scanf("%s %d",&a[i].name,&a[i].score);
	}for(int i=1;i<=n-1;i++){
		for(int j=1;j<=n-i;j++){
			if(a[j].score>a[j+1].score){
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}for(int i=1;i<=n;i++){
		printf("%s ",a[i].name);
	}return 0;
}

In this way, we can exchange the marked things with the data we sort. However, the time complexity of bubble sorting is O(n*n), which is still very high, but it can solve the small problems of exchanging with constants and wasting space that bucket sorting cannot achieve. However, so slow, is there a faster sort? It must be, yes.

3, Quick sort

I don't know how our teachers teach. Will they tell you: "you don't need to learn quick sorting. Just use a sort. A line of code can solve the problem." Little fish wants to tell you here: "No!" More is better. Sort is really fast, but sometimes it may be better to use quick sorting?

We can see the time complexity of the first two algorithms. Bucket sorting is O(M+N) and bubble sorting is O(N*N). What about quick sorting? His time complexity is O(NlogN); This can basically be regarded as the time complexity of linear O(N).

Quick sorting is actually quite easy to understand.

First, let's find an array 6 5 4 9 1 5 3 4 7 8. This is an array I input casually, with a total of 10 numbers. Then we need to sort it. We can't sort it with buckets, bubble or sort. (what I said earlier seems to be nonsense) emmmm, let's talk about how to sort quickly.

We can select a number in this array. For convenience, we choose the first array 6 as our special number, and then find a position k in the back. This position is also a special position. All the numbers on the left of k should be less than our special number, and the numbers on the right of 6 should be greater than 6. So how to find this position? Find two variables i and j, one from the beginning, one from the back, and j from the last number. What is j looking for? J is looking for the number that does not conform to the special position we mentioned above, that is, looking for the number that is less than the special number. It may be a little around, but it doesn't matter. Think more here. After reading here, you can understand the following. Then we can draw a conclusion by analogy with J that i is looking for a number greater than a special number. If it is not found (for i, J), i moves back and j moves forward. If found, exchange the two numbers found by i and J. If i and j reach the same number at this time, then this position is our special position k, and we can change the special position to our special number.

The course of change is as follows:

6 5 4 9 1 5 3 4 7 8

6 5 4 4 1 5 3 9 7 8

3 5 4 4 1 5 6 9 7 8.

This is the change process of 6. Then repeat the change of 6 on the left and right of 6 as a small exercise. This is for you to complete. (I saw a giant say that this idea is based on dichotomy, which can be understood by interested students)

The next step is the code implementation. (I still suggest to manually simulate the process, which can be understood more clearly and is also very interesting)

#include<stdio.h>
int a[1000],n;

void quicksort(int left,int right)
{
	int i,j,t,temp;
	if(left>right){
		return ;
	}temp=a[left];
	i=left;
	j=right;
	while(i!=j){
		while(a[j]>=temp&&i<j){
			j--;
		}while(a[i]<=temp&&i<j){
			i++;
		}if(i<j){
			t=a[j];
			a[j]=a[i];
			a[i]=t;
		}
	}a[left]=a[i];
	a[i]=temp;
	quicksort(left,i-1);
	quicksort(i+1,right);
} 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
	}quicksort(1,n);
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

In this way, in fact, the sorting algorithm is wonderful and interesting! Ah, I almost forgot there was a sort

4, sort

To tell you the truth, sort sorting is actually very common. Why do you say so, because it is simple. Just one line. You can realize the functions realized by the above pile of code.  

#include<iostream>
#include<algorithm>
using namespace std;
int a[110000];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}sort(a+1,a+n+1);//If your array starts with 1 like me, use this. If not, use it
sort(a,a+n);
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}return 0;
}

Now that we've talked about it, let's add a sort structure.

#include<iostream>
#include<algorithm>
using namespace std;
struct student{
	int x,y;
}a[110000];
bool cmp(student a,student b){
	return a.x>b.x;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a[i].x,&a[i].y);
	}sort(a+1,a+n+1,cmp);//In fact, just look at the bool above
	for(int i=1;i<=n;i++){
		printf("%d %d\n",a[i].x,a[i].y);
	}return 0;
}

Maybe that's all. I didn't expect that I wrote a summary from yesterday to today. Then it's still that sentence. You're welcome to give guidance and suggestions! See you next