文档介绍：第十章排序
基本概念
内部排序
内部排序方法比较
外部排序简介
基本概念
关键字(key): 记录的某一个可以用来标识一个数据元素的数据项
排序(Sorting):把一组记录,按照记录中某个关键字进行有序(递增或递减)排列的过程
内部排序:文件较小时,排序在内存中完成,不涉及外存的排序方法称为内部排序
外部排序:文件比较大,排序需要内存和外存,称这种排序为外部排序
排序方法的分类:
按是否涉及数据的内、外存交换
策略划分内部排序方法
内部排序
外部排序
插入排序
选择排序
交换排序
归并排序
分配排序
排序算法的基本操作
(1) 比较两个关键字的大小
(2) 改变指向记录的指针或移动记录本身
待排文件的常用存储方式
(1)以顺序表作为存储结构
(2)以链表作为存储结构
(3)用顺序的方式存储待排序的记录,并建立辅助表
排序算法性能评价
①执行时间和所需的辅助空间
②算法本身的复杂程度
内部排序 插入排序
概念:按关键字大小将一个记录插入到一个有序的文件中的适当位置,并且插入后使文件仍然是有序的
分类:
直接插入排序
折半插入排序
希尔排序
直接插入排序
概念:每一次将一个待排序的记录,按其关键字值的大小插入到已经排序的部分文件中适当的位置上,直到全部插入完成
算法:
InsertSort(Recordnode r[],int n)
{ for(i=2;i<=n;++i)
if(r[i]<r[i-1])
{ r[0]=r[i];
for(j=i-1;r[0]<r[j];--j)
r[j+1]=r[j]; /*记录后移*/
r[j+1]=r[0]; /*插入到正确位置*/
}
}
事例:
折半插入排序
概念:插入的记录的关键字和有序区间的中点处记录的关键字作比较,若二者相等则查找成功,否则可以根据比较的结果来确定下次的查找区间,若插入的记录关键字小于有序序列中点的记录关键字,那么下次查找的区间在中点记录前半部分,否则在中点记录的后半部分;然后在新的查找区间进行同样的查找,经过多次折半查找,直到找到插入位置为止;
算法:
BinsertSort(Recordnode r[],int n)
{
for(i=2;i<=n;++i)
{
r[0]=r[i];
low=1;high=i-1;
while(low<=high)
{
m=( low + high )/2;
if (r[0]<r[m].key) high=m-1; /*插入点在前半区*/
else low=m+1; /*插入点在后半区*/
}
for(j=i-1;j>=high+1;--j)
r[j+1]=r[j]; /*记录后移*/
r[high+1]=r[0]; /*插入*/
}
}
事例:在序列[01 14 19 23 55 84 92]已排好序的基础上,将元素15插入到序列中