9.1 排序的基本概念
二、相关概念
1 、内部排序:若整个排序过程不需要访问外存便能完成。
2 、外部排序:若内存无法容纳全部数据,排序需要借助外
部存储设备才能完成。
3 、稳定排序和不稳定排序
假设 K
i
=K
j
(1≤i≤n , 1≤j≤n , i≠j) ,若在排序前的
序列中
R
i
领先于 R
j
( 即 i<j) ,经过排序后得到的序列中 R
i
仍领
先于 R
j
,则排序方法是稳定的;反之,是不稳定的。
排序前的序列为: (56, 34, 47, 23, 66, 18, 82, 47)
若排序后结果为: (18, 23, 34, 47,47, 56, 66, 82) ,
则称该排序方法是稳定的。
若排序后结果为: (18, 23, 34,47,47, 56, 66, 82) ,
则称该排序方法是不稳定的。