I was in an interview a long time ago, and I was asked, can I write a bubble sort? To be honest, I had written much more complex processing logic before, but sadly I had no idea what bubbling sort was… I only know that if I sort some chaotic sequence, it will be done quickly, and the result is obvious, I was naked contempt… (even a performance of the worst bubbling sort thinking can not, why do you = =), the next day back, see what is sort, really beat the chest for a long time, the name is so nice, the original is this…
Simple sorting algorithm is basically the following several, which bubble sort, select sort, insert sort is the worst performance, the actual application of basic but also the simplest, can improve the confidence of your algorithm several small sorting methods.
.
Let’s implement it one by one if we want to order [1, 2, 32, 23, 321, 45, 8, 90, 227, 99] from small to large.
If we’re going to arrange them, the first thing we’re going to do is compare, put the big ones in the back and the small ones in the front, right? Compare them in pairs.
First take the first and second numbers, who is bigger than who, then the second and the third, or who is bigger than who, continue the third and fourth, fourth and fifth… After doing this, are you pretty sure that the last number is going to be the largest? And then there’s one less place in the chaotic sequence, right? I’m going to continue with the rest of the sequence and continue with the previous round. And if you think about the process, 12, 23, 34… Do you feel like there are waves of people coming out of a concert? Well, there’s no mistake, it’s a bubble, like a soft carpet, with a glass bead rolling inside, rolling the carpet is orderly. = = well, that’s bubble sort. So let’s see what it looks like in code.
The above is the simplest sort, the first instinct of a person can produce a solution to the problem. But? Thinking is certainly progressive, can not be stagnant all the time, why? Isn’t human wave sorting good? Well, bubble sort is not bad, is it? Simple and intuitive, but you know, some people’s brain circuits aren’t necessarily that intuitive, and they go something like this:
He said, “I’m going to swap every time I make a comparison, and I’m going to swap every time I make a comparison, and I’m going to swap every time I make a comparison,” right? Not a waste of time? Can I pick the largest number in this sequence and put it on the last edge?
The answer is yes. How? Since it’s a sequence, it’s an array, there’s a subscript, so I’m going to store the first one, and it’s going to keep going from the first one to the last one, and when someone has a larger value, they’re going to store their value, and then after a round, they’re going to get the maximum value, and then they’re going to put the number that they’ve picked, back to the last one. And then the second largest term is still the last term before this, until the whole sequence is complete. So this method of constantly picking the maximum number of remaining terms is called selection sort.
Let’s take a look at the code:
This kind of selection sort, although there is no exchange process, but there is more assignment process, is actually no better than bubbling, it is still the same, the theoretical performance can be slightly better so that it can be ignored.
With bubble and select the same period, there is an insert sort, insert sort way is more simple, you want to ask a question, if you have an empty array, then how would you sort? Would put first in the first empty array, take back the number of compare with the new array of the number of inserted into a two Numbers (only need to pay attention to behind you, small in front of you is OK), but, in fact, the newly created an array of spending is not small, there is no reason to a simple algorithm in this way, so it can be:
Pull out the second number, so it becomes the first half (your new array), and then the second half (your old big array), so you keep plugging your second half into the first half, and the first half of the big half moves back for the new one, right? Is it possible to achieve what you want? Let’s see how this insertion sort is implemented.
Do you want to have two for loops in your code that are completely iterated, step by step, right? One for each round of comparisons (where you’re just comparing a number, or determining where a number is in the array), and one for walking through the array, taking each member out for a walk. Right? That’s n ^ 2, which is O(n ^ 2).
Since there are predecessors groping, posterity stand these thinking is what kind of?
For example, when we’re talking about bubbling or insertion sort, do we notice the words “one by one”? Why move them one by one? Can you move it a long way? For example, if you sort an array from 1 to 100 (the original sequence is 100,99,98… 1), at this time 100 is the first digit, you have to move 99 times just to finish the number 100, you have to call the above swap method 99 times, but for example to move this number one by one into half and half, for example, the first number 100 is compared with 51 and then swapped with 99 and then compared with 52, isn’t that a very big step? And then when you do that, you change the interval to 25, and you take another step, although you might be wrong, right? It’s okay to make a step one correction at the end. And this is the famous Hill sort.
Let’s see how hill sort is implemented:
I’m going to compare them. I’m not going to move them. I’m going to take them out and divide them into groups. What’s the core sort point? You divide and conquer, divide and conquer. How? How to treat it? Why do I use this sort, this data gets sorted by this method? The core lies in the group – the group has only 2 members at most, for example, the length of the array is 8, divided into 4 2’s, 7 is divided into 3 2’s and 1 1’s, we can not see the order of many numbers, two can always be? Yes, that’s the point. So how do you treat it? Let’s take A look at the following let’s say I have now A and B have completed their internal sorting (they are both of length 4)
A B
1568, 2479,
Hand painting, don’t mind
Let’s see how it works:
At this point, another idea is born, which is also a kind of classification from the individual’s point of view. What does it look like? It’s kind of like gym class where the tall guys stand behind and the short guys stand in front, and the coach can’t tell who’s tall and who’s short at first glance, right? So many people, certainly is casually catch a, to take him as the benchmark, sort!! When you say the word, the little one stands in front of this guy, and the big one stands behind him, right? And that’s the core idea of quicksort. A bit like a dichotomy, but this dichotomy is a little different, it is not according to the length, it is according to the class, you work over there, short stood here, the whole is divided into two parts, the shorter the block also can’t points, that is, of course, the block just find another short, points again, this completes the internal process of a sort. (Small on the left and big on the right, so isn’t it ordered when the length is 3? Well, that’s the idea of quicksort.)
How to implement the specific code?
So it’s kind of intuitive to say, hey, let’s take two arrays, put tall and short, and concat back, right? Put the guy in the middle, of course. Don’t miss it. Take a look below:
Well, isn’t that intuitive? Left = [], right = []; left = []; right = []; Recursively, this is a very expensive memory, so we don’t do that, so how do we do that?
I didn’t recreate the array, but what? Through exchange, such as point of reference for the more than put on the left, less than the right, then I directly wait for a moment, a scan from the left, one from the right, when the scan is greater than the reference number on the number, the end of the scanning, on the right side of the scan, also when there is a number than reference for hours, ends scans, then put the two exchange, Student: Is it the realization that the small ones are in front and the big ones are behind, you say, but they’re not necessarily on both sides of the reference point? That’s right, keep scanning, and when I and J meet at a certain point, change the value of this reference point to the value of that position, so that one side is bigger and the other side is smaller. ,
Well, there is one, of course, there are countless times, and then the left piece continues to do the same thing, and so does the right, when the right and left plus the middle number is exactly 3 or less than 3, isn’t that OK?
There is also a very good performance of sorting, using a complete binary tree.
What does it think? God (uneducated I only know this sentence = =), not a sort, must make so many messy? Well, I don’t know, it’s an idea, but let’s not get too far into it and see how it works.
Heap, have big pile top with small top heaps, here don’t pull concept, the official to speak very well also very official = = in detail, simple to understand is a pyramid, you are wang, around you there are four major Kings to protect the eight king kong sixteen arhats, um so had been down, and the so-called big pile top is as you are living on the top of wang, small cap pile? On the contrary, the youngest of your gang is right there. Something like this:
This is what’s called the big top pile. Is it too common in life? (Please ignore the figure = =)
So how does it sort?
Remember how selection sort is sorted? You just pick a maximum number and keep plugging in to the end, right? But the process of choosing the largest number is achieved by constantly comparing and moving from place to place, so can we skip? Skip scanning. Actually, splitting into piles just makes sense.
Let’s see how the code works:
Here is a simple performance test to do
① Comparison of the speed of ordinary insert sort and quick sort (data volume: 200,000) :
It can be seen that in the sorting of 200,000 random numbers (0-10000), the quicksort takes less than 100 time units, while the insertion sort takes more than 50,000. Ordinary O(n ^ 2) performance is nothing compared to the best case O(n logn) fast sorting (the larger the data, the more obvious the results).
② Comparison between Hill sort and quicksort (data volume 20 million) :
Since both sorts are extremely unstable, hill sort performs slightly better than quicksort (javascript) in several tests.
Merge sort and Hill sort
Merge sort is at best and at worst nlogn, which is a stable and fast sorting algorithm, compared to the instability of hill and fast sorting. Using the complete binary tree mentality.
④ Heap sort and merge sort
It’s also 20 million random numbers between 1 and 10000.
conclusion
The way of thinking of human beings is constantly evolving. At the beginning, when we encounter problems, the solutions are similar to bubble sort, selection sort and insertion sort, which are simple, intuitive and easy to understand but inefficient. But as time goes on, we keep finding better alternatives, such as insertion sort, So if you can move one position at a time, why can’t you move a lot of positions at a time? Isn’t that more efficient? You said that every position may be moved sideways, for example, it may be moved a little bit bigger, it doesn’t matter ah, then continue to move again. That’s the idea of Hill sort. For the selection sort, in the same way, I want to choose one of the most large, through traditional location scan is the most simple and intuitive, but is too slow, I can direct pile, constant comparison binary number and the location of two grades of binary number, so jump to walk the whole cycle, you can get a lot of? If you look at quicksort, his idea is a little bit different, his idea is that if you have a sequence, you have to have a bunch of things that are bigger than a certain number and a bunch of things that are smaller than a certain number, and when you have a sequence that only has three numbers, it’s actually already sorted. Look at merge (or the idea of a complete binary tree), divide and conquer, no matter how long the sequence is, I can always break it up into groups of length 2 (or the last one left), I just have to make sure that all of these groups are sorted and merged.
This article comes from the cloud community partner “Programmers grow together”. For more information, you can pay attention to “Programmers grow together”.