Sorting Algo Avg. Complexity Worst Case Complexity Space Complexity Stable Bubble Sort ~n2 O(n2) 1 yes Selection Sort ~n2 O(n2) 1 no Insertion Sort ~n2 O(n2) 1 yes Shell Sort ~n1.5 Depends on gap sequence 1 no Quick Sort ~nlogn O(nlogn) logn no Merge Sort ~nlogn O(nlogn) 1 yes Heap Sort ~nlogn O(nlogn) 1 no Binary Sort ~nlogn O(nlogn) n yes I Bubble Sort Basic Idea: Compare 2 adjacent numbers, bubble up the smaller number (move the smaller number to the front). Detailed process： Compare 2 adjacent numbers, switch the positions if the 2nd number is smaller, do nothing if the 2nd number is bigger (in the right order). Do the above comparison process from back to front, therefore, the smallest number will be bubbled up to the very front. Repeating the process from 2nd , 3rd… n-1 smallest position have the correct number. Java
Comments
Post a Comment