第十章-内部排序.ppt

第10章内部排序;第十章内部排序;学习要点;排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~

排序分类

按待排序记录所在位置

内部排序：待排序记录存放在内存

外部排序：排序过程中需对外存进行访问的排序

按排序依据原则

插入排序：直接插入排序、折半插入排序、希尔排序

交换排序：冒泡排序、快速排序

选择排序：简单选择排序、堆排序

归并排序：2-路归并排序

基数排序;按排序所需工作量

简单的排序方法：T(n)=O(n2)

先进的排序方法：T(n)=O(logn)

基数排序：T(n)=O(d.n)

排序基本操作

比较两个关键字大小

将记录从一个位置移动到另一个位置

稳定排序与不稳定排序

关键码相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2则该排序方法是不稳定的。;10.2插入排序

直接插入排序:整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序

例：序列为{49，38，65，97，76，13，27，49}

{(49)，38，65，97，76，13，27，49}

(38){(38，49)，65，97，76，13，27，49}

(65){(38，49，65)，97，76，13，27，49}

(97){(38，49，65，97)，76，13，27，49}

(76){(38，49，65，76，97)，13，27，49}

(13){(13，38，49，65，76，97)，27，49}

(27){(13，27，38，49，65，76，97)，49}

(49){(13，27，38，49，49，65，76，97)};直接插入排序的算法;算法评价

时间复杂度

若待排序记录按关键字从小到大排列(正序)

关键字比较次数：;直接插入排序的稳定性;折半插入排序

排序过程：用折半查找方法确定插入位置的排序叫~;VoidBInsertSort(SqListL){

for(i=2;i=L.length;++i){

L.r[0]=L.r[i];（将L.r[i]暂存到L.r[0]）

low=1;high=i–1;

while(low=high){（在子表中查找插入位置）

m=(low+high)/2;

ifLT(L.r[0].key,L.r[m].key)high=m-1;（插入点在低半区）

elselow=m+1;（插入点在高半区）

}while

for(j=i-1;j=high+1;--j)L.r[j+1]=L.r[j];（记录后移）

L.r[high+1]=L.r[0];（插???记录）

}//for

};折半插入排序的稳定性;希尔排序(缩小增量法)

它属于插入排序类的方法。它的基本思想是：先将整个待排序的记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。

排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止;取d3=1

三趟分组：;算法描述;算法描述;希尔排序特点

子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列

希尔排序可提高排序速度，因为

分组后n值减小，n2更小，而T(n)=O(n2),所以T(n)从总体上看是减小了

关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序

增量序列取法

无除1以外的公因子

最后一个增量值必须为1;冒泡排序

将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上

对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置

重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止;例;算法评价

时间复杂度

最好情况（正序）

比较次数：n-1

移动次数：0

最坏情况（逆序）

比较次数：

;快速排序