Sorting
Comparison Sorting
Selection Sort
Find the smallest element in array[1,...,n] and swap into index 0; 每一次从后面找最小的数,放到当前index里。
Find the smallest element in array[2,...,n] and swap into index 1;
Keep going until all elements are sorted.
Time Complexity:
Best: O(n^2)
Worst: O(n^2)
Bubble Sort
Go through all elements, compare it with the one after it.If current index has greater value, swap. 每次和后一个数对比,如果大,就交换。每次把最大的数放后面。
Repeats until all elements are sorted.
Time complexity:
Best: O(n) - if nearly sorted
Worst: O(n^2)
Insertion Sort
Go through all elements, compare it with the one before it, keep going until it's larger or first of array. 每次往前比较,直到它比前面的数字都大或者前面没数字了。
Merge Sort
Divide: split partition into two sequence, about
n/2
elements eachConquer: merge two sorted subsequences into a sorted sequence
Complexity:
Time complexity: O(n log n)
Space complexity: O(n) – store partitions for merge
Heap Sort
Build a internal max/min heap
For every node from leaf to root, swap with current root, check if it's violates the max/min heap property, if does, perform heapify.
Time complexity: O(n log n)
Quick Sort
Select a pivot, usually first or last element in the array
Divide: partition array into 2 subarrays s.t. elements in the lower part <= elements in the higher part.
Conquer: recursively sort the 2 subarrays
Time complexity: O(n log n) – almost in-place
Linear Sorting
Counting Sort
Radix Sort
Bucket Sort
Last updated