第十章内部排序10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种排序方法的综合比较10.1概述一、排序的定义三、稳定排序和不稳定排序五、内部排序方法的分类四、内部排序和外部排序二、排序的分类一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。按待排序记录的稳定性-稳定排序-不稳定排序按待排序记录所在位置–内部排序：待排序记录存放在内存–外部排序：排序过程中需对外存进行访问的排序按排序依据原则–插入排序：直接插入排序、折半插入排序、希尔排序–交换排序：冒泡排序、快速排序–选择排序：简单选择排序、堆排序–归并排序：2-路归并排序–基数排序二、排序的分类按排序所需工作量–简单的排序方法：T(n)=O(n)²–先进的排序方法：T(n)=O(logn)–基数排序：T(n)=O(d.n)-排序基本操作•比较两个关键字大小•将记录从一个位置移动到另一个位置–待排序记录的存储方式•地址连续的一组存储单元——向量排序•静态链表，记录间的次序由指针指示——（链）表排序•地址连续的一组存储单元，另设一个指示各个记录存储位置的地址向量——地址排序稳定与不稳定：一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。例：初始关键字：49，38，65，97，76，13，27，49’排序结果：13，27，38，49，49’，65，76，97稳定的13，27，38，49’，49，65，76，97不稳定的三、稳定排序和不稳定排序四、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。五、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区ki基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类基数类待...
