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