Let's talk about sorting, which can be helpful when I deal with god damn interviews...
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.
One pivot with two pointers...
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.
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.
Construct a heap (Max heap 大顶堆 or Min head 小顶堆), pop root element, then fix the heap, then pop, then fix..... until no one left.
Divide an conquer
2. When to use?
| 排序场景 | 排序效率 |
| ---- | ---- | ---- |
| Random | 希尔>快排>归并 |
| Few unique | 快排>希尔>归并 |
| Reversed | 快排>希尔>归并 |
| Almost sorted | 插入排序>基数排序>快排>希尔>归并 |