排序基础
排序方法分两大类，一类是比较排序，快速排序(Quick Sort)、归并排序(Merge Sort)、插入排序(Insertion Sort)、选择排序(Selection Sort)、希尔排序(Shell Sort)、堆排序(Heap Sort)等属于比较排序方法，比较排序方法理论最优时间复杂度是O(nlogn)，各方法排序过程和原理见 可视化过程。
另一类是非比较排序，被排序元素框定范围的前提下可使用非比较排序方法，例如桶排序(Bucket Sort)、计数排序(Counting Sort)等，时间复杂度可减少至O(n)。
比较排序方法
快速排序(Quick Sort) 快速选择(Quick Select)是快速排序的衍生引用，常用于求中位数、Kth数字。
相关LeetCode题：
973. K Closest Points to Origin 题解
插入排序(Insertion Sort)
相关LeetCode题：
归并排序(Merge Sort) 有一项引申应用、计算数组的Inversions，即求数组中满足于a[i] > a[j] 且 i < j 这样条件的对数，详见 Count Inversions in an array | Set 1 (Using Merge Sort)
C++中提供了两个内置的归并排序方法：
merge(l1.begin(), l1.end(), l2.begin(), l2.end(), result.begin());//which stores the merged array in result
inplace_merge(l.begin(), l.middle, l.end());//where array [begin, middle) is merged with array [middle, end).
相关LeetCode题：
315. Count of Smaller Numbers After Self 题解
非比较排序方法
桶排序(Bucket Sort) 可视化过程，桶排序也有一些引申应用，例如 LeetCode题目 164. Maximum Gap 利用桶划分取值求两元素间隔最大值。
相关LeetCode题：
计数排序(Counting Sort) 可视化过程
相关LeetCode题：
1030. Matrix Cells in Distance Order 题解
排序的应用
实际应用中我们不从头实现排序函数、常直接调用库函数完成排序，如C++ STL中常用的sort、partial_sort等。
相关LeetCode题：
349. Intersection of Two Arrays 题解
350. Intersection of Two Arrays II 题解
976. Largest Perimeter Triangle 题解
非典型排序问题
一些问题要求按一定规则对序列进行排序，比如“奇偶奇偶……”奇数、偶数交叠，或 nums[0] <= nums[1] >= nums[2] <= nums[3]……，我称之为非典型排序问题。
这类问题不能用上述排序方法解决，更多是考量对数组元素排布的处理逻辑。
相关LeetCode题：