一、排序的稳定性
当排序记录中的关键字 ${K_i}(i = 1,2,...,n)$ 都不相同时，则任何一个记录的无序序列经排序后得到的结果唯一；反之，当待排序的序列中存在两个或两个以上关键字相等的记录时，则排序所得的结果不唯一。
假设 ${K_i} = {K_j}(1 \le i \le n,1 \le j \le n,i \ne j)$ ，也就是说其对应的关键字相同，且在排序前的序列中 ${R_i}$ 领先于 ${R_j}$（即 $i<j$ ）。若在排序后的序列中仍领先于，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中领先于，则称所用的排序方法是不稳定的。注意，排序算法的稳定性是针对所有 记录而言的。也就是说，在所有的待排序记录中，只要有一组关键字的实例不满足稳定性要求，则该排序方法就是不稳定的。虽然稳定的排序方法和不稳定的排序方法排序结果不同，但不能说不稳定的排序方法就不好，各有各的适用场合。
例题
1. 排序算法的稳定性是指（ A ）。
A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
C.排序算法的性能与被排序元素个数关系不大
D.排序算法的性能与被排序元素的个数关系密切
二、排序算法的分类和基本原理
- 插入排序的原理：向有序序列中依次插入无序序列中待排序的记录，直到无序序列为空，对应的有序序列即为排序的结果，其主旨是“插入”。
- 交换排序的原理：先比较大小，如果逆序就进行交换，直到有序。其主旨是“若逆序就交换”。
- 选择排序的原理：从无序序列找关键字最小的记录，再放到已排好序的序列后面， 直到所有关键字全部有序，其主旨是“选择”。
- 归并排序的原理：依次对两个有序子序列进行“合并”，直到合并为一个有序序列为止，其主旨是“合并”。
- 基数排序的原理：接待排序记录的关键字的组成成分进行排序的一种方法，即依次比较各个记录关键字相应“位”的值进行排序，直到比较完所有的“位”，即得到一个有序的序列。
