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).

©2019-2020 Toolsou All rights reserved,
about String How to create objects JavaScript Hundred refining into Immortals 1.15 Legendary Is MCU embedded , It's a cliche Resume the 13th session python Blue Bridge Cup html+css+js Make a simple website home page java Connect to the database to realize basic addition, deletion, modification and query VHDL——JK trigger Java of JDBC programming 3 4j It's not legal python expression _3+4j It's not legal Python expression .【linux】shell: ordinary shell Script exercise