排序小结

苍穹之下，万物有序。在(OI)中，排序也是必不可少的技能。排序可以分为依赖于比较的排序和不依赖比较的排序，根据时间复杂度还可以继续细分为三类：

(O(N^2))排序：选择排序，插入排序，冒泡排序

(O(NlogN))排序：快速排序，归并排序

以上五种排序都是基于比较的排序方式。(NlogN)是复杂度下界，只有不基于比较的排序方式才能打破下界。

(O(n))排序：桶排序，计数排序，基数排序

以上三种是不基于比较的排序方式，复杂度跟值域和数据个数有关。

另外，排序还有很多很多变种，例如排序网络、希尔排序、臭皮匠排序、珠排序、猴子排序等等，有兴趣的读者可以去看看，在(OI)应用中，上面列举的(8)种排序方式应该是足够的了。