排序算法&分析——什么时候 用 什么排序

了解各种排序，详见排序专栏

排序算法历史

纵观排序算法的历史，有哪些排序算法的速度可以到达$O(nlog(n))$？

• 冒泡排序（$Bubble$ $Sort$）：冒泡排序是最简单的排序算法之一。它通过多次比较和交换相邻元素的方式，将最大（或最小）的元素逐渐“冒泡”到数组的一端。尽管冒泡排序的时间复杂度为$O(n^2)$，效率较低，但它易于理解和实现。

• 选择排序（$Selection$ $Sort$）：选择排序是一种简单直观的排序算法。它通过每次选择未排序部分的最小（或最大）元素，并将其放置在已排序部分的末尾，逐渐构建有序序列。选择排序的时间复杂度也为$O(n^2)$，但相比冒泡排序，它的交换次数较少。

• 插入排序（$Insertion$ $Sort$）：插入排序是一种稳定的排序算法。它通过将未排序部分的元素逐个插入已排序部分的适当位置，来构建有序序列。插入排序的时间复杂度为$O(n^2)$，但对于小规模或基本有序的数组，插入排序的性能较好。

• 希尔排序（$Shell$ $Sort$）：希尔排序是插入排序的一种改进版本。它通过将数组分割成多个较小的子序列，并对子序列进行插入排序，最后再对整个数组进行一次插入排序。希尔排序的时间复杂度介于$O(n)$和$O(n^2)$之间，取决于所选的间隔序列。

• 归并排序（$Merge$ $Sort$）：归并排序是一种分治算法。它将数组递归地分成两个子数组，分别进行排序，然后将两个有序子数组合并成一个有序数组。归并排序的时间复杂度为$O(nlog(n))$，它是一种稳定的排序算法。

• 快速排序（$Quick$ $Sort$）：快速排序也是一种分治算法。它通过选择一个基准元素，将数组分成两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素。然后递归地对两个子数组进行排序。快速排序的时间复杂度为$O(nlog(n))$，但在最坏情况下可能达到$O(n^2)$。

• 堆排序（$Heap$ $Sort$）：堆排序利用堆这种数据结构进行排序。它通过构建最大堆（或最小堆），将堆顶元素与最后一个元素交换，并对剩余元素重新调整堆，重复这个过程直到整个数组有序。堆排序的时间复杂度为$O(nlog(n))$，它是一种不稳定的排序算法。

• 计数排序（这个不能算排序吧~）（$Counting$ $Sort$）：计数排序是一种非比较排序算法。它通过确定每个元素在排序后的序列中的位置，来实现排序。计数排序的时间复杂度为$O(n+k)$，其中k是待排序数组中的最大值。计数排序适用于元素范围较小的情况。

• 桶排序（$Bucket$ $Sort$）：桶排序也是一种非比较排序算法。它将待排序元素分到不同的桶中，对每个桶中的元素进行排序，然后按照桶的顺序将元素合并起来。桶排序的时间复杂度取决于桶的数量和每个桶内使用的排序算法。

• 基数排序（$Radix$ $Sort$）：基数排序是一种非比较排序算法。它根据元素的位数，将待排序元素按照位数从低到高进行排序。基数排序可以使用稳定的排序算法作为每个位数的排序算法，如计数排序或桶排序。

排序算法分析

很快的排序

我们发现，很快的排序，例如：桶排序和基数排序，它们的代码都比较复杂，一般能不用就不用。

较快的排序

而较快的排序，例如：归并排序和堆排序（之所以不放快排 是因为快排实在是太不稳定了！！！），它们的代码也比较复杂（优先队列当我没说），如果使用优先队列有不方便访问，因此能不用就不用。
注：有时优先队列是很方便的。

中等的排序

中等的排序，如：希尔排序和快速排序，有时速度无法满足要求，并且代码也属于复杂的范畴。

很慢的排序

很慢的排序，如：冒泡排序和选择排序，虽然代码简短好记，但是速度实在是太慢了！！！！！！

分析的结果

0.没有要求

如果没有特殊要求的话，用优先队列进行堆排是不错的选择，另外还可以用$sort$函数排序

1.对速度有要求

如果对速度有要求的话，建议用优先队列进行堆排，也可以用$sort$函数排序。

说了跟没说一样

2.边排序边操作

如果要在排序中操作，建议使用各种较慢的排序算法，这样方便理解以及更改。

3.条件1&条件2

这样的话就最好用归并排序了！！这是一种优秀的排序算法，并且稳定，可以在大部分情况下使用

4.在有序数中操作

这样建议使用插入排序，因为插入排序本身就是维护一个有序数列，这样的话方便快捷！

5.条件1&条件4

插入排序优化——超越归并排序的超级算法！！

详见我的神奇博客：史上最快的插入排序