排序算法

排序算法

应用到排序的场景比比皆是，例如当开发一个学生管理系统时需要按照学号从小到大进行排序，当开发一个电商平台时需要把同类商品按价格从低到高进行排序，当开发一款游戏时需要按照游戏得分从多到少进行排序。

根据时间复杂度的不同，主流的排序算法可以分为三类：

1. $O(n^2)$：冒泡排序、选择排序、插入排序

2. $O(n\log n)$：归并排序、快速排序（平均情况）、堆排序

3. 在取值范围、桶分布和位数等条件合适时可达线性复杂度：计数排序、桶排序、基数排序

在算法界还存在着更多五花八门的排序，它们有些基于传统排序变形而来，有些则是脑洞大开，如鸡尾酒排序、猴子排序、睡眠排序等。

例如睡眠排序，对于待排序数组中的每一个元素，都开启一个线程，元素值是多少，就让线程睡多少毫秒。当这些线程陆续醒来的时候，睡得少的线程先醒来，睡得多的线程后醒来。睡眠排序虽然挺有意思，但是没有任何实际价值。启动大量线程的资源消耗姑且不说，数值接近的元素也未必能按顺序输出，而且一旦遇到很大的元素，线程睡眠时间可能超过一个月。

稳定性

排序算法还可以根据其稳定性，划分为稳定排序和不稳定排序：

• 稳定排序：值相同的元素在排序后仍然保持着排序前的顺序。

• 不稳定排序：值相同的元素在排序后可能打乱排序前的顺序。