Summary of the top ten classic sorting algorithms (including java code implementation)
0. Description of sorting algorithm
0.1 definition of sorting
Sort a sequence of objects according to a keyword.
0.2 description of terms
0.3 algorithm summary
Explanation of picture terms:
0.5 algorithm classification
0.6 difference between comparison and non comparison
Common quick sort, merge sort, heap sort and bubble sort belong to comparative sort. In the final result of sorting, the order between elements depends on the comparison between them. Each number must be compared with other numbers to determine its position. In bubble sort, the problem scale is n, and because it needs to be compared n times, the average time complexity is O (n) ²)。 In sorting such as merge sort and quick sort, the problem scale is reduced to logn times by divide and conquer, so the time complexity is O (nlogn) on average. The advantage of comparative sorting is that it is suitable for data of all sizes and does not care about the distribution of data. It can be said that comparative sorting is applicable to all situations that need sorting.
Count sort, cardinality sort and bucket sort belong to non comparison sort. Non comparative sorting is to sort by determining how many elements should be before each element. For array arr, calculate the number of elements before arr [i], and uniquely determine the position of arr [i] in the sorted array. Non comparative sorting can be solved by determining the number of existing elements before each element, and all traversals can be solved at one time. Algorithm time complexity O (n). The time complexity of non comparative sorting is low, but it takes up space to determine the unique location. Therefore, there are certain requirements for data scale and data distribution.
1. Bubble sort
Bubble sorting is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and exchanges them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to exchange, that is, the sequence has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the sequence through exchange.
1.1 algorithm description
1.2 dynamic diagram demonstration