下一页
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 7单元
排序
下一页
上一页
停止放映
第 2 页
上节内容提要（ 1） —— 查找
? 查找 就是在给定的 DS中找出满足某种条件的结点；若存在这
样的结点, 查找成功；否则, 查找失败 。 （ 找 ）
? 查找表 是一组待查数据元素的集合 。 待找
? 静态查找 是仅仅进行查询和检索操作, 不改变查找表中数据
元素间的逻辑关系的查找 。 （ 不改变元素关系 ）
? 动态查找 是除了进行查询和检索操作外, 还对查找表进行插
入, 删除操作的查找, 动态地改变查找表中数据元素之间的逻辑
关系 。 改变元素关系
? 平均查找长度
与关键字进行比较的平均次数。对含有 n个数据元素的查找表，查
找成功时的平均查找长度为
? Pi 为查找第 i个数据元素的概率
? Ci为查找第 i个数据元素的比较次数。
ASL = ? Pi* Cin
i=1
下一页
上一页
停止放映
第 3 页
上节内容提要（ 2）
– 顺序查找、
– 折半查找 ASL ?
– 分块查找（ 索引顺序 查找 ）
– n为表长,S为块长
– 树表查找（ 二叉排序树 ）、
ASL ?
– 哈希查找 哈希函数常用的构造方法：数字分析法、平
方取中法、折叠法,除留余数法（求模取余法 ）、直接定址法
? 处理冲突有两种方法：开放地址法 （ 线性探测再散列, 二次探测再散
列 ）, 链地址法
i=1n
1
2
n+1n
i=1
n
ASL = ? Pi*Ci = ? (n-i+1) =
下一页
上一页
停止放映
第 4 页
本节内容
通过本单元的学习，了解、掌握有关排序的：
? 基本概念：
– 排序、排序分类、算法稳定性
? 典型的排序算法
– 插入排序、选择排序、交换排序
– 快速排序、归并排序
– 5种排序方法
下一页
上一页
停止放映
第 5 页
一、排序的基本概念
? 1.排序 (Sorting)
? 定义,
? 将记录按 关键字 递增 (递减 )的次序排列起来,
形成新的有序序列,称为排序 。
? 描述,
设 n个记录的序列为 {R1,R2,…,Rn},其相应关
键字序列为 {K1,K2,…,Kn},需确定一种排序
P1,P2,…,Pn,使其相应的关键字满足递增 (升
序 ),或递减 (降序 )的关系,
Kp1 ? Kp2 ?..,?Kpn
或
Kp1 ? Kp2 ?…, ? Kpn
下一页
上一页
停止放映
第 6 页
2.排序分类
? 根据 排序元素所在位置的不同,排序分,
内排序 和 外排序 。
? 内排序
在排序过程中，所有元素调到 内存中进行
的排序,称为内排序。内排序是排序的基
础。
? 外排序
在数据量大的情况下，只能分块排序，但
块与块间不能保证有序。
下一页
上一页
停止放映
第 7 页
内排序方法分类
? 内 排序方法的种类：
– 按排序过程中依据的不同原则分类：
? 插入、选择、归并和基数排序等；
– 按排序过程中所需工作量来区分：
? 简单排序（ O（ n2 ））
? 快速排序（ O（ nlogn））
? 基数排序（ O（ d*n））
? 排序过程中所需进行的操作：
– 比较两个关键字的大小
– 移动记录的位置
2
下一页
上一页
停止放映
第 8 页
? 3.排序算法的稳定性
? 若待排序的序列中，存在多个具有相同关键
字的记录，经过排序，这些记录的相对次序
保持不变，则称该算法是 稳定 的；
? 若经排序后，记录的相对次序发生了改变，
则称该算法是 不稳定 的。
? 4.算法的评价
? 内排序,时间花在比较和移动上，效率用比
较次数来衡量。
? 外排序,时间花在读写外存上，用读 /写外
存的次数来衡量其效率（时间复杂度）。
下一页
上一页
停止放映
第 9 页
? 为简单，这里用顺序存储结构描述待排序
的记录。
? 顺序存储结构（ C语言描述）：
#define N n
struct record {
int key ； /* 关键字项 */
int otherterm； /* 其它项 */
} ；
typedef struct record RECORD；
RECORD file[N+1]； /*RECORD型的 N+1元数组
5.排序算法的 数据结构
下一页
上一页
停止放映
第 10页
二、典型排序算法
?插入 排序
?选择排序
?交换排序（冒泡）
?快速排序
?归并排序
下一页
上一页
停止放映
第 11 页
1.插入 排序（算法 3-5）
? (1)基本思想, 将 n个元素的数列 分为 已有序
和无序两个部分 。
{{a1},{a2,a3,a4,…,an}}
{{a1(1),a2(1)},{a3(1),a4(1) …,an(1)}}
…,..
{{a1(n-1),a2(n-1), … },{an(n-1)}}
每次处理,将无序数列的第一个元素与有序数
列的元素从后往前逐个进行比较,找出插入位
置,将该元素插入到有序数列的合适位置中。
从前往后, 若比 ai小, 则放在 ai前面
从后往前, 若比 ai大, 则放在 ai后边 。
有序 无序
下一页
上一页
停止放映
第 12页
(2)插入 排序算法步骤
? Step1 从有序数列 {a1}和无序数列 {a2,a3,…,an}
开始进行排序 ;
? Step2 处理第 i个元素时 (i=2,3,…,n),数列
{a1,a2,…,ai-1}是已有序的,而数列 {ai,ai+1,…,an}
是无序的 。 用 ai与 ai-1,a i-2,…,a1进行比较,找
出合适的位置将 ai插入 。 （ 从后往前比较 ）
? Step3 重复 Step2,共进行 n-1的插入处理, 数
列全部有序 。 （ 从小到大排序 ）
下一页
上一页
停止放映
第 13页
插入 排序举例
设有数列 { 18,12,10,12,30,16 }
初始状态,{18},{12,10,12,30,16} 比较次数
i=1 {18},{12,10,12,30,16} 1
i=2 {12,18},{10,12,30,16} 2
i=3 {10,12,18},{12,30,16} 2
i=4 {10,12,12,18},{30,16} 1
i=5 {10,12,12,18,30},{16} 3
{10,12,12,16,18,30 }
总计,9 次
下一页
上一页
停止放映
第 14页
(3)插入排序算法实现
insert_sort(item,n )
int *item,n ;
{ int i,j,t ;
for（ i=1； i<n;i++ )/* n-1次循环 */
{ t=item[i]; /* 要插入的元素 */
j = i - 1; /* 有序部分起始位置 */
while(j>=0 && t < item[j])/* 寻找插入位置 */
{ item[j+1]=item[j]; /* 当前元素后移 */
j- - ;
}
item[j+1]=t; /* 插入该元素 */
}
}
下一页
上一页
停止放映
第 15页
插入排序算法主程序
#include,stdio.h”
main( )
{ int i,a[ ]={18,12,10,12,30,16};
printf(“Before sorting\n”);
for(i=0;i<6;i++)
printf(“%3d”,a[i]); printf(“\n”);/*打印
*/
insert_sort(a,6); /* 调用插入排序函数 */
printf(“After sorting\n”);
for(i=0;i<6;i++)
printf(“%3d”,a[i]);/* 排序后打印 */
printf(“\n”);
}
示例
下一页
上一页
停止放映
第 16页
（ 4）算法评价
? 插入算法比较次数和交换次数约
为 n2/2，因此，其时间复杂度
为 O（ n2 ）。
? 该算法是稳定的。
? 1 2 3 4 。。。 N
? 0 1 2 3。。。 N-1
? (n-1+1)*(n-1)/2
下一页
上一页
停止放映
第 17页
2.选择排序（算法 3-6）
? (1)基本思想,每次从待排序的记录中选出关键字
最小 （ 或最大 ） 的记录, 顺序放在已有序的记录
序列的最后 （ 或最前 ） 面, 直到全部数列有序 。
{{a1},{a2,a3,a4,…,an}}
{{a1(1),a2(1)},{a3(1),a4(1)…,an(1)}}
…,..
{{a1(n-1),a2(n-1), … },{an(n-1)}}
有序 无序
下一页
上一页
停止放映
第 18页
(2)选择 排序算法步骤
? Step1 从原始数列 {a1,a2,a3,…,an}开始进行
排序, 比较 n-1次, 从中选出最小关键字, 放在
有序数列中, 形成 {a1},{a2,a3,…,an}有序数
列和无序数列两部分, 完成第 1趟排序 。
? Step2 处理第 i趟排序时 (i=2,3,…,n),从剩下
的 n-i+1个元素中找出最小关键字, 放在有序数
列的后面 。
? Step3 重复 Step2,共进行 n-1趟的选择处理,
数列全部有序 。
? 从大到小排序
下一页
上一页
停止放映
第 19页
选择排序举例
设有数列 { 18,12,10,12,30,16 }
初始状态,{},{18,12,10,12,30,16} 比较次数
i=1 {10},{18,12,12,30,16} 5
i=2 {10,12},{12,18,30,16} 4
i=3 {10,12,12},{18,30,16} 3
i=4 {10,12,12,16},{18,30} 2
i=5 {10,12,12,16,18},{30} 1
总计,15 次
下一页
上一页
停止放映
第 20页
(3)选择排序算法
select_sort(int *item,int count)
{ int i,j,k,t;
for(i=0;i<count-1;++i)/* n-1次循环 */
{ k=i; /* 无序部分第 1个元素 */
t=item[i]; /* 及位置 */
for(j=i+1;j<count;++j)/* 寻找最小值循环 */
{ if(item[j]<t)
{ k=j; t=item[j]; }/* 记录最小值及位置 */
}
item[k]=item[i]; /* 交换最小值与无序 */
item[i]=t; /* 部分第 1个元素位置 */
}
}
下一页
上一页
停止放映
第 21页
选择排序算法主程序
#include "stdio.h"
#define N 6
static int n=0;
main()
{ int a[100],i;
printf("Enter a[i]\n");
for(i=0;i<N;i++)
scanf(“%d”,&a[i]);/* 输入一组数 */
select_sort(a,N);/* 调用选择排序函数 */
for(i=0;i<N;i++)
printf(,%d,,a[i]); /*打印排序后的数组 */
printf("\nn=%d\n",n);
} 示例
下一页
上一页
停止放映
第 22页
(4)算法评价
? 每次选出当前最小关键字，但没有为以后
的选择留下任何信息，比较次数仍为 O
（ n2 ）。
? 选择排序算法是不稳定的。（为什么？）
下一页
上一页
停止放映
第 23页
3、交换排序（冒泡排序）
? （ 1） 指导思想：
两两比较 待排序记录的关键字, 并交换不满足顺
序要求的那些偶对元素, 直到全部数列满足有序
为止 。
? 冒泡排序 （ Bubble sort） 是 基于交换排序的 一
种算法 。 它是依次两两比较待排序元素；若为逆
序 （ 递增或递减 ） 则进行交换, 将待排序元素从
左至右比较一遍称为一趟, 冒泡, 。 每趟冒泡都
将待排序列中的最大关键字交换到最后 （ 或最前 ）
位置 。 直到全部元素有序为止 。
? ? ? … ?
a1 a2 a3 … an-1 an
最大值
下一页
上一页
停止放映
第 24页
（ 2）冒泡排序算法（算法 3-7）
? step1 从待排序队列的前端开始 (a1)两两比较记
录的关键字值,若 ai>ai+1(i=1,2,…,n-1),则交换
ai和 ai+1的位置,直到队列尾部。一趟冒泡处理，
将序列中的最大值交换到 an的位置。
? step2 如法炮制，第 k趟冒泡，从待排序队列的前
端开始 (a1)两两比较 ai和 ai+1（ i=1,2,… n-k)，
并进行交换处理,选出序列中第 k大的关键字值,放
在有序队列的最前端。 (思考：为什么 I=1,… n-k?)
? Step3 最多执行 n-1趟的冒泡处理,序列变为有序。
? 从小到大排序
下一页
上一页
停止放映
第 25页
冒泡排序算法举例
设有数列 { 65,97,76,13,27,49,58 } 比较次数
第 1趟 {65,76,13,27,49,58},{97} 6
第 2趟 {65,13,27,49,58},{76,97} 5
第 3趟 {13,27,49,58},{65,76,97} 4
第 4趟 {13,27,49},{58,65,76,97} 3
第 5趟 {13,27},{49,58,65,76,97} 2
第 6趟 {13},{27,49,58,65,76,97} 1
总计,21 次
下一页
上一页
停止放映
第 26页
（ 3）冒泡排序实现（算法 3-7）
bubble(int *item,int count)
{ int a,b,t;
for(a=1;a<count;++a) /* n-1 趟冒泡处理 */
for(b=1;b<=count-a;b++)/* 每趟 n-i次的比较 */
if(item[b-1]>item[b])/* 若逆序, 则交换 */
{ t=item[b-1]; /* 它们的位置 */
item[b-1]=item[b];
item[b]=t;
}
}
下一页
上一页
停止放映
第 27页
冒泡排序算法 3-7主程序
#define N 7
#include "stdio.h"
main()
{ int s[]={65,97,76,13,27,49,58},i;/*定义数组 */
bubble(s,N); /* 调用选择排序函数 */
printf("The sorted string is:\n");
for(i=0;i<N;i++)
printf(,%d”,s[i]);/*打印排序结果 */
}
示例
下一页
上一页
停止放映
第 28页
（ 4）改进的冒泡排序算法 3-8
? 从上述举例中可以看出, 从第 4趟冒泡起, 序列已有序, 结果
是空跑了 3趟 。 若两次冒泡处理过程中, 没有进行交换, 说明
序列已有序, 则停止交换 。 这就是改进的冒泡算法的处理思
想 。
? 用改进的冒泡算法进行处理, 比较次数有所减少 。
对于数列 { 65,97,76,13,27,49,58 } 比较次数
第 1趟 {65,76,13,27,49,58},{97} 6
第 2趟 {65,13,27,49,58},{76,97} 5
第 3趟 {13,27,49,58},{65,76,97} 4
第 4趟 {13,27,49},{58,65,76,97} 3
总计,18 次
下一页
上一页
停止放映
第 29页
（ 4）改进的冒泡排序算法 3-8
bubble_a(int *item,int count)
{ int a,b,t,c;
for(a=1;a<count;++a) /* n-1趟的循环 */
{ c=1; /* 设置交换标志 */
for(b=1;b<=count-a;b++)/* n-1趟处理 */
{ if(item[b-1]>item[b])/* 若逆序, 则 */
{ t=item[b-1]; /* 交换位置 */
item[b-1]=item[b];
item[b]=t;
c=0; } /* 若有交换, 则 */
} /* 改变交换标志 */
if(c) break; /* 若没有交换, 则 */
} /* 退出处理 */
} 示例
下一页
上一页
停止放映
第 30页
（ 5）算法评价
? 若待排序列有序 (递增或递减 ),则只需进
行一趟冒泡处理即可 ;若反序，则需进行
n-1趟的冒泡处理。在最坏的情况下,冒泡
算法的时间复杂度是 O( n2 )。
? 当待排序列基本有序时，采用冒泡排序法
效果较好。
? 冒泡排序算法是 稳定的 。
下一页
上一页
停止放映
第 31页
4、快速排序
? 快速排序法是对冒泡排序法的一种改
进, 也是基于交换排序的一种算法 。
因此, 被称为, 分区交换排序, 。
? 快 速 排 序 法 是一 位 计 算机 科 学家
C.A.R.Hoare推出并命名的 。 曾被认
为是最好的一种排序方法 。
下一页
上一页
停止放映
第 32页
（ 1）快速排序基本思想
? 在待排序序列中按某种方法选取一个元素 K,以它为分
界点, 用交换的方法将序列分为两个部分：比该值小的
放在左边, 否则在右边 。 形成
{左子序列 }K{右子序列 }
再分别对左, 右两部分实施上述分解过程, 直到各子
序列长度为 1,即有序为止 。
? 分界点元素值 K的选取方法不同, 将构成不同的排序法,
也将影响排序的效率：
– 取左边第 1个元素为分界点；
– 取中点 A[（ left+right） /2]为分界点；
– 选取最大和最小值的平均值为分界点等 。
? 设有序列 {a1,a2,…,An},选取中点元素 K为分界点,从
序列两头分别与 K进行比较,小于 K的元素交换到左边,否
则交换到右边 ;一趟处理后,左边子序列的元素均小于分
界点值 K,右边子序列元素均大于等于 K值 。
下一页
上一页
停止放映
第 33页
（ 2）快速排序算法（算法 3-9）
? Step1 分别从两端开始, 指针 i指向第一个元素
A[left],指针 j指向最后一个元素 A[right],分界
点取 K ；
? Step2 循环 （ i?j）
– 从右边开始进行比较：
若 K ? A[j],则将 A[j]交换到左边；
若 K 〈 A[j], 则 j=j-1,再进行比较；
– 从左边开始进行比较：
若 K 〉 A[i],则 i=i+1,再进行比较；
若 K ? A[i],则将 A[i]交换到右边 。
– 当 i=j时, 一次分解操作完成 。
? Step3 在对分解出的左, 右两个子序列按上述步骤
继续进行分解, 直到子序列长度为 1（ 不可再分 ） 为
止, 也即序列全部有序 。
下一页
上一页
停止放映
第 34页
快速排序算法举例
对于数列 {49,38,60,90,70,15,30,49}，
采用中点分界法：
初始状态, 49 38 60 90 70 15 30 49 比较次数
第 1趟
49 38 60 90 70 15 30 49
49 38 60 90 70 15 30 49 5（ i4,j1）
49 38 60 49 70 15 30 90
5（ i4,j1）
{ 49 38 60 49 70 15 30 } 90
小计,10
i
k = 90
j
i j
ji
下一页
上一页
停止放映
第 35页
快速排序算法举例（续一）
初始状态, 49 38 60 49 70 15 30 比较次数
第 2趟 49 38 60 49 70 15 30
2（ i1,j1）
30 38 60 49 70 15 49
30 38 60 49 70 15 49
30 38 15 49 70 60 49
{ 30 38 15}49{ 70 60 49 } 小计,8
i j
k = 49
ji
i j
3（ i2,j1）
i j
3（ i1,j2）
下一页
上一页
停止放映
第 36页
快速排序算法举例（续二）
初始状态, 30 38 15 比较次数
第 3趟 30 38 15 3（ i2,j1）
{ 30,15 } 38 小计,3
第 4趟 70 60 49 2（ i1,j1）
49 60 70 2（ i1,j1）
小计,4
k = 38
i j
ji
k = 60
ji
ji
下一页
上一页
停止放映
第 37页
快速排序算法举例（续三）
初始状态, 30 15 比较次数
第 5趟 30 15 2（ i1,j1）
15 30 小计,2
最后状态：
{ 15 30 38 49 49 60 70 90 } 总计,27
k = 30
i j
下一页
上一页
停止放映
第 38页
快速排序算法 3-9
quick_sort(item,count)
int *item,count;
{
qs(item,0,count-1);
}
下一页
上一页
停止放映
第 39页
(3)快速排序 ----子函数 qs（）
qs(int *item,int left,int right)
{ int i,j,x,y,k; i=left; j=right;
x=item[(left+right)/2]; /* 计算中点位置 */
do{ /* i≤j 的循环处理 */
while(item[i]<x && i<right )
i++ ； /* 确定 i点交换位置 */
while(x<item[j] && j>left)
j--; /* 确定 j点交换位置 */
if(i<=j) /* 如果 i,j位置合法，则交换 */
{ y=item[i]; /* A[i]和 A[j]的位置 */
item[i]=item[j];
item[j]=y; i++; j--;
}
} while(i<=j);
if(left<j) qs(item,left,j); /* 对分割出的左部再处理 */
if(i<right) qs(item,i,right); /* 对分割出的右部再处理 */
}
下一页
上一页
停止放映
第 40页
快速排序算法 3-9主程序
#include "stdio.h"
main( )
{ int s[]={49,38,60,90,70,15,30,49},n,i;
quick_sort(s,8); /* 调用快速排序函数 */
printf("The sorted string is,\n");
for( n=0; n < 8; n++ )
printf(" %d",s[n]);
printf(“\n”);
}
示例
下一页
上一页
停止放映
第 41页
(4)算法评价
? 分界点选取方法不同，排序效果差异很大；
? 比较次数为 nlogn，即为,O（ nlogn），交换
次数为 n/6*logn。
? 快速排序算法是 不稳定的 。
下一页
上一页
停止放映
第 42页
5、归并排序
? （ 1） 思想
? 归并 （ Merge） 排序法是将两个 （ 或两个以上 ）
有序表合并成一个新的有序表；即把待排序序
列分为若干个子序列, 每个子序列是有序的 。
然后再把有序子序列合并为整体有序序列 。
? 将已有序的子序列合并，得到完全有序的序列；
? 即先使每个子序列有序，再使子序列段间有序。
? 若将两个有序表合并成一个有序表，称为 2-路
归并 。
下一页
上一页
停止放映
第 43页
（ 2）归并排序（算法 3-12）
? Step1 把待排序的 n个记录看作是长度为 1
的有序序列 。 将相邻子序列两两归并为长
度为 2的有序序列；
? Step2 把得到的 n/2个长度为 2的有序子序
列再归并为长度为 2*2 的有序序列；
? Step3 按 Step2的方式, 重复对相邻有序
子序列进行归并操作, 直到成为一个有序
序列为止 。
下一页
上一页
停止放映
第 44页
归并排序算法简述
? 设有待排序数列 {49,38,65,97,76,12,27}，
? 第一趟处理, 先将每个元素看成是有序的子序列, 即
[49] [38] [65] [97] [76] [12] [27]
? 第二趟处理, 将长度为 1的子序列合并为长度为 2的子
序列, 即
[38, 49] [65,97] [12, 76] [ 27 ]
? 第三趟处理，将长度为 2的子序列合并为长度为 4的子
序列，即
[38, 49, 65,97] [12, 27,76 ]
? 第四趟处理，将长度为 4的子序列合并为长度为 8的序
列，即
[12,27,38, 49, 65,76,97]
? 提示：将归并过程中贡献出的元素，送进工作单元（ SWAP[m]）中。
下一页
上一页
停止放映
第 45页
（ 2）归并排序算法 3-12说明
? 设有两个有序序列 L1和 L2,它们顺序存放在数组 X[l1]，
X[l1+1],…,X[u1]和 X[l2],X[l2+1],…,X[u2]中,其中,
l2=u1+1;
? 设置三个变量 i,j,m,其中 i,j分别表示序列 L1和
L2中当前要比较的记录的位置；初值 i=l1,j=l2。 m
表示 Swap数组中当前位置, 初值 m=l1。
? 归并时, 反复比较 X[i]和 X[j]：
– 若 X[i]?X[j] 则 X[i]送 Swap[m],i++； m++；
– 若 X[i]>X[j] 则 X[j]送 Swap[m],j++； m++；
? 当序列 L1或 L2的全部记录已归并到数组 X中,即 i=u1+1,
或 j=u2+1时,
比较结束,然后将另一个序列中剩余的所有记录依此放
回到数组 Swap中,完成 L1和 L2的合并 。
下一页
上一页
停止放映
第 46页
归并排序算法举例
设有数列 {6,202,100,301,38,8,1}，
初始状态,[6] [202] [100] [301] [38] [8] [1]
比较次数
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
i=3 [ 1 6 8 38 100 202 301 ] 4
总计,11
SWAP数组：
SWAP数组：
1006
301
202 1 8 38
1 6 8 38 100 202
301
下一页
上一页
停止放映
第 47页
（ 3）归并排序算法 3-12（实现）
merge_sort(int *x,int n)
{
int i,k,l;
int swap[N];
k=1;
while(k<n) /* 步长从 1到 2*m的循环
*/
{
merge(x,swap,k,n); //k 待归并的子序列长度
for(i=0;i<n;i++) /* 将 数列 从 SWAP放回 X中
*/
x[i]=swap[i];
k=2*k; /* 序 列 长 度 加 倍
*/
}
}
X:待排数组
N：元素个数
下一页
上一页
停止放映
第 48页
归并排序算法 3-12(续一）
merge(int *x,int *swap,int k,int n)
{ int i,j,l1,l2,u1,u2,m; l1=0; m=0;
while(l1+k<n)
{ l2=l1+k; u1=l2-1; u2=(l2+k-1<n)?l2+k-1:n-1;
for(i=l1,j=l2;i<=u1&&j<=u2;m++)
{ if(x[i]<=x[j])
{ swap[m]=x[i]; i++; }/* x[i]贡献出 */
else
{ swap[m]=x[j]; j++; }/* x[j]贡献出 */
}
while(i<=u1) /* 将序列 1中剩余元素顺序放回 SWAP中 */
{ swap[m]=x[i]; m++; i++; }
while(j<=u2)/* 将序列 2中剩余元素顺序放回 SWAP中 */
{ swap[m]=x[j]; m++; j++; }
l1=u2+1; /* 改变子序列 */
}/*将原始序列中剩余的, 不足一组的记录顺序放到 SWAP中 */
for(i=l1;i<n;i++,m++) swap[m]=x[i];
}
下一页
上一页
停止放映
第 49页
归并排序算法 3-12主程序
#define N 7
main( )
{ int s[N],n,i;
printf("Enter a[i]\n");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
merge_sort(a,N); /* 调用归并排序函数 */
printf("The sorted string is,\n");
for( n=0; n < N; n++ )
printf(" %d",s[n]);
printf(“\n”);
} 示例
下一页
上一页
停止放映
第 50页
(4)算法评价
? 空间复杂度为 O（ n ），
用辅助空间 L1,L2、（ Swap）
? 时间复杂度为 O（ nlogn）
? 2-路归并排序算法是 稳定的 。
下一页
上一页
停止放映
第 51页
6.希尔（ Shell）排序
? (1)思想：
? 希尔排序是一种快速排序法，出自 D.L.Shell,
? 指导思想：
仍采用插入法，排序过程通过调换并移动数据
项来实现。每次比较 指定间距的 两个数据项，
若左边的值小于右边的值，则交换它们的位置。
间距 d按给定公式 减少,di+1 =（ di +1） /2,
直到 d等于 1为止。 d取 {9,5,3,2,1}。
下一页
上一页
停止放映
第 52页
（ 2）算法步骤
? Step1 将 n个元素个数列分为 n个部分，元
素比较间距为 d。
? step2 在第 i步，两元素比较的间距取
di+1 =（ di +1） /2 {9,5,3,2,1}
若 ai+1 > ai,则交换它们的位置。
? Step3 重复上述步骤，直到 dK = 1。
下一页
上一页
停止放映
第 53页
希尔排序举例
设有数列,f d a c b e”,
第 1趟 d=5 f d a c b e 得到 e d a c b f
第 2趟 d=3 e d a c b f 得到 c b a e d f
第 3趟 d=2 c b a e d f 得到 a b c e d f
第 4趟 d=1 a b c e d f 得到 a d c d e f
下一页
上一页
停止放映
第 54页
（ 3） SHELL排序子函数
shell(char *item,int count)
{ int i,j,k,s,w; char x; int a[]={9,5,3,2,1};
for(w=0;w<5;w++)/* 不同步长的 5次循环 */
{ k=a[w];s=-k; //k为步长
for(i=k;i<count;i++)
{ x=item[i]; j=i-k;
if(s==0)
{ s++; item[s]=x; }
while(x<item[j]&&j>=0&&j<=count)
{ item[j+k]=item[j]; j=j-k; }
item[j+k]=x;
}
}
}
下一页
上一页
停止放映
第 55页
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
? 一趟比较示意图标 k=5
下一页
上一页
停止放映
第 56页
SHELL排序主函数
#include "stdio.h"
main()
{ char s[80];int l;
printf("Enter a string:");
gets(s);
l=strlen(s);
shell(s,l); /* 调用 shell函数 */
printf("The sorted string is,%s\n",s);
} 示例
下一页
上一页
停止放映
第 57页
上机实验要求
? 实验内容：
1、实现二叉排序树的查找
2、用前、中、后序法遍历二叉排序树
? 实验要求：
1、写出算法分析和操作步骤
2、设计、调试、上机通过上述程序；
3、将上述 4个程序作为作业提交
4、程序必须是上机通过的
5、实验结果的成绩将记入考试成绩中
? 详见“实验指导一”
下一页
上一页
停止放映
第 58页
作业、思考题
1、第 3章作业
思考,第 1,8,9,12题
作业：给定数列 {503,87,512,61,908、
170,897,275,653,426}，计算采用下列
算法的比较次数：
插入、选择、冒泡、快速、归并排序。
2、作业要求：
– 提交数字化作业，按要求提交到指定路径下
– 用 C语言描述
– 作业命名方式为：
学号,章数 _序号
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 7单元
排序
下一页
上一页
停止放映
第 2 页
上节内容提要（ 1） —— 查找
? 查找 就是在给定的 DS中找出满足某种条件的结点；若存在这
样的结点, 查找成功；否则, 查找失败 。 （ 找 ）
? 查找表 是一组待查数据元素的集合 。 待找
? 静态查找 是仅仅进行查询和检索操作, 不改变查找表中数据
元素间的逻辑关系的查找 。 （ 不改变元素关系 ）
? 动态查找 是除了进行查询和检索操作外, 还对查找表进行插
入, 删除操作的查找, 动态地改变查找表中数据元素之间的逻辑
关系 。 改变元素关系
? 平均查找长度
与关键字进行比较的平均次数。对含有 n个数据元素的查找表，查
找成功时的平均查找长度为
? Pi 为查找第 i个数据元素的概率
? Ci为查找第 i个数据元素的比较次数。
ASL = ? Pi* Cin
i=1
下一页
上一页
停止放映
第 3 页
上节内容提要（ 2）
– 顺序查找、
– 折半查找 ASL ?
– 分块查找（ 索引顺序 查找 ）
– n为表长,S为块长
– 树表查找（ 二叉排序树 ）、
ASL ?
– 哈希查找 哈希函数常用的构造方法：数字分析法、平
方取中法、折叠法,除留余数法（求模取余法 ）、直接定址法
? 处理冲突有两种方法：开放地址法 （ 线性探测再散列, 二次探测再散
列 ）, 链地址法
i=1n
1
2
n+1n
i=1
n
ASL = ? Pi*Ci = ? (n-i+1) =
下一页
上一页
停止放映
第 4 页
本节内容
通过本单元的学习，了解、掌握有关排序的：
? 基本概念：
– 排序、排序分类、算法稳定性
? 典型的排序算法
– 插入排序、选择排序、交换排序
– 快速排序、归并排序
– 5种排序方法
下一页
上一页
停止放映
第 5 页
一、排序的基本概念
? 1.排序 (Sorting)
? 定义,
? 将记录按 关键字 递增 (递减 )的次序排列起来,
形成新的有序序列,称为排序 。
? 描述,
设 n个记录的序列为 {R1,R2,…,Rn},其相应关
键字序列为 {K1,K2,…,Kn},需确定一种排序
P1,P2,…,Pn,使其相应的关键字满足递增 (升
序 ),或递减 (降序 )的关系,
Kp1 ? Kp2 ?..,?Kpn
或
Kp1 ? Kp2 ?…, ? Kpn
下一页
上一页
停止放映
第 6 页
2.排序分类
? 根据 排序元素所在位置的不同,排序分,
内排序 和 外排序 。
? 内排序
在排序过程中，所有元素调到 内存中进行
的排序,称为内排序。内排序是排序的基
础。
? 外排序
在数据量大的情况下，只能分块排序，但
块与块间不能保证有序。
下一页
上一页
停止放映
第 7 页
内排序方法分类
? 内 排序方法的种类：
– 按排序过程中依据的不同原则分类：
? 插入、选择、归并和基数排序等；
– 按排序过程中所需工作量来区分：
? 简单排序（ O（ n2 ））
? 快速排序（ O（ nlogn））
? 基数排序（ O（ d*n））
? 排序过程中所需进行的操作：
– 比较两个关键字的大小
– 移动记录的位置
2
下一页
上一页
停止放映
第 8 页
? 3.排序算法的稳定性
? 若待排序的序列中，存在多个具有相同关键
字的记录，经过排序，这些记录的相对次序
保持不变，则称该算法是 稳定 的；
? 若经排序后，记录的相对次序发生了改变，
则称该算法是 不稳定 的。
? 4.算法的评价
? 内排序,时间花在比较和移动上，效率用比
较次数来衡量。
? 外排序,时间花在读写外存上，用读 /写外
存的次数来衡量其效率（时间复杂度）。
下一页
上一页
停止放映
第 9 页
? 为简单，这里用顺序存储结构描述待排序
的记录。
? 顺序存储结构（ C语言描述）：
#define N n
struct record {
int key ； /* 关键字项 */
int otherterm； /* 其它项 */
} ；
typedef struct record RECORD；
RECORD file[N+1]； /*RECORD型的 N+1元数组
5.排序算法的 数据结构
下一页
上一页
停止放映
第 10页
二、典型排序算法
?插入 排序
?选择排序
?交换排序（冒泡）
?快速排序
?归并排序
下一页
上一页
停止放映
第 11 页
1.插入 排序（算法 3-5）
? (1)基本思想, 将 n个元素的数列 分为 已有序
和无序两个部分 。
{{a1},{a2,a3,a4,…,an}}
{{a1(1),a2(1)},{a3(1),a4(1) …,an(1)}}
…,..
{{a1(n-1),a2(n-1), … },{an(n-1)}}
每次处理,将无序数列的第一个元素与有序数
列的元素从后往前逐个进行比较,找出插入位
置,将该元素插入到有序数列的合适位置中。
从前往后, 若比 ai小, 则放在 ai前面
从后往前, 若比 ai大, 则放在 ai后边 。
有序 无序
下一页
上一页
停止放映
第 12页
(2)插入 排序算法步骤
? Step1 从有序数列 {a1}和无序数列 {a2,a3,…,an}
开始进行排序 ;
? Step2 处理第 i个元素时 (i=2,3,…,n),数列
{a1,a2,…,ai-1}是已有序的,而数列 {ai,ai+1,…,an}
是无序的 。 用 ai与 ai-1,a i-2,…,a1进行比较,找
出合适的位置将 ai插入 。 （ 从后往前比较 ）
? Step3 重复 Step2,共进行 n-1的插入处理, 数
列全部有序 。 （ 从小到大排序 ）
下一页
上一页
停止放映
第 13页
插入 排序举例
设有数列 { 18,12,10,12,30,16 }
初始状态,{18},{12,10,12,30,16} 比较次数
i=1 {18},{12,10,12,30,16} 1
i=2 {12,18},{10,12,30,16} 2
i=3 {10,12,18},{12,30,16} 2
i=4 {10,12,12,18},{30,16} 1
i=5 {10,12,12,18,30},{16} 3
{10,12,12,16,18,30 }
总计,9 次
下一页
上一页
停止放映
第 14页
(3)插入排序算法实现
insert_sort(item,n )
int *item,n ;
{ int i,j,t ;
for（ i=1； i<n;i++ )/* n-1次循环 */
{ t=item[i]; /* 要插入的元素 */
j = i - 1; /* 有序部分起始位置 */
while(j>=0 && t < item[j])/* 寻找插入位置 */
{ item[j+1]=item[j]; /* 当前元素后移 */
j- - ;
}
item[j+1]=t; /* 插入该元素 */
}
}
下一页
上一页
停止放映
第 15页
插入排序算法主程序
#include,stdio.h”
main( )
{ int i,a[ ]={18,12,10,12,30,16};
printf(“Before sorting\n”);
for(i=0;i<6;i++)
printf(“%3d”,a[i]); printf(“\n”);/*打印
*/
insert_sort(a,6); /* 调用插入排序函数 */
printf(“After sorting\n”);
for(i=0;i<6;i++)
printf(“%3d”,a[i]);/* 排序后打印 */
printf(“\n”);
}
示例
下一页
上一页
停止放映
第 16页
（ 4）算法评价
? 插入算法比较次数和交换次数约
为 n2/2，因此，其时间复杂度
为 O（ n2 ）。
? 该算法是稳定的。
? 1 2 3 4 。。。 N
? 0 1 2 3。。。 N-1
? (n-1+1)*(n-1)/2
下一页
上一页
停止放映
第 17页
2.选择排序（算法 3-6）
? (1)基本思想,每次从待排序的记录中选出关键字
最小 （ 或最大 ） 的记录, 顺序放在已有序的记录
序列的最后 （ 或最前 ） 面, 直到全部数列有序 。
{{a1},{a2,a3,a4,…,an}}
{{a1(1),a2(1)},{a3(1),a4(1)…,an(1)}}
…,..
{{a1(n-1),a2(n-1), … },{an(n-1)}}
有序 无序
下一页
上一页
停止放映
第 18页
(2)选择 排序算法步骤
? Step1 从原始数列 {a1,a2,a3,…,an}开始进行
排序, 比较 n-1次, 从中选出最小关键字, 放在
有序数列中, 形成 {a1},{a2,a3,…,an}有序数
列和无序数列两部分, 完成第 1趟排序 。
? Step2 处理第 i趟排序时 (i=2,3,…,n),从剩下
的 n-i+1个元素中找出最小关键字, 放在有序数
列的后面 。
? Step3 重复 Step2,共进行 n-1趟的选择处理,
数列全部有序 。
? 从大到小排序
下一页
上一页
停止放映
第 19页
选择排序举例
设有数列 { 18,12,10,12,30,16 }
初始状态,{},{18,12,10,12,30,16} 比较次数
i=1 {10},{18,12,12,30,16} 5
i=2 {10,12},{12,18,30,16} 4
i=3 {10,12,12},{18,30,16} 3
i=4 {10,12,12,16},{18,30} 2
i=5 {10,12,12,16,18},{30} 1
总计,15 次
下一页
上一页
停止放映
第 20页
(3)选择排序算法
select_sort(int *item,int count)
{ int i,j,k,t;
for(i=0;i<count-1;++i)/* n-1次循环 */
{ k=i; /* 无序部分第 1个元素 */
t=item[i]; /* 及位置 */
for(j=i+1;j<count;++j)/* 寻找最小值循环 */
{ if(item[j]<t)
{ k=j; t=item[j]; }/* 记录最小值及位置 */
}
item[k]=item[i]; /* 交换最小值与无序 */
item[i]=t; /* 部分第 1个元素位置 */
}
}
下一页
上一页
停止放映
第 21页
选择排序算法主程序
#include "stdio.h"
#define N 6
static int n=0;
main()
{ int a[100],i;
printf("Enter a[i]\n");
for(i=0;i<N;i++)
scanf(“%d”,&a[i]);/* 输入一组数 */
select_sort(a,N);/* 调用选择排序函数 */
for(i=0;i<N;i++)
printf(,%d,,a[i]); /*打印排序后的数组 */
printf("\nn=%d\n",n);
} 示例
下一页
上一页
停止放映
第 22页
(4)算法评价
? 每次选出当前最小关键字，但没有为以后
的选择留下任何信息，比较次数仍为 O
（ n2 ）。
? 选择排序算法是不稳定的。（为什么？）
下一页
上一页
停止放映
第 23页
3、交换排序（冒泡排序）
? （ 1） 指导思想：
两两比较 待排序记录的关键字, 并交换不满足顺
序要求的那些偶对元素, 直到全部数列满足有序
为止 。
? 冒泡排序 （ Bubble sort） 是 基于交换排序的 一
种算法 。 它是依次两两比较待排序元素；若为逆
序 （ 递增或递减 ） 则进行交换, 将待排序元素从
左至右比较一遍称为一趟, 冒泡, 。 每趟冒泡都
将待排序列中的最大关键字交换到最后 （ 或最前 ）
位置 。 直到全部元素有序为止 。
? ? ? … ?
a1 a2 a3 … an-1 an
最大值
下一页
上一页
停止放映
第 24页
（ 2）冒泡排序算法（算法 3-7）
? step1 从待排序队列的前端开始 (a1)两两比较记
录的关键字值,若 ai>ai+1(i=1,2,…,n-1),则交换
ai和 ai+1的位置,直到队列尾部。一趟冒泡处理，
将序列中的最大值交换到 an的位置。
? step2 如法炮制，第 k趟冒泡，从待排序队列的前
端开始 (a1)两两比较 ai和 ai+1（ i=1,2,… n-k)，
并进行交换处理,选出序列中第 k大的关键字值,放
在有序队列的最前端。 (思考：为什么 I=1,… n-k?)
? Step3 最多执行 n-1趟的冒泡处理,序列变为有序。
? 从小到大排序
下一页
上一页
停止放映
第 25页
冒泡排序算法举例
设有数列 { 65,97,76,13,27,49,58 } 比较次数
第 1趟 {65,76,13,27,49,58},{97} 6
第 2趟 {65,13,27,49,58},{76,97} 5
第 3趟 {13,27,49,58},{65,76,97} 4
第 4趟 {13,27,49},{58,65,76,97} 3
第 5趟 {13,27},{49,58,65,76,97} 2
第 6趟 {13},{27,49,58,65,76,97} 1
总计,21 次
下一页
上一页
停止放映
第 26页
（ 3）冒泡排序实现（算法 3-7）
bubble(int *item,int count)
{ int a,b,t;
for(a=1;a<count;++a) /* n-1 趟冒泡处理 */
for(b=1;b<=count-a;b++)/* 每趟 n-i次的比较 */
if(item[b-1]>item[b])/* 若逆序, 则交换 */
{ t=item[b-1]; /* 它们的位置 */
item[b-1]=item[b];
item[b]=t;
}
}
下一页
上一页
停止放映
第 27页
冒泡排序算法 3-7主程序
#define N 7
#include "stdio.h"
main()
{ int s[]={65,97,76,13,27,49,58},i;/*定义数组 */
bubble(s,N); /* 调用选择排序函数 */
printf("The sorted string is:\n");
for(i=0;i<N;i++)
printf(,%d”,s[i]);/*打印排序结果 */
}
示例
下一页
上一页
停止放映
第 28页
（ 4）改进的冒泡排序算法 3-8
? 从上述举例中可以看出, 从第 4趟冒泡起, 序列已有序, 结果
是空跑了 3趟 。 若两次冒泡处理过程中, 没有进行交换, 说明
序列已有序, 则停止交换 。 这就是改进的冒泡算法的处理思
想 。
? 用改进的冒泡算法进行处理, 比较次数有所减少 。
对于数列 { 65,97,76,13,27,49,58 } 比较次数
第 1趟 {65,76,13,27,49,58},{97} 6
第 2趟 {65,13,27,49,58},{76,97} 5
第 3趟 {13,27,49,58},{65,76,97} 4
第 4趟 {13,27,49},{58,65,76,97} 3
总计,18 次
下一页
上一页
停止放映
第 29页
（ 4）改进的冒泡排序算法 3-8
bubble_a(int *item,int count)
{ int a,b,t,c;
for(a=1;a<count;++a) /* n-1趟的循环 */
{ c=1; /* 设置交换标志 */
for(b=1;b<=count-a;b++)/* n-1趟处理 */
{ if(item[b-1]>item[b])/* 若逆序, 则 */
{ t=item[b-1]; /* 交换位置 */
item[b-1]=item[b];
item[b]=t;
c=0; } /* 若有交换, 则 */
} /* 改变交换标志 */
if(c) break; /* 若没有交换, 则 */
} /* 退出处理 */
} 示例
下一页
上一页
停止放映
第 30页
（ 5）算法评价
? 若待排序列有序 (递增或递减 ),则只需进
行一趟冒泡处理即可 ;若反序，则需进行
n-1趟的冒泡处理。在最坏的情况下,冒泡
算法的时间复杂度是 O( n2 )。
? 当待排序列基本有序时，采用冒泡排序法
效果较好。
? 冒泡排序算法是 稳定的 。
下一页
上一页
停止放映
第 31页
4、快速排序
? 快速排序法是对冒泡排序法的一种改
进, 也是基于交换排序的一种算法 。
因此, 被称为, 分区交换排序, 。
? 快 速 排 序 法 是一 位 计 算机 科 学家
C.A.R.Hoare推出并命名的 。 曾被认
为是最好的一种排序方法 。
下一页
上一页
停止放映
第 32页
（ 1）快速排序基本思想
? 在待排序序列中按某种方法选取一个元素 K,以它为分
界点, 用交换的方法将序列分为两个部分：比该值小的
放在左边, 否则在右边 。 形成
{左子序列 }K{右子序列 }
再分别对左, 右两部分实施上述分解过程, 直到各子
序列长度为 1,即有序为止 。
? 分界点元素值 K的选取方法不同, 将构成不同的排序法,
也将影响排序的效率：
– 取左边第 1个元素为分界点；
– 取中点 A[（ left+right） /2]为分界点；
– 选取最大和最小值的平均值为分界点等 。
? 设有序列 {a1,a2,…,An},选取中点元素 K为分界点,从
序列两头分别与 K进行比较,小于 K的元素交换到左边,否
则交换到右边 ;一趟处理后,左边子序列的元素均小于分
界点值 K,右边子序列元素均大于等于 K值 。
下一页
上一页
停止放映
第 33页
（ 2）快速排序算法（算法 3-9）
? Step1 分别从两端开始, 指针 i指向第一个元素
A[left],指针 j指向最后一个元素 A[right],分界
点取 K ；
? Step2 循环 （ i?j）
– 从右边开始进行比较：
若 K ? A[j],则将 A[j]交换到左边；
若 K 〈 A[j], 则 j=j-1,再进行比较；
– 从左边开始进行比较：
若 K 〉 A[i],则 i=i+1,再进行比较；
若 K ? A[i],则将 A[i]交换到右边 。
– 当 i=j时, 一次分解操作完成 。
? Step3 在对分解出的左, 右两个子序列按上述步骤
继续进行分解, 直到子序列长度为 1（ 不可再分 ） 为
止, 也即序列全部有序 。
下一页
上一页
停止放映
第 34页
快速排序算法举例
对于数列 {49,38,60,90,70,15,30,49}，
采用中点分界法：
初始状态, 49 38 60 90 70 15 30 49 比较次数
第 1趟
49 38 60 90 70 15 30 49
49 38 60 90 70 15 30 49 5（ i4,j1）
49 38 60 49 70 15 30 90
5（ i4,j1）
{ 49 38 60 49 70 15 30 } 90
小计,10
i
k = 90
j
i j
ji
下一页
上一页
停止放映
第 35页
快速排序算法举例（续一）
初始状态, 49 38 60 49 70 15 30 比较次数
第 2趟 49 38 60 49 70 15 30
2（ i1,j1）
30 38 60 49 70 15 49
30 38 60 49 70 15 49
30 38 15 49 70 60 49
{ 30 38 15}49{ 70 60 49 } 小计,8
i j
k = 49
ji
i j
3（ i2,j1）
i j
3（ i1,j2）
下一页
上一页
停止放映
第 36页
快速排序算法举例（续二）
初始状态, 30 38 15 比较次数
第 3趟 30 38 15 3（ i2,j1）
{ 30,15 } 38 小计,3
第 4趟 70 60 49 2（ i1,j1）
49 60 70 2（ i1,j1）
小计,4
k = 38
i j
ji
k = 60
ji
ji
下一页
上一页
停止放映
第 37页
快速排序算法举例（续三）
初始状态, 30 15 比较次数
第 5趟 30 15 2（ i1,j1）
15 30 小计,2
最后状态：
{ 15 30 38 49 49 60 70 90 } 总计,27
k = 30
i j
下一页
上一页
停止放映
第 38页
快速排序算法 3-9
quick_sort(item,count)
int *item,count;
{
qs(item,0,count-1);
}
下一页
上一页
停止放映
第 39页
(3)快速排序 ----子函数 qs（）
qs(int *item,int left,int right)
{ int i,j,x,y,k; i=left; j=right;
x=item[(left+right)/2]; /* 计算中点位置 */
do{ /* i≤j 的循环处理 */
while(item[i]<x && i<right )
i++ ； /* 确定 i点交换位置 */
while(x<item[j] && j>left)
j--; /* 确定 j点交换位置 */
if(i<=j) /* 如果 i,j位置合法，则交换 */
{ y=item[i]; /* A[i]和 A[j]的位置 */
item[i]=item[j];
item[j]=y; i++; j--;
}
} while(i<=j);
if(left<j) qs(item,left,j); /* 对分割出的左部再处理 */
if(i<right) qs(item,i,right); /* 对分割出的右部再处理 */
}
下一页
上一页
停止放映
第 40页
快速排序算法 3-9主程序
#include "stdio.h"
main( )
{ int s[]={49,38,60,90,70,15,30,49},n,i;
quick_sort(s,8); /* 调用快速排序函数 */
printf("The sorted string is,\n");
for( n=0; n < 8; n++ )
printf(" %d",s[n]);
printf(“\n”);
}
示例
下一页
上一页
停止放映
第 41页
(4)算法评价
? 分界点选取方法不同，排序效果差异很大；
? 比较次数为 nlogn，即为,O（ nlogn），交换
次数为 n/6*logn。
? 快速排序算法是 不稳定的 。
下一页
上一页
停止放映
第 42页
5、归并排序
? （ 1） 思想
? 归并 （ Merge） 排序法是将两个 （ 或两个以上 ）
有序表合并成一个新的有序表；即把待排序序
列分为若干个子序列, 每个子序列是有序的 。
然后再把有序子序列合并为整体有序序列 。
? 将已有序的子序列合并，得到完全有序的序列；
? 即先使每个子序列有序，再使子序列段间有序。
? 若将两个有序表合并成一个有序表，称为 2-路
归并 。
下一页
上一页
停止放映
第 43页
（ 2）归并排序（算法 3-12）
? Step1 把待排序的 n个记录看作是长度为 1
的有序序列 。 将相邻子序列两两归并为长
度为 2的有序序列；
? Step2 把得到的 n/2个长度为 2的有序子序
列再归并为长度为 2*2 的有序序列；
? Step3 按 Step2的方式, 重复对相邻有序
子序列进行归并操作, 直到成为一个有序
序列为止 。
下一页
上一页
停止放映
第 44页
归并排序算法简述
? 设有待排序数列 {49,38,65,97,76,12,27}，
? 第一趟处理, 先将每个元素看成是有序的子序列, 即
[49] [38] [65] [97] [76] [12] [27]
? 第二趟处理, 将长度为 1的子序列合并为长度为 2的子
序列, 即
[38, 49] [65,97] [12, 76] [ 27 ]
? 第三趟处理，将长度为 2的子序列合并为长度为 4的子
序列，即
[38, 49, 65,97] [12, 27,76 ]
? 第四趟处理，将长度为 4的子序列合并为长度为 8的序
列，即
[12,27,38, 49, 65,76,97]
? 提示：将归并过程中贡献出的元素，送进工作单元（ SWAP[m]）中。
下一页
上一页
停止放映
第 45页
（ 2）归并排序算法 3-12说明
? 设有两个有序序列 L1和 L2,它们顺序存放在数组 X[l1]，
X[l1+1],…,X[u1]和 X[l2],X[l2+1],…,X[u2]中,其中,
l2=u1+1;
? 设置三个变量 i,j,m,其中 i,j分别表示序列 L1和
L2中当前要比较的记录的位置；初值 i=l1,j=l2。 m
表示 Swap数组中当前位置, 初值 m=l1。
? 归并时, 反复比较 X[i]和 X[j]：
– 若 X[i]?X[j] 则 X[i]送 Swap[m],i++； m++；
– 若 X[i]>X[j] 则 X[j]送 Swap[m],j++； m++；
? 当序列 L1或 L2的全部记录已归并到数组 X中,即 i=u1+1,
或 j=u2+1时,
比较结束,然后将另一个序列中剩余的所有记录依此放
回到数组 Swap中,完成 L1和 L2的合并 。
下一页
上一页
停止放映
第 46页
归并排序算法举例
设有数列 {6,202,100,301,38,8,1}，
初始状态,[6] [202] [100] [301] [38] [8] [1]
比较次数
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
i=3 [ 1 6 8 38 100 202 301 ] 4
总计,11
SWAP数组：
SWAP数组：
1006
301
202 1 8 38
1 6 8 38 100 202
301
下一页
上一页
停止放映
第 47页
（ 3）归并排序算法 3-12（实现）
merge_sort(int *x,int n)
{
int i,k,l;
int swap[N];
k=1;
while(k<n) /* 步长从 1到 2*m的循环
*/
{
merge(x,swap,k,n); //k 待归并的子序列长度
for(i=0;i<n;i++) /* 将 数列 从 SWAP放回 X中
*/
x[i]=swap[i];
k=2*k; /* 序 列 长 度 加 倍
*/
}
}
X:待排数组
N：元素个数
下一页
上一页
停止放映
第 48页
归并排序算法 3-12(续一）
merge(int *x,int *swap,int k,int n)
{ int i,j,l1,l2,u1,u2,m; l1=0; m=0;
while(l1+k<n)
{ l2=l1+k; u1=l2-1; u2=(l2+k-1<n)?l2+k-1:n-1;
for(i=l1,j=l2;i<=u1&&j<=u2;m++)
{ if(x[i]<=x[j])
{ swap[m]=x[i]; i++; }/* x[i]贡献出 */
else
{ swap[m]=x[j]; j++; }/* x[j]贡献出 */
}
while(i<=u1) /* 将序列 1中剩余元素顺序放回 SWAP中 */
{ swap[m]=x[i]; m++; i++; }
while(j<=u2)/* 将序列 2中剩余元素顺序放回 SWAP中 */
{ swap[m]=x[j]; m++; j++; }
l1=u2+1; /* 改变子序列 */
}/*将原始序列中剩余的, 不足一组的记录顺序放到 SWAP中 */
for(i=l1;i<n;i++,m++) swap[m]=x[i];
}
下一页
上一页
停止放映
第 49页
归并排序算法 3-12主程序
#define N 7
main( )
{ int s[N],n,i;
printf("Enter a[i]\n");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
merge_sort(a,N); /* 调用归并排序函数 */
printf("The sorted string is,\n");
for( n=0; n < N; n++ )
printf(" %d",s[n]);
printf(“\n”);
} 示例
下一页
上一页
停止放映
第 50页
(4)算法评价
? 空间复杂度为 O（ n ），
用辅助空间 L1,L2、（ Swap）
? 时间复杂度为 O（ nlogn）
? 2-路归并排序算法是 稳定的 。
下一页
上一页
停止放映
第 51页
6.希尔（ Shell）排序
? (1)思想：
? 希尔排序是一种快速排序法，出自 D.L.Shell,
? 指导思想：
仍采用插入法，排序过程通过调换并移动数据
项来实现。每次比较 指定间距的 两个数据项，
若左边的值小于右边的值，则交换它们的位置。
间距 d按给定公式 减少,di+1 =（ di +1） /2,
直到 d等于 1为止。 d取 {9,5,3,2,1}。
下一页
上一页
停止放映
第 52页
（ 2）算法步骤
? Step1 将 n个元素个数列分为 n个部分，元
素比较间距为 d。
? step2 在第 i步，两元素比较的间距取
di+1 =（ di +1） /2 {9,5,3,2,1}
若 ai+1 > ai,则交换它们的位置。
? Step3 重复上述步骤，直到 dK = 1。
下一页
上一页
停止放映
第 53页
希尔排序举例
设有数列,f d a c b e”,
第 1趟 d=5 f d a c b e 得到 e d a c b f
第 2趟 d=3 e d a c b f 得到 c b a e d f
第 3趟 d=2 c b a e d f 得到 a b c e d f
第 4趟 d=1 a b c e d f 得到 a d c d e f
下一页
上一页
停止放映
第 54页
（ 3） SHELL排序子函数
shell(char *item,int count)
{ int i,j,k,s,w; char x; int a[]={9,5,3,2,1};
for(w=0;w<5;w++)/* 不同步长的 5次循环 */
{ k=a[w];s=-k; //k为步长
for(i=k;i<count;i++)
{ x=item[i]; j=i-k;
if(s==0)
{ s++; item[s]=x; }
while(x<item[j]&&j>=0&&j<=count)
{ item[j+k]=item[j]; j=j-k; }
item[j+k]=x;
}
}
}
下一页
上一页
停止放映
第 55页
? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
? 一趟比较示意图标 k=5
下一页
上一页
停止放映
第 56页
SHELL排序主函数
#include "stdio.h"
main()
{ char s[80];int l;
printf("Enter a string:");
gets(s);
l=strlen(s);
shell(s,l); /* 调用 shell函数 */
printf("The sorted string is,%s\n",s);
} 示例
下一页
上一页
停止放映
第 57页
上机实验要求
? 实验内容：
1、实现二叉排序树的查找
2、用前、中、后序法遍历二叉排序树
? 实验要求：
1、写出算法分析和操作步骤
2、设计、调试、上机通过上述程序；
3、将上述 4个程序作为作业提交
4、程序必须是上机通过的
5、实验结果的成绩将记入考试成绩中
? 详见“实验指导一”
下一页
上一页
停止放映
第 58页
作业、思考题
1、第 3章作业
思考,第 1,8,9,12题
作业：给定数列 {503,87,512,61,908、
170,897,275,653,426}，计算采用下列
算法的比较次数：
插入、选择、冒泡、快速、归并排序。
2、作业要求：
– 提交数字化作业，按要求提交到指定路径下
– 用 C语言描述
– 作业命名方式为：
学号,章数 _序号
