基本概念插入排序交换排序选择排序归并排序基数排序内部排序比较外排序第9章排序关键字关键字(Key)(Key)作为排序依据的数据对象中作为排序依据的数据对象中的属性域。不同的数据对象若关键字互不的属性域。不同的数据对象若关键字互不相同相同，，则这种关键字称为主关键字。则这种关键字称为主关键字。排序排序使一组任意排列的对象变成一组按关使一组任意排列的对象变成一组按关键字线性有序的对象。键字线性有序的对象。排序算法的稳定性排序算法的稳定性判断标准：关键字相判断标准：关键字相同的数据对象在排序过程中是否保持前后同的数据对象在排序过程中是否保持前后次序不变。次序不变。9.19.1基本概念基本概念排序方法的分类排序方法的分类按是否涉及数据的内、外存交换分类按是否涉及数据的内、外存交换分类外排序、内排序外排序、内排序按策略划分内部排序方法按策略划分内部排序方法插入排序、选择排序、交换排序、归插入排序、选择排序、交换排序、归并排序和基数排序。并排序和基数排序。排序算法性能评价排序算法性能评价评价排序算法好坏的标准主要有两条：评价排序算法好坏的标准主要有两条：算法执行所需要的时间和所需要的附加算法执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也空间。另外，算法本身的复杂程度也是需要考虑的一个因素。是需要考虑的一个因素。不同存储方式的排序过程不同存储方式的排序过程以顺序表作为存储结构以顺序表作为存储结构对记录本身进行物理重排对记录本身进行物理重排以链表作为存储结构以链表作为存储结构无须移动记录，仅需修改指针。无须移动记录，仅需修改指针。用顺序的方式存储待排序的记录，但同用顺序的方式存储待排序的记录，但同时建立一个辅助表时建立一个辅助表只需对辅助表的表目进行物理重排，只需对辅助表的表目进行物理重排，适适用于难于在链表上实现，仍需避免排用于难于在链表上实现，仍需避免排序序过程中移动记录的排序方法过程中移动记录的排序方法为简单起见，数据的存储结构采用记录数为简单起见，数据的存储结构采用记录数组形式，同时假定关键字是整数。记录数组形式，同时假定关键字是整数。记录数组的类型说明如下：组的类型说明如下：typedefintKeyTypetypedefintKeyType；；typedefstruct{typedefstruct{KeyTypekeyKeyTypekey；；InfoTypeotherinfoInfoTypeotherinfo；；}RecType}RecType；；typedefRecTypeSeqList[n+1]typedefRecTypeSeqList[n+1]；；9.29.2插入排序插入排序基本原理：每步将一个待排序的对象，基本原理：每步将一个待排序的对象，按其关键字大小，插入到前面已经排按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对好序的一组对象适当位置上，直到对象全部插入为止。象全部插入为止。直接插入排序希尔排序直接插入排序直接插入排序基本思想：当插入第基本思想：当插入第ii个对象时，前面个对象时，前面的的R[1]R[1]，，R[2]R[2]，…，，…，R[i-1]R[i-1]已经排好已经排好序，此时，用序，此时，用R[i]R[i]的关键字与的关键字与R[i-1],R[i-1],，，R[i-2]R[i-2]，…的关键字顺序进行比较，找，…的关键字顺序进行比较，找到插入位置即将到插入位置即将R[i]R[i]插入，原来位置上插入，原来位置上对象向后顺移。对象向后顺移。直接插入排序举例直接插入排序举例i(0)(1)(2)(3)(4)(5)tempi(0)(1)(2)(3)(4)(5)temp[[2121]254925*160825]254925*1608251[1[21252125]4925*160849]4925*1608492[2[212549212549]25*160825*]25*160825*3[3[212525*49212525*49]160816]1608164[4[16212525*4916212525*49]0808]08085[5[0816212525*490816212525*49]]直接插入排序算法直接插入排序算法voidlnsertSort(SeqListR){inti,j;for(i=2;i
