0-1开课;;9.1排序的基本概念;排序的定义;排序的定义;正序、逆序;算法的稳定性;排序的分类;排序算法的性能;9.2插入排序(InsertSorting);运行实例;算法描述;直接插入排序在插入第i个记录时，前面的i-1个记录已经排好序;算法描述;比较次数：n-1次;暂存单元、监视哨;改进的着眼点;SHELL排序;举例;关键问题;时空性能;9.3交换排序(ExchangeSort);运行实例;基本过程;C实现;比较次数：n-1次;空间性能;改进的着眼点;快速排序;10;关键问题;关键问题;运行实例;10;intPartition(RecordTypeR[],ints,intt)
{/*对R[[s..t]中元素进行一次划分（一趟排序），并返回枢轴记录的位置*/
inti=s,j=t;
R[0]=R[i]; /*用区间的第一个记录作为枢轴记录，并暂存于R[0]中*/
while(ij)
{while(R[j].keyR[0].keyij)j--;//自右向左扫描
if(ij){R[i]=R[j]; i++;}//将较小记录交换到前面
while(R[i].key=R[0].keyij)i++;//自左向右扫描
if(ij){R[j]=R[i];j--;}//将较大记录交换到后面
}
R[i]=R[0]; /*枢轴记录最后定位*/
returni; /*返回枢轴位置*/
};关键问题;运行实例;算法描述;O(nlog2n);排序趟数：n-1;空间性能;改进的着眼点;9.4选择排序(SelectionSort);运行实例;关键问题;（1）在r[i]~r[n]中找最小值
（2）将最小记录与r[i]交换;算法描述;时间性能;改进的着眼点;堆的定义;堆与序列的关系;基本思想;堆排序的思路：将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区为[R1,R2,…Rn]
将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全二叉树按照堆定义要求进行调整，使关键字最小(大)的记录成为二叉树的根(存在R[1]中)——初建堆
将根结点中记录与无序区中最后一个结点交换，并将无序区中最后一个记录划入有序区内。
无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，故经过适当调整后可将无序区中记录重建成堆，无序区当前最小(大)成为根。——堆调整
重复上述过程，直到无序区为空(即执行n-1次)。;关键问题;关键问题——堆调整;50;关键问题——初建堆;初建堆举例：;时间性能;9.5归并排序(MergeSort);二路归并排序;运行实例;关键问题;20254050;20254050;执行过程;2025;2025;2025;时间性能;空间性能;9.6基数排序(RadixSort);多关键字排序;基数排序是按最低位优先排序;基数排序;链式基数排序运行实例;505;008;性能分析;9.7各种排序方法的比较;时间性能;时间性能;时间性能;时间性能;空间性能;稳定性与简单性;记录本身信息量;关键码的分布;9.8外排序;什么是外排序;外排序的基本方法;外排序的基本方法;磁盘排序过程;生成初始归并段;置换-选择排序方法;例：;置换-选择排序方法比较次数分析;多路平衡归并;;;;最佳归并树;;;;;