(1) Bubble Sort

Bubble sort is the process of moving a smaller element forward or a larger element backward. The comparison is between two neighboring elements and the exchange also happens between these two elements. So the order of the same elements before and after does not change, so bubble sort is a stable sorting algorithm.

(2) Selection Sort

Selection sort is to select the smallest of the current elements for each position, such as selecting the smallest for the first position. ...... Example illustrates much better. Sequence 5 8 5 2 9, we know that the first selection of the first element 5 will be exchanged with 2, then the relative order of the original sequence of two 5 will be destroyed, so the selection of the sort of unstable sorting algorithm

(3) Insertion Sort

Insertion Sort is the insertion of one element at a time into the base of an already ordered small sequence. Comparison is made from the end of the ordered sequence, that is, the element you want to insert and the largest already ordered than the beginning, if it is larger than it is inserted directly after it, otherwise, keep moving forward until you find the position where it should be inserted. If it is equal to the inserted element, then the inserted element puts the element it wants to insert after the equal element. So the order of the equal elements before and after does not change. So insertion sort is stable.

(4) Rapid sort

Rapid sort has two directions, the i subscript on the left goes all the way to the right (backward) when a[i] <= a[center_index], where center_index is the array subscript of the pivot element, which is generally taken as the 0th element of the array. And the j subscript on the right goes all the way to the left (forward) when a[j] > a[center_index]. If both i and j can't go any further, i <= j, exchange a[i] and a[j],repeat the above process until i>j. Exchange a[j] and a[center_index] to complete one trip of quick sort. In the pivot element and a[j] exchange, it is likely to upset the stability of the previous elements, for example, the sequence is 5 3 3 4 3 8 9 10 11, now the pivot element 5 and 3 (the fifth element, the subscript counts from 1) exchange will upset the stability of the element 3, so the fast sort is an unstable sorting algorithm. (Instability occurs at the moment when the pivot element and a[j] are exchanged)

(5) Merge sort

Merge sort is to recursively divide the sequence into short sequences, the recursive exit is a short sequence of only 1 element (considered directly ordered) or 2 sequences (1 comparison and exchange), and then merge the various ordered segments of the sequence into an ordered long sequence. The merging continues until the original sequences are fully ordered. No swapping occurs when they are equal. Therefore, merge sort is also a stable sorting algorithm.

(6) Base Sort

Base sort is to sort by low first, then collect; then sort by high, then collect; and so on until the highest. Sometimes some attributes are prioritized, so they are sorted by low priority first, then by high priority, and the final order is that the high priority is first, and the low priority is first if the high priority is the same. Base sorting is based on sorting separately and collecting separately, so its a stable sorting algorithm.

(7) Hill Sort (shell)

Hill Sort is an insertion sort according to different step lengths of the elements, when the elements are very unordered at the beginning, the step length is the largest, so the insertion of the number of elements is very small, the speed is very fast; when the elements are basically ordered, the step length is very small, the insertion of the sequences for the ordered sequence of the efficiency of the insertion of the sort is very high. So, the time complexity of Hill sort will be better than o(n^2). Due to multiple insertion sort, we know that one insertion sort is stable and does not change the relative order of the same elements, but during different insertion sorts, the same elements may move in their respective insertion sorts, and finally their stability will be disturbed, so shell sort is unstable.

(8) Heap sort

We know that the structure of heap is that the children of node i are 2*i and 2*i+1 nodes, big top heap requires that the parent node is greater than or equal to its 2 children, and small top heap requires that the parent node is less than or equal to its 2 children. In a sequence of length n, the process of heap sorting is from the n/2nd and its children nodes *** 3 values to choose the largest (big top heap) or the smallest (small top heap), the choice between these 3 elements will not destabilize of course. But when choosing between n/2-1, n/2-2, .... .1 the selection of elements for these parents is destabilizing. It is possible that the n/2nd parent node swap swaps the next element over, while the n/2-1th parent node leaves the next identical element unswapped, then the stability between these 2 identical elements is destabilized. So, heap sort is unstable sorting algorithm

I. Sorting

Sorting method Average time Worst case Stability Extra space Remarks

Bubbling O(n2) O(n2) Stable O(1) Better in n hours

Swap O(n2) O(n2) Unstable O(1) Better in n hours

Select O(n2) O( n2) unstable O(1) better for n hours

Insertion O(n2) O(n2) stable O(1) better when mostly sorted

Shell O(nlogn) O(ns) 1<s<2 unstable="" o(1)="" s is the selected grouping</s

Fast O(nlogn) O( n2) Unstable O(nlogn) Better when n is large

Grouping O(nlogn) O(nlogn) Stable O(1) Better when n is large

Heap O(nlogn) O(nlogn) Unstable O(1) Better when n is large

Base O(logRB) O(logRB) Stable O(n) B is the true number (0-9 ), R is the base (tens hundreds)

II Finding

Unwritten ......

III Tree diagrams

The time complexity of Kruskal's algorithm is O(eloge)

The time complexity of Prim's algorithm is O(n2)

Dijay Stella's algorithm has a time complexity of O(n2)

Topological sorting algorithm has a time complexity of O(n+e)

Critical path algorithm has a time complexity of O(n+e)