Sorting method          Average situation         Best case         Worst case scenario         Auxiliary space         stability
Bubble sort          O(n^2)           O(n)              O(n^2)
O(1)                stable Select sort          O(n^2)          O(n^2)
O(n^2)            O(1)               instable Insert sort          O(n^2)
O(n)              O(n^2)            O(1)                stable
Shell Sort O(n*log(n))~O(n^2) O(n^1.3)       O(n^2)            O(1)              instable
Heap sort           O(n*log(n))     O(n*log(n))    O(n*log(n))       O(1)
instable Merge sort        O(n*log(n))     O(n*log(n))    O(n*log(n))       O(n)
stable Quick sort        O(n*log(n))     O(n*log(n))      O(n^2)
O(1)              instable

After optimization of bubble sort , The best time complexity can be achieved O(n). Set a flag bit , If there is one comparison where no exchange occurs , Can end early , Therefore, in the case of positive sequence , The time complexity is O(n). Select sort at worst and best , Must select the smallest of the remaining sequences （ large ） The number of , Exchange with the next position element of the ordered sequence , The best time complexity and worst time complexity are both O(n^2). Insert sort is to insert the next element of the ordered sequence into the previous sorted one ( You need to choose the right location ) In the sequence of , In the case of positive sequence, the time complexity is O(n). A heap is a complete binary tree , So the depth of the tree must be log(n)+1, The best and worst time complexity are both O(n*log(n)). Merge sort is to divide a large array into two small arrays , Recursion in turn , Equivalent to a binary tree , The depth is log(n)+1, So the best and worst time complexity is O(n*log(n)). Quick sort in positive or reverse order , The subsequence of each partition is only one less record than the previous partition , Draw it with a recursive tree , It's a slanting tree , It is necessary at this time n-1 Subrecursion , And i The secondary division should go through n-i Second keyword comparison to find i Records , So the time complexity is \sum_{i=1}^{n-1}(n-i)=n(n-1)/2, Namely O(n^2).

Technology
Daily Recommendation
views 5
views 3
views 3