文章目录
- 1.排序的基本概念
- 2.稳定排序和不稳定排序
- 3.内部排序和外部排序
1.排序的基本概念
- 排序定义：
将一组数据元素序列重新排列，使得数据元素序列按某个数据项（关键字）有序。 - 排序依据：是依据数据元素的关键字。
若关键字是主关键字（关键字值不重复），这无论采用何种排序方法，排出的结果都是唯一的；
若关键字是次关键字（关键字值可以重复），则排出的结果可能不唯一； - 一般情况下，
假设含n个记录的序列为{ R1, R2, …， Rn }，其相应的关键字序列为 { K1, K2, …， Kn }
这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ：Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …， Rpn }的操作称作排序。
2.稳定排序和不稳定排序
- 对于任意的数据元素序列，若排序前后所有相同关键字的相对位置都不变，则称该排序方法称为稳定的排序方法。
- 若存在一组数据序列，在排序前后，相同关键字的相对位置发生了变化，则称该排序方法称为不稳定的排序方法。
例如，对于关键字序列3， 2， 3， 4，若某种排序方法排序后变为2， 3， 3， 4，则该排序方法是不稳定的。
3.内部排序和外部排序
- 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
- 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序
- 内部排序的方法：
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
