文档介绍：第九章排序
本章要求
【教学目的】掌握内排序方法的插入排序;选择排序;交换排序;基数排序;归并排序;排序的存储方式:连续地址、静态链表、索引;稳定的和不稳定的排序方法的判定方法,常见的稳定的排序方法和的不稳定的排序方法。了解外部排序的方法以及外部排序方法的特点。
【教学重点】每种排序方法的算法及算法的性能分析
【教学难点】排序方法的比较及稳定性的确定
第八章查找
一、基本概念
二、插入排序
三、交换排序
四、选择排序
五、归并排序
一、基本概念
排序的目的
排序是为了通过关键字高效的查找相关的记录
排序
就是要调整原文件中的记录顺序,使之按关键字递增(或递减)次序排列起来。其形式化定义描述如下:
输入:n个记录r1,r2,…,rn,其相应的关键字分别为k1,k2,…,kn
输出:rl′,r2′,…,rn′,使得k1′≤k2′≤…≤kn′。
(或k1′≥k2′≥…≥kn′) //有序升序或者降序
一、基本概念
排序的数据结构
待排序的记录采用顺序存储,待排序记录的定义为:
#define MAXSIZE 100 /*假定顺序表的最大长度为100 */
typedef int KeyType; /* 假定关键字类型为整数类型*/
typedef struct {
KeyType key;/* 关键字项*/
OtherType other;/* 其他项*/
}DataType;/* 数据元素类型*/
typedef struct {
DataType r[MAXSIZE +1];
/* r[0]闲置或充当哨兵*/
int length;/* 顺序表长度*/
} SqList;/* 顺序表类型*/
一、基本概念
排序的数据结构
排序的稳定性:若存在关键字相同的多个记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;否则则称这种排序方法是不稳定的。
排序的分类:按是否涉及数据的内、外存交换分类:内排序、外排序。
内部排序方法有:插入排序、选择排序、交换排序、归并排序
排序的效率分析:时间代价和空间代价
二、插入排序
基本思想
通过构建有序序列,将待排序的数据,在已排好序的序列中从后向前扫描,找到其相应位置并进行插入操作。
直接插入排序
二分法插入排序
Shell排序
二、插入排序
直接插入排序
算法思想: 将待插入子序列元素逐步插入到有序子序列中,设有一待排序序列S={r1,r2,r3,…,ri,…,rn},其中{r1,r2,…,ri}(1≤i≤n)是按照关键字{k1≤k2≤…≤ki}有序的子序列,序列{ ri+1,…,rn } 无序。从序列{ ri+1,…,rn }的第一个元素ri+1开始取数据元素,每取一个元素就将其插入到前面的有序序列中,并使插入后的序列有序,直到所有元素插入完成,得到一个有序序列。
二、插入排序
直接插入排序
算法:
void StraightInsertSort(SqList *S)
{ /* 对顺序表s中的s->r[1..length]作直接插入排序*/
for(i=2;i<=S->length;i++)
{ S->r[0]=S->r[i]; /*复制为哨兵*/
j= i-1;
while (S->r[0].key < S->r[j].key)
{ S->r[j+1]=S->r[j];
j-- ;
} /*记录后移*/
S->r[j+1]=S->r[0]; /*插入到正确位置*/
}
}
能不能
改为<=?
二、插入排序
直接插入排序
效率分析:
空间效率:用了一个辅助单元r[0],因此辅助空间为O(1)
时间效率:
最好情形:待排序序列中各数据元素在排序前已按关键字大小排好序,总的比较次数=n-1次,总的移动次数=n-1次,所以时间复杂度为O(n)
最坏情形:待排序序列中各数据元素为逆序状态时,
直接插入排序是稳定的排序算法
二、插入排序
二分插入排序
算法思想:在插入第i个关键码时,前i-1个关键已经有序,可以通过折半的方式找到插入点。
但是,虽然可以更快地找到插入点,但意义不大?
因为,找到插入点后还需要进行移动元素,并没有改变移动元素的次数,因此其时间复杂度并没有发生改变。