第3章 查找与排序技术3.2(new)

青 海 大 课 学 程 建 设 项 目

软件技术基础

计算机系教研室授课教师 韩亮 397406660@

软件技术基础

3.1 基本的查找技术 3.2 基本的排序技术

青海大学课程建设项目

3.1 基本的查找技术

软件技术基础

上次课主要内容 3.1.1 顺序查找 3.1.2 有序表的对分查找

3.1.3 分块查找 3.1.4 哈希表

青海大学课程建设项目第2章 基本数据结构及其运算 3

3.2 基本的排序技术

软件技术基础

本次课主要内容 3.2.1 冒泡排序与快速排序

3.2.2 简单插入排序与希尔排序

3.2.3 简单选择排序与堆排序 3.2.4 其他排序方法简介

青海大学课程建设项目第2章 基本数据结构及其运算 4

软件技术基础 3.2 基本的排序技术

排序：将一组次序任意的数据元素转变成按其关键字值 递增(或递减)次序排列的过程。序号 ISBN 书名 单价 销量 销售额

01 2 3 ... n-1

7-4302-7685-315-2302-3849-2 9-7809-2345-9 9-7873-0203-9

数据结构数据库 C语言设计 软件技术 ...

3021 21.5 21

3000900 5000 1200

9000018900 107500 25200

3-3303-3849-7

图像处理

33

300

9900

青海大学课程建设项目

软件技术基础 3.2.1 冒泡排序与快速排序(交换排序)

1. 冒泡排序(1)首先，从表头开始往后扫描线性表，在扫描过程中逐 次比较相邻两个元素的大小。

(2)若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。 显然，在扫描过程中，不断地将两相邻元素中的大者往后移 动，最后就将线性表中的最大者换到了表的最后。 经过第 i 趟排序后，序列达到有序，结束排序。青海大学课程建设项目

软件技术基础

青海大学课程建设项目

软件技术基础输入：无序序列p(1:n)。 输出：有序序列p(1:n)。 Procedure Bubsort(p,n) m = n; While(m>0) DO /*判断子表是否为空*/ k = m-1; For j=0 to k If p[j]>p[j+1] Then p[j] <-> p[j+1]; m--; Return;

青海大学课程建设项目

软件技术基础冒泡排序C语言描述 bubsort(ET p[], int n) { int m,k,j,tmp; m = n; while(m>0) { k = m-1; For j=0 to k If p[j]>p[j+1] Then {tmp=p[j]; p[j]=p[j+1];p[j]=tmp;} m--; } }青海大学课程建设项目

软件技术基础2. 快速排序

青海大学课程建设项目

软件技术基础首先，选取表中一个元素p(k),令T=p(k)称为控制关键字。

然后设置两个指针i和j分别指向表的起始与最后的位置。反复作以下两步： (1)将j逐渐减小，并逐次比较P(j)与T,直到发现一个P(j) <T为止，将P(j)移到P(i)的位置上。 (2)将i逐渐增大，并逐次比较P(i)与T,直到发现一个P(i)

>T为止，将P(i)移到P(j)的位置上。上述两个操作交替进行，直到指针i与j指向同一个位置(即 i=j)为止，此时将T移到P(i)的位置

上。

青海大学课程建设项目

软件技术基础

68 56 32

39 39 39

65 65 47

83 47

74 32 65

32

47 74

56 83 83

6868

565656 56

747474 74

3232 32

39

4747 47

6565 65

6868 68

8383 83 结果

3939

青海大学课程建设项目

软件技术基础线性表的分割 输入：待分割的子表P(m:n)。 输出：分割后的分界线位置i。 Procedure Split(p,m,n,i) 选取P(k) 其中m≤k≤n P(k)=P(m); T=P(k); i=m;j=n WHILE (i≠j) DO { WHILE (P(j)≥T)and(i<j) DO j=j-1; P(i)=P(j); WHILE (P(i)≤T)and(i<j) DO i=i+1; P(j)=P(i); } P(i)=T RETURN青海大学课程建设项目

软件技术基础快速排序的递归算法 输入：待排序的子表P(m:n)。

输出：有序子表P(m:n)。PROCEDURE QKSORT1(P,m,n) IF (n>m) THEN [子表不空]

{ SPLIT(P,m,n,i);

[分割]

QKSORT1(P,m,i-1);[对前面子表进行快速排序] QKSORT1(p,i+1,n);[对后面子表进行快速排序] } RETURN青海大学课程建设项目

软件技术基础快速排序C语言描述 qksort1(ET p[],int m,int n) { int i; /*分割*/

if (n>m) /*子表不空*/{i=split(p,m,n); qksort1(p,m,i-1);/*对前子表进行快速排序*/ qksort1(p,i+1,n);/*对后子表进行快速排序*/ } return; }青海大学课程建设项目

软件技术基础int split(ET p[],int m,int n) /*返回分界线位置*/ { int i,j,k,u;ET t;

i=m; j=n;t =p[m];while (i!=j) { while ((i<j)&&(p[j]>=t)) j=j-1; p[i]=p[j]; while ((i<j)&&(p[i]<=t)) i=i++1; p[j]=p[i]; } p[i]=t;return(i);青海大学课程建设项目 }

软件技术基础 3.2.2 简单插入排序与希尔排序1. 简单插入排序

5

22

18

9

20

13

46

22

5

22

18

9

20

13

46

18

5

18 22 9

22 18 13

22 9 18 20

20 22

13 22

46

46 13 20 9

青海大学课程建设项目

软件技术基础输入：待排序序列P(1:n)。

输出：有序序列P(1:n)。PROCEDURE FOR i=1 { x=P(i) FOR j=i-1 TO 0 BY -1 DO INSORT(P,n) TO n-1 DO

IF (x<P(j)) THEN P(j+1)=P(j)P(j+1)=x } RETURN青海大学课程建设项目

软件技术基础简单插入排序C语言描述 insort(ET p[],int n) { int j,k; ET t; for (j=1; j<n; j++) { t=p[j]; k=j-1; while ((k>=0)&&(p[k]>t)) { p[k+1]=p[k]; k=k-1; } p[k+1]=t; } return; }青海大学课程建设项目