第08章 排序.ppt

排序定义——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫~
排序分类
按待排序记录所在位置
内部排序:待排序记录存放在内存
外部排序:排序过程中需对外存进行访问的排序
按排序依据原则
插入排序:直接插入排序、折半插入排序、希尔排序
交换排序:冒泡排序、快速排序
选择排序:简单选择排序、堆排序
归并排序:2-路归并排序
基数排序
基本概念
按排序所需工作量
简单的排序方法:T(n)=O(n²)
先进的排序方法:T(n)=O(logn)
基数排序:T(n)=O()
排序基本操作
比较两个关键字大小
将记录从一个位置移动到另一个位置
存储方式
通常的存储方式有如下三种:
以顺序表作为存储结构,排序过程是对记录本身进行物理重排;
以链表作为存储结构,排序过程中无须移动记录,仅需修改指针即可;
以顺序方式存储待排序的记录,同时建立一个辅助索引表,排序过程中只需对这个辅助表的表目进行物理重排,而不移动记录本身。
教材中算法若无特别声明,均假定按升序排序,采用顺序表作为存储结构。其类型定义如下:
# define n 100
typedef int Keytype;
typedef struct {//记录类型
Keytype key;
Infotype ortherinfo;
}Rectype;
typedef Rectype Seqlist[n+1]; // Seqlist为顺序表类型以存储待排文件,第0个元素通常作为哨兵结点
插入排序
直接插入排序
排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序
例
49 38 65 97 76 13 27
i=2 38 (38 49) 65 97 76 13 27
i=3 65 (38 49 65) 97 76 13 27
i=4 97 (38 49 65 97) 76 13 27
i=5 76 (38 49 65 76 97) 13 27
i=6 13 (13 38 49 65 76 97) 27
i=1 ( )
i=7 (13 38 49 65 76 97) 27
27
j
j
j
j
j
j
97
76
65
49
38
27
(13 27 38 49 65 76 97)
排序结果:
算法评价
时间复杂度
若待排序记录按关键字从小到大排列(正序)
关键字比较次数:
记录移动次数:
若待排序记录按关键字从大到小排列(逆序)
关键字比较次数:
记录移动次数:
若待排序记录是随机的,取平均值
关键字比较次数:
记录移动次数:
T(n)=O(n²)
空间复杂度:S(n)=O(1)
以单链表作为存储结构实现直接插入排序算法。
void llinsertsort(Linklist head)
{//以单链表作为存储结构实现直接插入排序
head;p=head->next;head->next=NULL;
while(p!=NULL)
{pre=head;
while (pre->next!=NULL&&pre->next->data<=p->data)
pre=pre->next;
q=p->next;
p->next=pre->next;pre->next=p;
p=q;
}
}//llinsertsort
折半插入排序
排序过程:用折半查找方法确定插入位置的排序叫~
例
i=1 (30) 13 70 85 39 42 6 20
i=2 13 (13 30) 70 85 39 42 6 20
i=7 6 (6 13 30 39 42 70 85 ) 20
…...
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
m
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
m
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
m
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
i=8 20 (6 13 20 30 39 42 70 85 )
算法描述
算法评价
时间复杂度:T(n)=O(n²)
空间复杂度:S(n)=O(1)
希尔排序(缩小增量法)
排序过程:先取一个正整数d1<n,把所有相隔d1的记录放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止