排序基本概念与分类

1.排序的定义

2.排序的稳定性

假设Ki = Kj(1 <= i <= n, 1 <= j <= n, i != j),并且在排序前Ri 领先于Rj（即i < j）。如果在排序后Ri仍领先于Rj,则称所用的排序方法是稳定的。否者是不稳定的。比如下图所示：

稳定排序与不稳定排序图解.png

3.内排序与外排序

内排序：在排序整个过程中，待排序的所有记录都放置在内存中。
外排序：由于排序的记录个数较多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

对于内排序来说，影响排序算法的性能主要有三个：
1.时间性能：高效率的内排序算法应当尽可能少的关键字比较次数和尽可能少的记录移动次数。
2.辅助空间：辅助空间是除了存放待排序的记录集合所占用的存储空间外算法所需要的其他空间。
3.算法的复杂度：指的算法本身的复杂度不是时间复杂度。

4.内排序的分类

内排序的分类.png