A brief discussion on the implementation of eight major sortings in javascript_javascript skills

One month into the school year, I have dreamed of data structure algorithm questions appearing in written exams many times. I am more afraid of data structures than any "ghosts". Haha, it seems that it is really necessary to review commonly used data structures to prevent the "nightmare" from coming true.

Needless to say the importance of programming basics such as data structures, let’s get straight to the point.

The sorting algorithm is divided into internal sorting and external sorting. Internal sorting uses memory, and only internal sorting is discussed here.

1. Insertion sort: direct insertion sort and Hill sort

2. Selection sort: simple selection sort and heap sort

3. Exchange sort: bubble sort and quick sort

4, merge sort

5, radix sort

Direct insertion sort

Basic idea: In a set of numbers to be sorted, assuming that the previous (n-1) [n>=2] numbers are already in order, first insert the n-th number into the previous ordered number, So that these n numbers are also sorted. Repeat this cycle until everything is in order.

Hill sort

Basic idea: The algorithm first divides a set of numbers to be sorted into several groups according to a certain increment d (n/2, n is the number to be sorted), and the subscripts recorded in each group differ by d. Perform direct insertion sort on all elements in each group, then group them by a smaller increment (d/2), and perform direct insertion sort on each group. When the increment is reduced to 1, the sorting is completed after direct insertion sorting.

Simple selection sort

Basic idea: From a set of numbers to be sorted, select the smallest number and exchange it with the number in the first position, and then find the smallest number among the remaining numbers and exchange it with the number in the second position, so Find haha ​​until the second to last number and the last number.

Heap sort

Basic idea: Heap sort is a tree selection sort, which is an effective improvement on direct selection sort.

A sequence (h1, h2,...,hn) with n elements, if and only if (hi>=h2i,hi>=2i 1) or (hi

Bubble sort

Basic idea: In a set of numbers to be sorted, compare and adjust the two adjacent numbers in sequence from top to bottom for all the numbers in the range that have not yet been sorted, so that the larger The few sink, and the smaller ones rise. That is: whenever two adjacent numbers are compared and it is found that their ordering is opposite to the ordering requirement, they are swapped.

Quick Sort

Basic idea: Select a benchmark element, usually the first element or the last element, and divide the sequence to be sorted into two parts through one scan, one part is smaller than the benchmark element, and the other part is greater than or equal to the benchmark element. At this time, the benchmark The elements are in their correct sorted positions, and then the two divided parts are sorted recursively in the same way.

Merge sort

Basic sorting: Merge sorting method is to merge two (or more) ordered lists into a new ordered list, that is, the sequence to be sorted is divided into several subsequences, each subsequence has sequential. Then merge the ordered subsequences into the overall ordered sequence.

Radix sort

Basic idea: Unify all values ​​to be compared (positive integers) to the same digit length, and add zeros in front of numbers with shorter digits. Then, starting from the lowest bit, sort them one by one. In this way, after sorting from the lowest bit to the highest bit, the sequence becomes an ordered sequence.

Code demonstration address: http://lovermap.sinaapp.com/test/sort.html

Now we analyze the stability of 8 sorting algorithms.

(Netizens are asked to understand the stability of sorting by combining the basic ideas of sorting previously (the basic ideas of the 8 kinds of sorting have been mentioned before and will not be repeated here) otherwise it may be a bit vague)

(1) Direct insertion sort : In general insertion sort, the comparison starts from the last element of the ordered sequence. If it is larger than it, it is inserted directly behind it, otherwise it keeps comparing forward. If an element equal to the inserted element is found, it is inserted after the equal element. Insertion sort is stable.

(2) Hill sorting : Hill sorting is an insertion sorting of elements according to different synchronization lengths. An insertion sorting is stable and will not change the relative order of the same elements, but in different During the insertion sort process, the same elements may move in their respective insertion sort, and the stability will be destroyed, so Hill sorting is unstable.

(3) Simple selection sorting : In one selection, if the current element is smaller than an element, and the small element appears behind an element equal to the current element, then it will be stable after exchange Sex is destroyed. It may be a bit vague just to say it, let’s look at a small example: 858410, in the first scan, the first element 8 will be exchanged with 4, then the relative order of the two 8s in the original sequence is inconsistent with the original sequence, so the selection sorting is not possible Stablize.

(4) Heap sorting : The process of heap sorting is to select the largest (big top heap) or the smallest (small top heap) starting from the n/2th and its child nodes with a total of 3 values. This The choice between 3 elements certainly does not destroy stability. But when selecting elements for parent nodes n/2-1, n/2-2, ..., it is possible that the n/2th parent node exchanges the next element, and the n/2-1th The parent node does not exchange the same element at the end, so heap sorting is not stable.

(5) Bubble sort : As can be seen from the previous content, bubble sort is a comparison of two adjacent elements, and exchange also occurs between these two elements. If the two elements are equal , no need to exchange. So bubble sort is stable.

(6) Quick sort : When the central element is exchanged with an element in the sequence, it is very likely to disrupt the stability of the previous element. Let’s look at a small example: 6 4 4 5 4 7 8 9. In the first sorting pass, the exchange of the central element 6 and the third 4 will destroy the original sequence of element 4, so quick sort is unstable.

(7) Merge sort : In the decomposed sub-column, when there are 1 or 2 elements, 1 element will not be exchanged, and 2 elements will not be exchanged if they are equal in size. During the sequence merging process, if the two current elements are equal, we save the elements of the previous sequence in front of the result sequence, so the merge sort is also stable.

(8) Radix sorting : Sort by low order first, and then collect; then sort by high order, and then collect; and so on, until the highest order. Sometimes some attributes have a priority order. They are sorted by low priority first, and then by high priority. The final order is that those with high priority come first, and those with the same high priority and low priority come first. Radix sorting is based on separate sorting and separate collection, so it is stable.

Summary of classification, stability, time complexity and space complexity of 8 kinds of sorting:

The above is the entire content of this article, I hope you all like it.