当前位置:首页 >> 学科竞赛 >>

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案


§9

内部排序

在《数据结构》里,排序一般分为:插入排序、交换排序、选择排序、归并排序和基数排 序五种。

写在前面的话: 在看下面的各种算法之前,请先想想,如果给你一个无序的数列,你如 何去排序?设计出你自己的算法。还有没有其它方法? 相信自己的能力, 排序算法是连小学生都可以设计出的! 不希望以后听到这样的话:

“排序的算法我忘了……” ,排序算法不是背 出来的!

§9.1

插入排序 (Insertion Sort)

基本思想: 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数 列依然有序;直到待排序数据元素全部插入完为止。 排序过程: 【示例】 : [初始关键字] [49] 38 J=2(38) [38 J=3(65) [38 J=4(97) [38 J=5(76) [38 J=6(13) [13 J=7(27) [13 J=8(49) [13 65 97 76 13 27 49 49] 65 97 76 13 27 49 49 65] 97 76 13 27 49 49 65 97] 76 13 27 49 49 65 76 97] 13 27 49 38 49 65 76 97] 27 49 27 38 49 65 76 97] 49 27 38 49 49 65 76 97]

§9.2

选择排序

基本思想: 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数 列的最后,直到全部待排序的数据元素排完。 排序过程: 【示例】 : 初始关键字 第一趟排序后 第二趟排序后 第三趟排序后 第四趟排序后 第五趟排序后 第六趟排序后 第七趟排序后 最后排序结果 13 13 13 13 13 13 13 13 [49 38 65 97 76 13 27 49] [38 65 97 76 49 27 49] 27 [65 97 76 49 38 49] 27 38 [97 76 49 65 49] 27 38 49 [49 97 65 76] 27 38 49 49 [97 97 76] 27 38 49 49 76 [76 97] 27 38 49 49 76 76 [97] 27 38 49 49 76 76 97

§9.3

冒泡排序 (BubbleSort)

基本思想: 两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没 有反序的数据元素为止。 排序过程: 设想被排序的数组 R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡 不能在重气泡之下的原则,从下往上扫描数组 R,凡扫描到违反本原则的轻气泡,就使其向上 "漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。 【示例】 : 49 38 65 97 76 13 27 49 13 49 38 65 97 76 27 49 13 27 49 38 65 97 76 49 13 27 38 49 49 65 97 76 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97

【练习 1】 请分别用以上三种算法完成。 同学们进行了身体素质测量,其中立位体前屈的成绩是以 XX . XX cm 来记录的,这个成绩 不可能超过 100,当有可能为负数(当指尖碰不到足时) ,现有若干同学的成绩,请帮他们排序。 输入: 第一行 正整数 n (有 n 个同学) 第二行 n 个成绩 输出: n 个成绩从大到小的排列

§9.4

快速排序 (Quick Sort)

基本思想: 在当前无序区 R[1..H]中任取一个数据元素作为比较的"基准元素",用此基准元素将当 前无序区划分为左右两个较小的无序区:R[1..I-1]和 R[I+1..H],且左边的无序子区中数据 元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准元素则 位于最终排序的位置 I 上,即 R[1..I-1]≤R[I]≤R[I+1..H](1≤I≤H),当 R[1..I-1] 和 R[I+1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已 排序为止。 排序过程: ——将数列从小到大排序 以第一个元素作为基准,设两指针 i 和 j,初始时 i 指向区间第一个元素,j 指向最末一个 元素;先移动 j 指针,如果 j 元素比 i 元素大,j 指针前移,否则若 j 小于 i,则交换 i 和 j 。 交换 i 和 j 后,移动 i 指针,如果 i 元素比 j 元素小,i 指针后移,否则若 i 大于 j,则交换 i 和 j 。再移动 j 指针,??,轮流移动 i 指针和 j 指针,直到 j = i 。 将数列分成两部分,分别进行上述过程。 i j 【示例】 : 初始关键字 ,j 指针左移 [49 38 65 97 76 13 27 49] i j [27 38 65 97 76 13 49 49] i j [27 38 49 97 76 13 65 49] i j [27 38 13 97 76 49 65 49] i j [27 38 13 49 76 97 65 49] i j [27 38 13 49 76 97 65 49]

第一次交换后 ,j 指针不动,i 指针右移

第二次交换后 ,i 指针不动,j 指针左移

第三次交换后 ,j 指针不动,i 指针右移

第四次交换后,i 指针不动,j 指针左移

j 指针左移,遇 i 指针 (递归过程) 初始关键字 一趟排序之后 二趟排序之后 三趟排序之后 最后的排序结果

[49 38 65 97 76 13 27 49] [27 38 13] 49 [76 97 65 49] [13] 27 [38] 49 [49 65]76 [97] 13 27 38 49 49 [65]76 97 13 27 38 49 49 65 76 97

参考程序: Procedure Parttion(L, H : Integer; var I : integer); {对无序区 R[L,H]做划分,I 返回出本次划分后已被定位的基准元素的位置} begin I:=L; J:=H; X:=R[I]; {初始化} Repeat While (R[J]>=X) And (I<J) Do J:=J–1; {J 指针左移,查找第 1 个小于基准的元素} If I<J Then R[I]:=R[J]; {相当于交换 R[I]和 R[J]} While (R[I]<=R[J]) And (I<J) Do I:=I+1; {I 指针右移,查找第 1 个大于基准的元素} If I<J Then R[J]:=R[I]; Until I=J; R[I]:=X; {基准 X 已被最终定位} end; {Parttion} Procedure QuickSort(S,T:Integer); {对 R[S..T]快速排序} begin If S<T Then begin {当 R[S..T]为空或只有一个元素是无需排序} Partion (S,T,I); {对 R[S..T]做划分,返回 I} QuickSort (S,I-1); {递归处理左区间 R[S,I-1]} QuickSort (I+1,T); {递归处理右区间 R[I+1,T]} end; end; {QuickSort}

【练习 2】请将给出的单词按字典排序。 (利用字符串比较) 输入:从文件 word.in 读入 第一行 正整数 n

以下 n 行 每行一个单词 输出:写入文件 word.out 中 按字典排序,每行一个单词

§9.5

堆排序 (Heap Sort)

基本思想: 堆排序是一树形选择排序,在排序过程中,将 R[1..N]看成是一棵完全二叉树的顺序存 储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 堆的定义: N 个元素的序列 K1, K2, K3, ??, Kn. 称为堆,当且仅当该序列满足特性: Ki≤K2i Ki≤K2i+1 (1≤ i≤ [N/2])

堆实质上是满足如下性质的二叉树: 1. 是一棵完全二叉树; 2. 树中任一结点的值均大于等于(小于等于)其孩子结点的值; 3. 树根的值是最大的(最小的) 例如序列 10, 15, 56, 25, 30, 70 就是一个堆,它对应的完全二叉树如下图所示。

这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆。反之,若完全二叉 树中任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆。 这棵二叉树的存储,既可以用链表的方式存储,也可以用顺序表(一维数组 S)的方式存 储。采用顺序表的存储结构如上图所示,若某结点为 S[ i ],则其左右子树分别为 S[ 2i ] 和 S[ 2i+1 ]。

堆的调整: 在介绍从一个无序序列建堆的方法前,我们先看如何在一个已建成的堆中,若在输出堆 顶的最小值之后,调整剩余的 n-1 个元素的序列,重又建成一个一个堆。 设图 9-1 为一个几建成的小根堆。

图 9-1

输出堆顶元素后,以堆中最后元素代替之,如图 9-2 (a)。此时根结点的左右子树均为 堆,则仅需自上而下进行调整即可。 首先以新堆顶元素与其左右子树根结点的值比较,由于右子树根结点的值小于左子树根 结点的值,且小于根结点的值,则将根结点的值 69 与右子树根结点的值 11 交换, 如图 9-2 (b)。由于 69 替代了 11 之后破坏了右子树的“堆” ,需进行和上述相同的调整,直至叶子结 点。调整后的状态如图 9-2 (c)。这个过程可称为“筛” 。

(a)

(b) 图 9-2 调制建新堆的过程

(c)

输出堆顶元素后的调整过程如下: procedure sift ( var S : array [ 1..n ] of integer ; k , m : integer ); { 假设 S[k+1. . m]为小根堆,调整 S[k]使整个序列 S[k . . m]满足堆的性质 } begin i:=k; while j:=2*i; x:=S[k]; finish:=false; do begin

(j<=m) and (finish=false)

if (j<m) and (S[ j ]>S[ j+1 ]) then j:=j+1; {若存在右子树,且右子树根结点的值更小,则沿右分支调整} if x<=S[ j ] then finish:=true else begin S[ i ] := S[ j ]; end; end; {whie} S[ i ]:=x; end; i :=j ; j :=2*i ;

排序过程: 从一个无序序列建堆的过程就是一个反复调整的过程。 将无序数列看成一棵完全二叉树, 从最后一个非叶子结点 i 开始进行调整以该结点为根的子树,然后在调整以 i-1 为根的子 树,?? 这样,在原序列的尾部形成有序区并逐步向前扩大到整个序列。 【例】 :对无序序列 42,13,91,23,24,16,05,88 建立大跟堆

【练习】对输入的无序序列进行堆排序。 输入: 第一行: n 第二行: n 个整数 输出: 将 n 个整数按从小到大排序输出

§9.6

排序算法的比较和选择

1. 选取排序方法需要考虑的因素: (1) (2) (3) (4) 待排序的元素数目 n; 元素本身信息量的大小; 关键字的结构及其分布情况; 语言工具的条件,辅助空间的大小等。

2. 小结: (1) 若 n 较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的 记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。 (3) 若 n 较大,则应采用时间复杂度为 O(nlog2n)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。 (4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因 此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的 n 个关键字随机分布 时,任何借助于"比较"的排序算法,至少需要 O(nlog2n)的时间。 (5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案_学科竞赛_高中教育_教育专区。§9 内部排序 在《数据结构》里,排序一般分为:插入...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案_其它课程_高中教育_教育专区。§7 §7.1 树的概念 树 【定义】 树(Tree)是 n(n>0...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案_学科竞赛_高中教育_教育专区。§1 §1.1 什么是数据结构 概论 数据结构(Data ...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案_学科竞赛_高中教育_教育专区。§4 §4.1 串的匹配 串 子串的定位操作称为串的模式匹配,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案_学科竞赛_高中教育_教育专区。§2 §2.1 线性表的定义及其基本运算 线性表 线性表是...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案_学科竞赛_高中教育_教育专区。§6 §6.1 广义表的定义 广义表 广义表 (Lists) 又称...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案_学科竞赛_高中教育_教育专区。§5 §5.1 特殊矩阵 §5.1.1 三角矩阵与...
广东省汕头市金山中学高中信息技术 pascal教程01 第一课 让程序“跑”起来教案
广东省汕头市金山中学高中信息技术 pascal教程01 第一课 让程序“跑”起来教案_其它课程_高中教育_教育专区。第一课 让程序“跑”起来 计算机可以帮我们做很多事,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案_学科竞赛_高中教育_教育专区。§8 §8.1 图的基本概念 图 图: 图是数据结构 G=(V,...
更多相关标签:
广东省汕头市金山中学 | 广东省汕头市 | 广东省汕头市潮阳区 | 广东省汕头市邮编 | 广东省汕头市潮南区 | 广东省汕头市澄海区 | 广东省汕头市金平区 | 广东省汕头市地图 |