Basic Sorting
Overview
There are 7 main sorting algorithm, which are also connected with other conceptions. Will be finished in the future.
Insert sort
$O(n^2)$
- Insert the value into a sorted list - swap with element of bottom one by one
Hill sort
$O(nlog(n))$
Select sort
$O(n^2)$
- Choose the smallest/largest element and put into the sorted array
Heap sort
$O(nlog(n))$
- Put items into heap, and pop one by one out
- Use heap can find the top K values easily. Create a heap with length of K, put items into it one by one
Bubble sort
$O(n^2)$
- Choose a value, if it is larger than the next one, replace them, until this value arrive the boundary of end
- Update the boundary of end, do the previous choosing and moving steps again
Quick sort (binary sort)
$O(nlog(n))$
- Choose a pivot, put all values smaller than pivot into left, all values larger than pivot into right
- Do quick sort for left and right
- Connect left, pivot and right
Merge sort
$O(nlog(n))$
- Divide a list into left and right
- Do the merge sort for left and right
- Put the sorted left and right together
Some functions in Python
- sorted(a, key=lambda x:x[0])
Some samples
- Find the 0-Kth largeset elements
- Heap O(klong(n))
- Find the Kth largeset element
- Move the smaller elements to left, larger elemetns to right, until the right part only have K elements