Let's talk about sorting, which can be helpful when I deal with god damn interviews...

1. What?

• Bubble sort
  It traverses the whole array. At each traverse, it will compares two adjacent numbers from the array head to the array tail. If the former is larger then the latter, they will be swapped.

• Quick sort
  One pivot with two pointers...
  
  

• insertion sort
  Start from the second element (pointer A), compare with the previous one. If the previous one is greater than the latter, swapping. Repeat these steps until previous one is less than or equal to the latter, Move the pointer A to the next element, then repeat all steps.
  

• shell sort

• selection sort
  Start From the first element (pointer A), then the other pointer (pointer B = A + 1) will traverse the rest of elements to find the minimum value, then put the minimum one to the start pointer A, then the start pointer A +1. Repeat these steps until A = len - 1.
  

• heap sort
  Construct a heap (Max heap 大顶堆 or Min head 小顶堆), pop root element, then fix the heap, then pop, then fix..... until no one left.
  

• merge sort
  Divide an conquer
  
  
  

• bucket sort

• radix sort

---

2. When to use?

| 排序场景 | 排序效率 |
| ---- | ---- | ---- |
| Random | 希尔>快排>归并 |
| Few unique | 快排>希尔>归并 |
| Reversed | 快排>希尔>归并 |
| Almost sorted | 插入排序>基数排序>快排>希尔>归并 |

3. How?

Animation of these sortings