Date: 07/23 , 8/2
1) selection sort
[23451] - -> [12345]
Solution: Iterate the array, select the smallest item, and swap it with the item in current position.
Repeat until all the items are sorted.
Time: O(n^2)
Space: O(1)
2) merge sort
Solution: split to the smallest sorted unit ,then merge two sorted unit.
repeat until all the items are sorted.
Time: O(nlogn)
Space: O(n)
3) quick sort
solution: find a pivot position, make the left part smaller or equal than the pivot, the right part bigger or equal than pivot, each time make sure the pivot in the correct sorted position.
Time: O(nlogN)
Space: O(1)
4) rainbow sort
{1,0,1,-1,0} ->> {-1, 0,0,1,1}
solution 1: create a same size empty sorted array. When iterate the number array, put -1 to the left part of the sorted array, 1 to the right part of the sorted array, between -1, and 1 , fill with 0.
Time: O(n)
Space: O(n)
solution 2: swap
Time: O(n)
Space: O(1)
5) move 0s to the end 1
Solution: use two pointers, one called start pointer, which start at the beginning position of the array, mainly used to iterate the array, the other one called the end pointer, start at the end position of the array. If the element at the start position is 0, swap the element with the element at the end pointer position. and then move end pointer one step towards the beginning, else move the start pointer one step towards the end. Repeat until two pointers meet.
Time: O(n)
Space: O(1)
