1.排序的基本概念

在排序过程中,根据数据元素是否完全在内存中,可将排序算法分为两类:

1. 内部排序
2. 外部排序

并非所有的内部排序算法都要基于比较操作,事实上,基数排序就不基于比较。

注意

大多数的内部排序算法只适用于顺序存储的线性表

结论 对于任意序列进行基于比较的排序, 求至少的比较次数应考虑最坏情况。对任意 $n$ 个关键字 排序的比较次数至少为 $\left\lceil\log _{2}(n !)\right\rceil$ 。

上述公式证明如下: 在基于比较的排序方法中, 每次比较两个关键字后, 仅出现两种可能的转移。假设整个排序过程至少需要做 $t$ 次比较, 则显然会有 $2^{t}$ 种情况。 由于 $n$ 个记录共有 $n$ !种不同的排列, 因而必须有 $n$ !种不同的比较路径, 于是有 $2^{t} \geqslant n !$, 即 $t \geqslant \log _{2}(n !)$ 。 考虑到 $t$ 为整数, 故为 $\left\lceil\log _{2}(n !)\right\rceil$ 。