大话数据结构读书笔记-排序

## 1.排序的基本概念与分类 **定义：**假设含有n个记录的序列为${r_1, r_2,...,r_n}$,其相应的关键字分别为${k_1,k_2,...,k_n}$，需要确定1, 2, ..., n的一种序列$p_1,p_2,...,p_n$,使得其对应的关键字满足$k_{p1},k_{p2},...k_{pn}$（非递减或非递增）关系，即使得序列成为一个按关键字有序得序列${r_{p1},r_{p2},...,r_{pn}}$,这样得操作称为排序。 在排序问题中，通常将数据元素称为记录。输入是一个记录集合，输出也是一个记录集合，所以可以将排序看作是排序表得一种操作。关键字$k_i$可以是记录r的主关键字，也可以是次关键字，甚至是若干数据项的组合。 ### 1.1 排序的稳定性 由于待排序记录序列中可能存在两个或两个以上的关键字相等的记录，排序结果可能存在不唯一的情况。 **定义：**假设$k_i=k_j(1<=i<=n,1<=j<=n,i!=j)$，且在排序前的序列中$r_j$领先于$r_j$(i