排序基础
Overview
在之前学习排序算法的过程中，我们一般会将排序算法分为不同的种类来学习，比如插入类排序、选择类排序等等。但是在实际使用算法时，我们其实并不需要对算法属于哪一个种类关注太多，而更需要关注的是排序的时间复杂度、空间复杂度和排序的稳定性，从而根据业务场景选择适当的算法。本文也将以时间复杂度为纬度，来对常用的算法进行划分，对不同种类的算法进行比较。
稳定排序
原地排序
in place
逆序数
逆序数（inversion）： 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
当一个待排序列完全有序时，逆序数为 0，当完全逆序时，逆序数为n * (n-1) / 2。
O(n^2)
适合小规模数据的排序，当数据量较大时便不太实用：
- 冒泡排序
- 直接插入排序
- 选择类排序
O(nlogn)
数据量较大时常用：
- 快速排序
- 归并排序
- 堆排序
O(n)
对初始序列要求非常苛刻，只能适用于极少数的应用场景：
- 桶排序
- 基数排序
这两种算法是基于非比较的排序算法，不涉及元素之间的比较操作，所以这两种算法都可以将排序的时间复杂度降到 O(n)。时间复杂度 O(n)的排序算法也叫作线性排序（Linear sort）。