24/12/291第第88章排序章排序•排序的概念及种类•插入法排序的各种具体实现方法及算法分析•选择法排序的各种具体方法的实现及时间性能分析•交换法排序的具体实现及性能分析•归并排序和基数排序的各自实现算法传世www.523cs.com为您整理24/12/292本章导读本章导读排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法的适用场合，以便在实际应用中能根据具体的问题选择合适的排序方法。通过本章学习，读者应该掌握以下几项内容：•排序的概念及种类•插入法排序的各种具体实现方法及算法分析•选择法排序的各种具体方法的实现及时间性能分析•交换法排序的具体实现及性能分析•归并排序和基数排序的各自实现算法24/12/2938.18.1排序的基本概念排序的基本概念8.1.18.1.1排序及其分类排序及其分类11．排序概念．排序概念排序（sorting）又称分类，是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值（关键字）递增或递减的次序重新排列的过程。排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。如电话簿、病历、档案室中的档案、图书馆和各种词典的目录表等，几乎都需要对有序数据进行操作。24/12/294假设含有n个记录的序列为：{R1，R2，…，Rn}(8-1)其相应的关键字序列为：{K1，K2，…，Kn}需确定1，2，…，n的一种排序p1，p2，…，pn，使其相应的关键字满足如下关系：Kp1≤Kp2≤…≤Kpn(8-2)即使得式（8-1）的序列成为一个按关键字有序的序列{Rp1，Rp2，…，Rpn}(8-3)这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。24/12/29522．排序分．排序分类类(1)增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。(2)稳定排序和不稳定排序：假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj（即i
