Pay attention to forwarding, pay attention to the public account: the way to advance JAVA architecture, reply to Ali to get interview information
Many times, listening to others discussing quick sorting, selection sorting, bubbling sorting, etc., I think it s very awesome. I think, damn, there are so many sorts of sorts, and I think others are very awesome, but it s not true. After I went to understand and study, I found that it is not as difficult as I imagined. Today, I will summarize the implementation principles of various sorts and implement them.
1. An overview of article writing style
Selection sort, insertion sort, bubble sort, merge sort, quick sort, hill sort, heap sort,
Finally, compare various sorting algorithms to clarify the advantages and disadvantages of various sorts.
Among them, quick sort is an enhancement of bubble sort, heap sort is an enhancement of selection sort, and Hill sort is an enhancement of insertion sort. There are six types, and the last one is merge sort.
2. select sort
Selective sorting is the simplest kind of sorting in my opinion, because we can easily think of this method to sort arrays. The principle is very simple.
The schematic diagram is as shown above: first compare the number in the first place value with the numbers in all subsequent positions in turn, if the number in the first position is greater than the number in the second position, exchange it. Then continue to compare the number in the first position with the number in the third position. After a round of comparison, the number in the first position is the smallest of all numbers, and then the second position The upper number is compared with the numbers in all subsequent positions. The same rule is that after the second round of comparison, the second place is the second smallest number among all numbers, and the numbers are compared in turn until the last position ends. Sorting in this way is called selective sorting.
3. insertion sort
Simple, given a set of records, divide it into two sequence groups, one is an ordered sequence (from small to large or from large to small in order), and the other is an unordered sequence. Initially, the first sequence in the record A number is regarded as a data in an ordered sequence group, and all other numbers are regarded as data in an unordered sequence group. Then compare the data in the disordered sequence group (that is, starting from the second data in the record) with the records in the ordered sequence, and then insert it into the appropriate position in the ordered sequence group, until the disordered sequence The last data in the group is inserted into the ordered sequence group.
Very interesting video, fun dance for insertion sort: v.youku.com/v_show/id_X...
4. bubble sort
Bubble sorting is as simple as selection sorting. It is easy to understand. The whole process will rise like bubbles. Assuming sorting from small to large, for a given n records, start from the first record and start with two adjacent records For comparison, when the current record is larger than the following record, switch positions. After a round of comparison, the nth position is the largest number in the entire record, and then perform the second round of comparison on the first n-1 records, repeat The process continues until only one record remains for comparison.
Bubble sort: v.youku.com/v_show/id_X...
5. merge sort
There are two ways to implement merge sort, one is non-recursive, the other is recursive, but I think if you understand the implementation of non-recursive, then you know the principle of merge sort, and recursive is also very simple .
What is merge sort? (We are talking about 2-way merge sort)
One picture can understand what is called 2-way merge sort
Initially, each element in an array is regarded as an ordered sequence (the length of the array is n), and then two adjacent ordered sequences are merged into an ordered sequence. The first merge can get n/2 lengths For an ordered sequence of 2 (the length of the last ordered sequence may be 1, or it may not, the key depends on the number of elements in the array), in pairwise merging, n/4 ordered sequences of length 4 are obtained Sequence (the length of the last one may be less than 4)... Keep merging like this until you get an ordered sequence 1 of length n
Simply put, by solving three problems in three steps, you can write a merge sort
1. Solve the problem of merging two adjacent ordered sequences into one ordered sequence. It is very simple. Add an array (the length is the same as the array to be arranged).
The core operation of two-way merging may destroy the original ordered sequence during the merging process. Therefore, store the merged result in another array, and set two adjacent ordered sequences as r[s] ~ r[m] and r[m+1]~r[t], merge these two ordered sequences into one ordered sequence, r1[s]~r1[t], set three parameters i, j, k . i and j respectively point to the first record of the two ordered sequences, that is, i=s, j=m+1, and k points to the location where the merged result is stored (that is, where to put the merged result in r1) k= s. Then, compare the number of records pointed to by i and j, take the smaller one as the merged result and store it in the position pointed by k, and then move the point of the smaller one back until all records in one of the two ordered sequences are After fetching, send the remaining records of another ordered sequence to the merged ordered sequence (that is, put it in r1)
2. How to complete a merger?
Here we need to divide the situation, three situations,
Suppose the number of elements in each ordered sequence is h (h=1 for the first merge), i=0, starting from the first element. When merging takes two ordered sequences each time, the span is 2h, and the problem comes. As long as you know how many of these two ordered sequences are in an array of length n (n is the maximum subscript value of the array), then You can perform different operations.
The first case: (i+2*h-1) <= n//For example, when i=0 and h=1, (i+2*h-1) means pointing to the first two The subscript value of the last position of the sequence sequence, use it to compare with n (n is the largest subscript value of the array), if it is less than n, then there are other numbers behind, if it is equal to n, it means it is the end. The entire array is exactly two ordered sequences, and there will be no extra numbers. Then perform a merge, merge the two ordered sequences, and then add 2h to i. If this condition is still met, continue to merge, if not, judge other situations.
The second case: (i+h-1) <n//It means that there are two ordered sequences at the end, but the length of the last ordered sequence is not h, and they are also merged
The third case: (i+h-1) >= n//It means that only the last ordered sequence is left, and the ordered sequence is directly sent to the corresponding position of r1.
3. Complete the entire merge sort
We have solved two problems earlier, one is how to merge two ordered sequences, and the other is how to judge the completion of a merge process. Now we need to solve how to control the end of the two-way merger? That is, how many times need to be merged.
When the step size is equal to n or greater than n, it means that there is only one ordered sequence left, and the merging is over.
6. quick sort
Quick sorting is an enhancement of bubble sorting. The point of enhancement is that: in bubble sorting, the comparison and movement of records are carried out in two adjacent positions, and records can only be moved back by one position per exchange, so the total number of comparisons And the number of moves is large, and the comparison and movement of the quick row records are carried out from both ends to the middle. The larger record can be moved from the front to the back at one time, and the smaller record can be moved from the back to the front at one time. It reduces the number of comparisons and the number of moves
Quick sort principle: select an axis value (comparison benchmark), divide the records to be sorted into two independent parts, the records on the left are all less than or equal to the axis value, and the records on the right are greater than or equal to the axis value, and then respectively Repeat the previous process for the left part and the right part, that is, select an axis value on the left part and divide it into two independent parts, which uses recursion. At the end, the entire sequence becomes orderly.
Question: How to choose the axis value? How to turn the sequence into left and right parts?
There are three options for the axis value:
1. Select the record at the first position of the sequence
2. Select the record at the middle position of the sequence
3. Compare the records at the first position, the middle position and the end position of the sequence, and select the record with the middle size.
How to divide the sequence into left and right parts?
Look at the execution process of the picture. When a trip is compared, the left and right sides of the axis value are arranged. Two parameters, first and end, are used. One starts from the starting point and the other starts from the end. When the two are equal When, it traverses all the records in the sequence. The first comparison times are the same as the first comparison times of the selection sort, but then it starts to be different, because the element on the left side of the axis value is There is no need to compare with the elements on the right side of the axis value, and the selection order is still compared with all.
Quick sort: v.youku.com/v_show/id_X...
7. Hill sort
Hill sorting is actually an upgraded version of insertion sorting. Essentially, it is also inserting sorting operations. However, Hill sorting does not regard a group of records as a whole, but divides the entire record into several groups of records, and then compares each Insertion sort of group records,
The grouping rules are as follows: Suppose there are 1 2 3 4 5 6 7 8 9 10 ten positions (a number will be placed in each position, the number is ignored here, only the position is discussed). (The insertion sort operation is omitted, only how to group is explained, and the complete Hill sort is to perform the insertion sort operation after each grouping)
The step size is: 5, 3, 1
Divide into 5 groups of records for the first time (the number of groups is the same as the step length): 1,6, 2,7, 3,8, 4,9, 5,10 these five groups of records, and perform these five groups of records separately Insertion sort.
The second time is divided into 3 groups of records: 1, 4, 7, 10, 2, 5, 8, 3, 6, 9 these three groups of records, insert and sort these three groups of records respectively
Divide into 1 group of records for the third time: 1 2 3 4 5 6 7 8 9 10, insert sort for this group of records,
As long as the step size is 1 for the last time, the step size is from large to small. Generally use (array length/2) or (array length/3 +1) to represent the step length.
The advantages of this are:
Divide the array elements to be sorted into multiple groups, and the number of records in each group is relatively small
After the first few sorts, the entire sequence becomes a "basically ordered sequence", and finally all elements are sorted by direct insertion.
Direct insertion sort is very efficient for sequences with basic order and few records, and Hill sort takes advantage of these two points.
Explanation: The first grouping, 49,13,38,27,65,49,97,55,76,04 five groups, insert sorting of these five groups respectively, when 49 finds 13, it will perform insertion sorting. The positions will be swapped, instead of grouping all of them first and sorting them later.
The execution is repeated according to the step length until the step length is 1, and the last direct insertion sort is executed, and the entire Hill sort is completed.
Runtime dynamic graph: Just look at the resources I shared at the bottom. (I don't know how to upload .swf files in the blog garden, or how to upload dynamic pictures. Helpless)
Hill sort dance: v.youku.com/v_show/id_X...
8. heap sort
The Hill sorting mentioned above is an enhancement to insertion sorting, and heap sorting is to enhance selection sorting. Selecting and sorting a data requires a comparison with each data, and does not use the results of some comparisons, for example, 4 is compared with 10, after 3 is compared with 4, it is reasonable to say that there is no need to compare 3 with 10, but the selection sort is not this kind of intelligent, but an honest comparison, and the heap sort makes perfect use of the first few The result of this comparison, thereby increasing efficiency.
Before explaining heap sort, you must know what a heap is?
Heap is a complete binary tree, what is a complete binary tree? Only the nodes of the bottom two layers can be less than 2, and the nodes of the bottom layer are concentrated in the leftmost position of the binary tree (if you don t understand yet, go to Baidu to find out what is a complete binary tree)
This graph is a complete binary tree, but not a heap.
There are two types of piles, large top pile and small top pile
Big top heap: On the basis of a complete binary tree, each parent node is larger than its two child nodes. This is a big top heap, which is characterized by the maximum value of the root node. See the figure below, 90 to 70,80 Big, 70 is bigger than 60, 10, and so on
Small top heap: In contrast to the big top heap, the root node is the smallest value, and each parent node is smaller than its own child nodes, as shown in the figure below
Heap sorting is written by using this characteristic of the heap. The principle is: first construct a set of n-element sequences into a large top heap or a small top heap, and then proceed with the number on the root node with the last digit of the heap. Exchange, at this time, the n-th number is the largest or smallest number in the entire sequence, and then construct the first n-1 elements into a large top heap or a small top heap, and then combine the root node with the nth number The -1 digit is swapped to get the second largest or second smallest number, and the first n-2 digits are constructed, and so on, until only one element is left, and the sorting is complete.
By explaining the principle: heap sorting is divided into three steps
1. Build a large top pile or a small top pile
The root node and the end node are interchanged,
Build a large top pile or a small top pile
3. The sorting is complete
9. summarize and compare the advantages and disadvantages of various sorting algorithms
1. Note that the stability of sorting means: give an example.
Before sorting: 5, 6 (1), 1, 4, 3, 6 (2), (the first 6 is before the second 6)
After sorting: If the result of sorting is 1, 2, 3, 4, 5, 6 (1), 6 (2), then the sorting algorithm is said to be stable, otherwise it is unstable
2. When the number of records to be sorted n is large, and it is a disordered sequence, when stability is not required, it is appropriate to use quick sort
3. When the number of records to be sorted is large, the memory space is allowed, and the sorting is required to be stable, it is appropriate to use merge sorting
4. When the number of records to be sorted is large, and there may be positive or reverse order in the sequence, stability is not required, and heap sort or merge sort is appropriate
5. Wait. . . This kind of direct search on Baidu will definitely be summarized by someone, and the summary is definitely better than me. I understand the principles of various sorting algorithms, how to implement them in Java, and some basic characteristics. Students who are more demanding of themselves need to continue to study in depth. .
Pay attention to forwarding, pay attention to the public account: the way to advance JAVA architecture, reply to Ali to get interview information