This is the 17th day of my participation in the August Text Challenge.More challenges in August

Insertion sort

  • Insert records to be sorted one at a time into a previous’ sorted subsequence ‘by their keyword size, similar to insert cards
  • For example, n=6, the six collation codes of array R are: 17,3,25,14,20,9. Its direct insertion sort execution process

Hill sorting

Firstly, the whole sequence of records to be sorted is divided into several sub-sequences for 'direct insertion sort' respectively. When the records in the whole sequence are "basically ordered", the direct insertion sort of all records is carried out successively. Assuming the increment is 5, then I, I +5.... ; The increment in the figure below is 5Copy the code

Exchange sort

  • Treat the sorting sequence from back to front (starting with the element with larger subscript), ‘compare the sorting code of adjacent elements’, if’ reverse order is found, swap ‘,
  • So that the smaller elements of the sorting code gradually move from the back to the front, like bubbles under the water, gradually rise up.
  • For example, n=6, the six collation codes of array R are: 17,3,25,14,20,9. The following figure shows the execution process of bubble sort algorithm.

Quick sort

  • Take an element (usually the first element) in the sequence to be sorted as the benchmark, and divide the elements into “left and right sub-sequences” through a sorting.
  • The collation codes of ‘left subsequence elements’ are all’ less than or equal to the collation codes of the reference elements’,
  • The collation code of the ‘right subsequence’ is’ greater than that of the reference element ‘, and the two subsequences are then rapidly sorted until the whole sequence is in order.
  • Elements are compared and exchanged from both ends to the middle. Elements with larger sorting codes can be swapped to the back at once, and records with smaller sorting codes can be swapped to the front at once.
  • The distance recorded for each move is larger, resulting in fewer overall comparisons and moves.

For example, given the sort code :(46,55,13,42,94,05,17,70)

A division of

Selection sort

Simple selection sort

The basic idea is: Select the minimum value from 'array[0]~array[n-1]' and swap with 'array[0]'. Select the minimum value from 'array[1]~array[n-1]' and swap with 'array[1]'. Select the minimum value from 'array[2]~array[n-1]' for the third time, swap with 'array[2]'... For example, given n=8, the collation code for the eight elements in array R is: '(8, 3, 2, 1, 7, 4, 6, 5)'Copy the code

Heap sort

  • Sort codes K1, K2, K3… Kn is represented as’ a complete binary tree ‘, and then the selection starts from the last non-leaf node of the tree.
  • Make the subbinary tree with this node as the root conform to the definition of heap, then repeat from the NTH / 2-1 sorting code until the first sorting code.
  • Swap the data of the first node (binary root node) and the last node in the heap (K1 and KN),
  • Then k1Kn-1 rebuilds the heap, and then k1 and KN-1 swap, and k1Kn-2 rebuilds the heap, and k1 and KN-2 swap,
  • This is repeated, decreasing the number of elements each time the heap is rebuilt by one, until there is only one element left.

Merge sort

  • To combine two (or more) ordered tables into a ‘new ordered table’, that is, to divide the sequence to be sorted into subsequences,
  • Each subsequence is’ ordered ‘. Then the ordered subsequence is combined into a whole ordered sequence.

Radix sort

  • Number sort allocates the elements to be sorted into buckets for sorting purposes
  • Is a stable sort whose time complexity is O(nlog(r)m), where r is the radix taken and m is the number of heaps

Comparison of sorts

'Unstable' : 'fast select heap' (quicksort, select sort, heap sort, Hill sort) 'stable' : 'insert and return base' (simple insert sort, bubble sort, merge sort, count sort, radix sort) 'Heap sort, Merge sort, select sort, radix sort '-- >' Heap sort, merge sort, select sort, radix sort'Copy the code