A brief discussion on the implementation of eight major sortings in javascript

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<=h2i,hi<=2i 1 ) (i=1,2,...,n/2) is called a heap. Only heaps that meet the former condition are discussed here. It can be seen from the definition of a heap that the top element of the heap (that is, the first element) must be the largest item (big top heap). A complete binary tree can represent the structure of a heap very intuitively. The top of the heap is the root, and the others are the left subtree and the right subtree. Initially, the sequence of numbers to be sorted is regarded as a binary tree stored sequentially, and their storage order is adjusted so that it becomes a heap. At this time, the number of root nodes of the heap is the largest. Then swap the root node with the last node of the heap. Then re-adjust the previous (n-1) numbers to form a heap. And so on, until there is a heap with only two nodes, and they are exchanged, and finally an ordered sequence of n nodes is obtained. From the algorithm description, heap sorting requires two processes, one is to establish the heap, and the other is to exchange positions between the top of the heap and the last element of the heap. So heap sort consists of two functions. One is the penetration function to build the heap, and the other is the function to repeatedly call the penetration function to implement sorting.

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: