西安邮电学院 《数据结构》曾艳 第9章 排序

发布时间:2021-08-04 20:39:31

第九章 内部排序
9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序法 9.4 选择类排序法 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的综合比较 9.8 总结与提高

9.1 排序的基本概念 一、排序的定义
排序是计算机内经常进行的一种操作, 排序是计算机内经常进行的一种操作, 其目的是将一组“无序” 其目的是将一组“无序”的记录序列调整 有序”的记录序列。 为“有序”的记录序列。 例如: 例如:将如下序列

52, 49, 80, 36, 14, 58, 61, 23, 97, 75
调整为

14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

定义: 定义:
设含 n 个记录的序列为 { R1, R2, …, Rn } , 其相应的关键字序列为 { K1, K2, …,Kn } , 记录关键字相互之间可以进行比较, 记录关键字相互之间可以进行比较,即存 在关系 : Kp1≤Kp2≤…≤Kpn ≤ 按此关系将上述记录序列调整为 { Rp1, Rp2, …,Rpn } , 的操作称作排序。 排序。

稳定的排序和不稳定的排序 排序和不稳定的 二、稳定的排序和不稳定的排序 设待排序记录序列中有关键字相 等的记录, 等的记录 即ki=kj(i<>j), 且在排序前 Ri领先于 领先于Rj. 领先于 若排序后可以保证Ri仍领先于 若排序后可以保证 仍领先于 可以保证 仍领先于Rj, 则 所用的排序方法称为稳定的 稳定的; 所用的排序方法称为稳定的 若排序后不能保证 仍领先于Rj, 则 不能保证Ri仍领先于 若排序后不能保证 仍领先于 所用的排序方法称为不稳定的 不稳定的. 所用的排序方法称为不稳定的

例如: 例如:
排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后必有结果: 若排序后必有结果: ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的; 则称该排序方法是稳定的 稳定 若排序后可能得结果: 若排序后可能得结果: ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定 不稳定的 则称该排序方法是不稳定的。

三、内部排序和外部排序
若整个排序过程不需要访问外存 便能完成,则称此类排序问题为内部 便能完成,则称此类排序问题为内部 排序。 排序。 反之, 反之 若参加排序的记录数量很 整个序列的排序过程不可能在内 大, 整个序列的排序过程不可能在内 中完成,则称此类排序问题为外 存 中完成,则称此类排序问题为外 部排序。 部排序。

四、内部排序的存储方式 1、顺序存储:移动记录实现排序; 、顺序存储:移动记录实现排序; 2、(静态 链表:修改指针 游标 实 、 静态 链表:修改指针(游标 静态)链表 游标)实 现排序; 现排序; 3、地址向量:移动地址实现排序; 、地址向量:移动地址实现排序; (又称地址排序 又称地址排序) 又称地址排序
本课程我们重点讨论在顺序存储结构 上,各种排序方法的实现。 各种排序方法的实现。

9.2 插入类排序 基本思想: 基本思想: 将无序序列中的记录一个一个的 将无序序列中的记录一个一个的 “插入”到有序序列中的恰当位置,以 插入”到有序序列中的恰当位置, 恰当位置 逐渐增加有序序列的长度K(K=1 逐渐增加有序序列的长度 从而实现排序。 从而实现排序。 N),

一趟插入排序的基本过程:
有序序列r[1..i-1] 无序序列 r[i..n] r[i] 找位置

插入
有序序列r[1..i] 无序序列 r[i+1..n]

实现“一趟插入排序”可分三步进行: 实现“一趟插入排序”可分三步进行: 1.查找插入位置:在r[1..i-1]中查找 . 插入位置: 中查找r[i] 中查找
的插入位置j+1 : 的插入位置 r[1..j].key ≤ r[i].key < r[j+1..i-1].key; ;

2.后移:将r[j+1..i-1]中的所有记录均 .后移: 中的所有记录均
后移一个位置; 后移一个位置;

3.插入:将r[i] 插入 复制 到r[j+1]的 .插入: 插入(复制 复制)到 的
位置上。 位置上。

不同的具体实现方法导致不同的算法描述
基于顺序查找) 直接插入排序(基于顺序查找)

折半插入排序(基于折半查找) 基于折半查找)
基于逐趟缩小增量) 希尔排序(基于逐趟缩小增量)

一、直接插入排序
利用 “顺序查找”实现 顺序查找” “在r[1..i-1]中查找r[i]的插入位置 的插入位置” 的插入位置

算法的实现: 算法的实现:

1. 从r[i-1]起向前进行顺序查找, 起向前进行顺序查找, 起向前进行顺序查找 监视哨设置在r[0]; ; 监视哨设置在
r[0] r[i]

j j 插入位置 j j j=i-1 循环结束确定r[i]的插入位置为 循环结束确定 的插入位置为 j +1; 2. 将所有 j+1…i-1 的记录向后移动 1位; 位 3. 将r[0](原r[i])“插入”到j+1的位置。 插入” 的位置。 原 插入 的位置

方法的改进: 方法的改进
可以在查找的同时实现记录向后移动; 可以在查找的同时实现记录向后移动;
r[0] r[i]

j

插入位置

j= i-1

r[0]=r[i]; j=i-1; while( r[0].key <r[j].key) { r[j+1]= r[j]; j=j-1;} 上述循环结束后可以直接进行“插入” 上述循环结束后可以直接进行“插入”

算法: 算法:
可实现整个序列的排序。 令 i = 2,3,…, n, 可实现整个序列的排序。 Void inssort(recordtype r[ ], int n) {for(i=2;i<=n; i++) ( {r[0]=r[i]; j=i-1; while(r[0].key <r[j].key) { r[j+1]= r[j]; j=j-1;} r[j+1]=r[0];}}

稳定? 稳定?

时间复杂度分析: 时间复杂度分析:
实现内部排序的基本操作有两个: 实现内部排序的基本操作有两个: 基本操作有两个 (1)“比较”序列中两个关键字的 ) 比较” 大小; 大小; (2)“移动”记录。 ) 移动”记录。

对于直接插入排序: 对于直接插入排序:
最好的情况(关键字在记录序列中顺序有序 最好的情况 关键字在记录序列中顺序有序): 关键字在记录序列中顺序有序

“比较”的次数: 比较”的次数: 比较 ∑ 1 = n-1
i=2 n

“移动”的次数: 移动”的次数: 移动
2(n-1)

最坏的情况(关键字在记录序列中逆序有序): 最坏的情况(关键字在记录序列中逆序有序):

“比较”的次数: 比较”的次数: 比较 ∑(i) =
i=2 n

“移动”的次数: 移动”的次数: 移动
(n+4)(n-1) ∑(i+1) = 2 i=2
n

(n+2)(n-1) 2

所以,时间复杂度为 所以,时间复杂度为O(n2)

二、折半插入排序
因为 r[1..i-1] 是一个按关键字有序 的序列, 则可以利用折半查找 折半查找实现在 的序列 则可以利用折半查找实现在 的插入位置” “r[1..i-1]中查找 r[i]的插入位置”, 如 中查找 的插入位置 此实现的插入排序为折半插入排序。 此实现的插入排序为折半插入排序。它 只能减少查找的次数不能减少移动 减少查找的次数不能减少移动的次 只能减少查找的次数不能减少移动的次 数, 因此与查找后移同时实现的直接插 入排序比较, 改进不大。 入排序比较 改进不大。 算法见: 算法见 p302,自学! ,自学!

例如: 例如

插入 位置

i

L.r 14 36 49 52 80 58 61 23 97 75
low high low high low m m m

再如: 再如

插入 位置

i

L.r 14 36 49 52 58 61 80 23 97 75
low high low high m m m high

缩小增量排序) 三、希尔排序(缩小增量排序 缩小增量排序
由于插入排序的效率取决于 记录的个数 由于插入排序的效率取决于:记录的个数 插入排序的效率取决于 及记录的原始序; 及记录的原始序; 所以希尔排序的基本思想为 希尔排序的基本思想为: 所以希尔排序的基本思想为:对待排记录 序列先作“宏观”调整,再作“微观”调整。 序列先作“宏观”调整,再作“微观”调整。
“宏观”调整:先“跳跃式”的分组进行排序, 使 宏观”调整: 跳跃式”的分组进行排序 宏观 得整个序列“基本有序” 每组记录少 每组记录少) 得整个序列“基本有序”。(每组记录少 “微观”调整:在整个序列“基本有序”后, 再 微观”调整:在整个序列“基本有序” 微观 进行直接插入排序使整个序列“完全有序” 进行直接插入排序使整个序列“完全有序”。 记录的原始序优 (记录的原始序优)

具体做法: 具体做法:
将记录序列跳跃式的分成若干组, 将记录序列跳跃式的分成若干组,分别对每组进 跳跃式的分成若干组 插入排序,组数不断减少,最后仅剩一组。 行插入排序,组数不断减少,最后仅剩一组。 例如: 例如:将 n 个记录
{ r[1], r[2]…r[d], r[1+d],r[2+d]…r[2d], r[1+2d] …r[n]}

个子序列: 分成 d 个子序列:
{ r[1], r[1+d], r[1+2d], … , r[1+kd]… } , , , { r[2], r[2+d], r[2+2d], … , r[2+kd] … } , , , … { r[d], r[2d], r[3d], … , r[(k+1)d] }

其中, 称为增量, 其中 d 称为增量 它的值在排序过程中从 大到小逐渐缩小,直至最后一趟排序减为 1 . 大到小逐渐缩小,直至最后一趟排序减为

例如:
16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序,设增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序,设增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希尔排序,设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47

算法: 算法:
Void shellinsert(recordtype r[ ], int length, int d ) { for(i=1+d; i<=length; i++) if(r[i].key < r[i-d].key) {r[0]=r[i]; /*是监视哨吗?*/ 是监视哨吗? 是监视哨吗 for(j=i-d;j>0&&r[0].key< r[j].key;j-=d) r[j+d]=r[j]; r[j+d]=r[0];}} Void shellsord(recordtype r[ ], int length, int d[], int n) { for (i=0;i<=n-1,++i) 稳定? 稳定? shellinsert(r,length, d[i] );}

例:d=5, 3, 1 ,对如下记录进行排序 对如下记录进行排序 37 25 12 30 47 11 23 36 9 18 31
希尔排序的时间复杂度分析是一个数学上尚未解 决的难题。增量序列d[1..t]的设计至关重要,目前没有 的设计至关重要, 决的难题。增量序列 的设计至关重要 统一定论,以经验为主。 统一定论,以经验为主。 逆转数:对于待排序序列中的某个记录的关键字, 逆转数:对于待排序序列中的某个记录的关键字,它 的逆转数是指在它之前比此关键字大的关键字的个数。 的逆转数是指在它之前比此关键字大的关键字的个数。 直接插入排序:一次移动只能减少一个逆序数。 直接插入排序:一次移动只能减少一个逆序数。逆转 数之和就是排序所需要移动的记录的次数。 数之和就是排序所需要移动的记录的次数。 希尔排序:一次移动后减少的逆转数不止一个 不止一个。 希尔排序:一次移动后减少的逆转数不止一个。 时间复杂度为O(n1.5). 希尔排序的 时间复杂度为

设比较位置如下图所示,此时: 设比较位置如下图所示,此时:Ki>Kj
Ki Kj

交换后如下图: 交换后如下图:
Kj Ki

可以确定交换位置之前 之后的关键字的逆转数不变化。 之前, 的关键字的逆转数不变化 可以确定交换位置之前,之后的关键字的逆转数不变化。 交换位置以及其间的关键字的逆转数发生变化。 以及其间的关键字的逆转数发生变化 仅交换位置以及其间的关键字的逆转数发生变化。 假设: 之间:关键字值大于 的记录有M个 大于K 假设:Ki和Kj之间:关键字值大于Ki的记录有M个 关键字值小于 的记录有N个 小于K 关键字值小于 j的记录有 个 关键字值介于 介于K 之间的记录有 的记录有L个 关键字值介于 j和Ki之间的记录有 个 不变; 则:关键字值大于 i和小于 j的记录,其逆转数不变; 关键字值大于K 小于K 的记录,其逆转数不变 大于 关键字值介于 介于K 之间的记录 其逆转数减 ; 的记录, 关键字值介于 j和Ki之间的记录,其逆转数减1; Ki的逆转数增加 的逆转数增加 增加M; 减少( Kj的逆转数减少(L+M+1); 的逆转数减少 )

逆转数总和将减少2L+1. 逆转数总和将减少

9.3 交换类排序法
一、 起泡排序 二、 快速排序 三、 快速排序的时间分析

一、 起泡排序 假设在排序过程中,记录序列r[1..n] 假设在排序过程中,记录序列 i 的状态为: 的状态为:
无序序列r[1..i] 有序序列 r[i+1..n] 有序序列大于无序序列

对无序序列,比较(交 对无序序列,比较 交 换)相邻记录,可将关 相邻记录, 相邻记录 键字最大的记录交换 键字最大的记录交换 到 i 的位置上
无序序列r[1..i-1]

一 趟起泡排序

有序序列 r[i..n]

算法一:
void bubblesort(recordtype r[ ], int length); { n=length;change=true; for( i=n; i>1&&change; --i) {change=false; for (j=1; j<i ; ++j) if (r[j+1].key < r[j].key) {x=r[j]; r[j]=r[j+1]; r[j+1]=x; change=true; } } } 稳定? 稳定?

算法二:
void bubblesort(recordtype r[ ], int n); {i= n; while ( i >1) { laste=1; for (j=1; j<i; j++) if (r[j+1].key < r[j].key) {x=r[j]; r[j]=r[j+1]; r[j+1]=x; laste= j; } {记下进行交换的记录位置 记下进行交换的记录位置} 记下进行交换的记录位置 i= laste; {本趟最后一次进行交换的记录位置 本趟最后一次进行交换的记录位置} 本趟最后一次进行交换的记录位置 }
}

注意: 注意: 1. 起泡排序的结束条件为, 最后一趟没有进行“交换记录” 最后一趟没有进行“交换记录”。 2. 算法一每经过一趟“起泡”则“i减1”, i 但算法二并不是每趟如此。 例如: 例如 1 3 1 3 5 3 9 2 2 5 5 7 8 1 5 2 3 1 9 7 9 8
laste i=2 laste i=6 i=7

时间分析: 时间分析:
最好的情况(关键字在记录序列中顺序有序): 最好的情况(关键字在记录序列中顺序有序): 只需进行一趟起泡

“比较”的次数: 比较”的次数: 比较

“移动”的次数: 移动”的次数: 移动

最坏的情况(关键字在记录序列中逆序有序): 最坏的情况(关键字在记录序列中逆序有序): 需进行n-1趟起泡 需进行 趟起泡

n-1

0

“比较”的次数: 比较”的次数: 比较
n (n-1) ∑(i -1) = 2 i=2
n

“移动”的次数: 移动”的次数: 移动
3n (n-1) 3∑(i -1) = 2 i=2
n

所以,时间复杂度为 所以,时间复杂度为O(n2)

二、快速排序
起泡排序一趟之后, 起泡排序一趟之后,使最大的记录定 位到最后 如果一趟之后可使某记录(任意 最后,如果一趟之后可使某记录 任意) 位到最后 如果一趟之后可使某记录 任意 定位在它应处的位置 在有序序列中),而 应处的位置(在有序序列中 定位在它应处的位置 在有序序列中 而 将其余的无序序列以它为枢轴 分成两部 将其余的无序序列以它为枢轴,分成两部 枢轴 比它小的放在它的前面,比它大的的放 分,比它小的放在它的前面 比它大的的放 比它小的放在它的前面 在它的后面,下一趟分别对前后的子序列 在它的后面 下一趟分别对前后的子序列 排序,显然可加快速度 这就是快速排序 显然可加快速度。 排序 显然可加快速度。

一趟快速排序(一次划分) 一趟快速排序(一次划分)
目标:找一个记录, 目标:找一个记录,以它的关键字作为 枢轴” 关键字小于枢轴的记录均 的记录均移 “枢轴”,凡关键字小于枢轴的记录均移 动至该记录之前,反之, 动至该记录之前,反之,凡关键字大于枢 的记录均移动至该记录之后 移动至该记录之后。 轴的记录均移动至该记录之后。 致使一趟排序之后,记录的无序序列r[s..t] 致使一趟排序之后,记录的无序序列 一趟排序之后 分割成两部分: 将分割成两部分:r[s..i-1]和r[i+1..t],且 和 , r[j].key≤ r[i].key ≤ r[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。 。

例如 s

r[s] 52

t

23 14 52 80 52 49 80 36 14 58 61 97 23 75
low low low low low high high high high high high

设 r[s]=52 为枢轴 和枢轴的关键字进行比较, 将 r[high].key 和枢轴的关键字进行比较, 要求 r[high].key ≥ 枢轴的关键字 枢轴的关键字进行比较, 将 r[low].key 和 枢轴的关键字进行比较, 要求 r[low].key ≤ 枢轴的关键字

可见,经过“一次划分” 可见,经过“一次划分”,将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 变为: 变为 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中,设立了两个指针: 在调整过程中,设立了两个指针: low 和high,它们的初值分别为: s 和 t, ,它们的初值分别为: , 之后逐渐减小 high,增加 low,并保证 , , r[high].key≥52,和 r[low].key≤52,否 , , 则进行记录的“交换” 实际只需赋值) 则进行记录的“交换”(实际只需赋值)。

一趟快速排序算法
int QKpass(recordtype r[ ], int s, int t)
/*本算法对 本算法对r[s..t]进行一趟快速排序 进行一趟快速排序*/ 本算法对 进行一趟快速排序 {x=r[s]; i=s; j=t; while (i<j) /*low用i表示 high用j表示 表示, 表示*/ 用 表示 用 表示 {while (i<j)&&(r[j].key>=x.key) j=j-1; r[i]=r[j]; while (i<j)&&(r[i].key<=x.key) i=i+1; r[j]=r[i]; } r[i]=x; return i; }

快速排序过程
首先对无序的序列进行“一次划分” 之 首先对无序的序列进行“一次划分”,之 分别对分割所得两个子序列 递归” 对分割所得两个子序列“ 后分别对分割所得两个子序列“递归”进 行快速排序。 行快速排序。
无序的记录序列

一次划分
无序记录子序列(1)
枢轴

无序子序列(2)

分别进行快速排序

快速排序算法
void QKsort(recordtype r[ ], int low, int high);
/*对记录序列 low.. high]进行快速排序 对记录序列r[ 进行快速排序*/ 对记录序列 进行快速排序

{ if (low < high) { pos=QKpass(r,low,high); /*对 r[low.. high] 进行一趟划分 为枢轴*/ 进行一趟划分,pos为枢轴 QKsort(r,low,pos-1); /*对低子序列递归排序*/ QKsort(r,pos+1,high); /*对高子序列递归排序 对高子序列递归排序*/ 对高子序列递归排序 }}

稳定? 稳定?

三、快速排序的时间分析
假设一次划分所得枢轴位置 假设一次划分所得枢轴位置 i=k,则 , 个记录进行快速排序所需时间: 对n 个记录进行快速排序所需时间: T(n) = Tpass(n) + T(k-1) + T(n-k) 其中 Tpass(n)为对 n 个记录进行一次划分 为对 所需时间。 所需时间。
若待排序列中记录的关键字是随机分布的, 若待排序列中记录的关键字是随机分布的, 中任意一值的可能性相同。 则 k 取 1 至 n 中任意一值的可能性相同。

由此可得快速排序所需时间的*均值为 由此可得快速排序所需时间的*均值为: *均值
1 Tavg (n) = cn + n ∑ [Tavg (k?1)+Tavg (n?k)] [ ? ?
k=1 n-1 n

= cn + n ∑ Tavg (i)
i=1

2

设Tavg(0)≤b , Tavg(1)≤b , ≤ ≤ 则用数学归纳法可证明: 则用数学归纳法可证明:

c,b为常数 为常数

Tavg (n)≤2 n (b+c) ln (n) 结论: 快速排序的时间复杂度为O(nlogn) 结论 快速排序的时间复杂度为

若待排记录的初始状态为按关键字有序 快速排序将蜕化为起泡排序, 时,快速排序将蜕化为起泡排序,其时间 复杂度为O(n2)。 复杂度为 。 为避免出现这种情况, 为避免出现这种情况,需在第一次划分 之前,进行“予处理” 之前,进行“予处理”,即: 先对 r[s].key, r[t].key 和 r[?(s+t)/2?].key ? ? 进行相互比较,然后取 中间” 进行相互比较,然后取关键字为 “中间” 的记录为枢轴记录。 的记录为枢轴记录。 为枢轴记录

9.4 选择类排序法
一、简 单 选 择 排 序 二、树 形 选 择 排 序 三、堆 排 序

一、简单选择排序
假设排序过程中, 待排记录序列的状态为: 假设排序过程中 待排记录序列的状态为: 有序序列r[1..i-1] 有序序列 第i趟 简单选择排序 无序序列 r[i..n]
关键字最小的记录

有序序列小于无序序列 有序序列小于无序序列 小于 从中选出

有序序列r[1..i] 有序序列

无序序列 r[i+1..n]

简单选择排序算法
void SelectSort(RecordType r[], int length) { n=length; for ( i=1 ; i<= n-1; ++i) - {k=i; ; for ( j=i+1 ; j<= n ; ++j) if (r[j].key < r[k].key ) k=j; ; if ( k!=i) { x= r[i]; r[i]= r[k]; r[k]=x; } ; ; } }

稳定? 稳定?

时间性能分析 个记录进行简单选择排序, 对 n 个记录进行简单选择排序, 所需进行的 关键字间的比较次数 总计为: 总计为:
n(n ?1) ∑(n ? i) = 2 i=1
n?1

移动记录的次数: 移动记录的次数:最小值为 0 最大值为3(n-1) 。 最大值为

二、树形选择排序
是一种按锦标赛的思想进行排序的 是一种按锦标赛的思想进行排序的 锦标赛 方法。 方法。 选择时两两比较,第一轮小者为胜 选择时两两比较 第一轮小者为胜 者再进行第二轮比较,逐层向上直到比 者再进行第二轮比较 逐层向上直到比 出冠军为最小者。 出冠军为最小者。 比较的过程是一个二叉树结构,其 比较的过程是一个二叉树结构 其 中记录了互相之间的比较结果,利用此 中记录了互相之间的比较结果 利用此 结果再比较很快会得到第二第三 …。 。

01 01 02

02

03 03 01 02

04

05 05

06

07

08 06

05 01 02

按锦标赛规则, 将成为亚军,显然不合理 将成为亚军 不合理。 按锦标赛规则,05将成为亚军,显然不合理。解决 夺冠之后 退出, 参加过的比赛重 的方法是在01夺冠之后, 退出 的方法是在 夺冠之后,01退出,01参加过的比赛重 新进行(再筛选)。 新进行(再筛选)。 如此,第二、第三… 各名次的结果才真实、合理。 如此,第二、第三 各名次的结果才真实、合理。 由此,引出堆排序方法(空间 时间效率更高) 空间、 由此,引出堆排序方法 空间、时间效率更高

三、堆排序
堆的定义: 堆的定义 堆是满足下列性质的数列{r 堆是满足下列性质的数列 1, r2, …,rn}: , :
? ri ≤ r2i ? ri ≥ r2i (小顶堆 或 ? 小顶堆) (大顶堆 大顶堆) 小顶堆 大顶堆 ? ?ri ≤ r2i+1 ?ri ≥ r2i+1

可将该数列视作按层次存储的完全二叉树, 可将该数列视作按层次存储的完全二叉树, 的左孩子; 的右孩子。 则 r2i 是 ri 的左孩子; r2i+1 是 ri 的右孩子。

ri r2i r2i+1

例如: 例如
{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆

可利用堆的特性 81, 73, 55, 49} 不是堆 堆的特性(首元素最小或最大 可利用堆的特性 首元素最小或最大) {12, 36, 27, 65, 40, 14, 98,首元素最小或最大 对记录序列进行排序! 对记录序列进行排序! 12 36 65 81 73 55 40 49 14 34 27 98

不 是堆

堆排序的特征
堆排序是在排序过程中, 堆排序是在排序过程中,将向量中 存储的数据看成一棵完全二叉树, 存储的数据看成一棵完全二叉树,利用完 全二叉树中双亲结点和孩子结点之间的 内在关系来选择关键字最小的记录, 内在关系来选择关键字最小的记录,即 待排序记录仍采用向量数组方式存储, 待排序记录仍采用向量数组方式存储, 并非采用树的存储结构, 并非采用树的存储结构,仅仅是采用完 全二叉树顺序结构的特征进行分析处理。 全二叉树顺序结构的特征进行分析处理。

堆排序即是利用堆的特性对记录序列 堆排序即是利用堆的特性对记录序列 即是利用堆的特性 进行排序的一种排序方法,过程如下 过程如下: 进行排序的一种排序方法 过程如下: 1、对给定序列建堆; 、对给定序列建堆; 2、输出堆顶;(首元素与尾元素交换 首元素与尾元素交换) 、输出堆顶; 首元素与尾元素交换 3、对剩余元素重建堆;(筛选首元素 3、对剩余元素重建堆;(筛选首元素) 筛选首元素) 4、重复 ,3,直至所有元素输出。 、重复2, ,直至所有元素输出。

问题: 问题
1、如何由一个无序序列“建堆”? 、如何由一个无序序列“建堆” 2、输出堆顶后如何“重建堆” ? 、输出堆顶后如何“重建堆” 两个问题均可归结为“ 问题? 两个问题均可归结为“筛选”问题?

例如: 例如:
{ 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } 交换 98 和 12 { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 经过筛选 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } 交换 81 和 12 {12, 73, 49, 64, 36, 27, 40, 55, 81, 98 }

继续重复,可的有序序列。

所谓“筛选”指的是,对一棵左/ 所谓“筛选”指的是,对一棵左 右子树均为堆的完全二叉树, 调整” 右子树均为堆的完全二叉树,“调整” 根结点使整个二叉树也成为一个堆 使整个二叉树也成为一个堆。 根结点使整个二叉树也成为一个堆。 筛 选 堆 堆

例如: 例如

12 73 81

81 12 98
比较

49 27 40

64 73 55 12 64 98 12

36

是大顶堆

但98 和12 互换后(去掉98), 不为堆。 因此,需要对它进行“筛选 筛选”(调整12)。 筛选 建初堆也是一个“筛选 的过程! 筛选”的过程 建初堆也是一个 筛选 的过程!

例如给定的关键字序列为: 例如给定的关键字序列为 40, 55 ,49, 73, 12 ,27, 98, 81, 64, 36
98 40 81 55 81 73 55 73 81 36 12 27 98 49 40 49 98

64 12 36 是从最后一个有孩子的结点开始, 建初堆是从最后一个有孩子的结点开始,往 前逐个结点进行“筛选”的过程。 前逐个结点进行“筛选”的过程。 现在, 右子树都已经调整为堆, 现在,左/右子树都已经调整为堆,最后只要 调整根结点,使整个二叉树是个“ 即可。 调整根结点,使整个二叉树是个“堆”即可。

筛选算法
void sift(RecordType r[], int k,int m) ( /* 调整 调整r[k],使整个序列 ,使整个序列r[k..m]满足堆的性质 */ 满足堆的性质 { t= r[k] ; x=r[k].key ; i=k ;j=2*i ;finished=FALSE ; while( j<=m && ! finished ) {if (j<m && r[j].key< r[j+1].key ) j=j+1; ; if ( x>= r[j].key) finished=TRUE ; /* 筛选完毕 */ else {r[i] = r[j] ;i=j ;j=2*i ;} /* 继续筛选 */ } r[i] =t ; /* r[k]填入到恰当的位置 */ 填入到恰当的位置 }

建初堆算法
void crt_heap(RecordType r[], int length )
/*对记录数组 建堆,length为数组的长度 对记录数组r建堆 为数组的长度*/ 对记录数组 建堆, 为数组的长度

{ n= length; for ( i=n/2 ; i>= 1 ; --i) sift(r,i,n) ; ,, }

稳定? 稳定?

堆排序算法
void HeapSort(RecordType r[],int length) ( ) /* 对r[1..n]进行堆排序 进行堆排序*/ 进行堆排序 { crt_heap(r, length);n= length; ; for ( i=n ; i>= 2 ; --i) {b=r[1]; r[1]= r[i]; r[i]=b; /* 将堆顶记录和堆中最后一个记录互换 */ sift(r,1,i-1); /* 进行筛选 使r[1..i-1]成为堆 */ 进行筛选,使 , , ; 成为堆 } }

堆排序时间复杂度分析: 堆排序时间复杂度分析:
1. 对深度为 k 的堆,“筛选”所需进行的关键字 的堆, 筛选” 比较的次数至多为2(k-1); 比较的次数至多为 ; 2. n 个关键字的堆深度为 ?log2n?+1, 初建堆所需 初建堆 ? 进行的关键字比较的次数至多为: 进行的关键字比较的次数至多为:n* ?log2n?; ? 3. 重建堆 n-1 次,所需进行的关键字比较的次数 不超过: 不超过:(n-1)*2?log2n?; ? ?

因此,堆排序的时间复杂度为(最坏情况): 因此,堆排序的时间复杂度为(最坏情况): O(n* ?log2n? + (n-1)*2?log2n?)= O(nlogn)。 ? ? ? 。

9.5 归并排序
归并排序的过程基于下列基本思想 归并排序的过程基于下列基本思想 进行: 进行: 将两个或两个以上的有序子序列 归并” 为一个有序序列。 “归并” 为一个有序序列。

在内部排序中,通常采用的是 路归并 在内部排序中,通常采用的是2-路归并 排序。即:将两个位置相邻的有序子序列 排序。 归并为一个有序的序列。 归并为一个有序的序列。
有序子序列 r[l..m] 有序子序列 r[m+1..n]
归 并

有 序 序 列 r[l..n]
这个操作对顺序表而言,是轻而易举的。 这个操作对顺序表而言,是轻而易举的。

例:
(19) (13) (05) (27) (01) (26) (31) (16)

(13,19)

(05,27)

(01,26)

(16,31)

(05,13,19,27)

(01,16,26,31)

(01,05,13,16,19,26,27,31)

完整的归并排序过程为:先分组再归并。 完整的归并排序过程为:先分组再归并。 52, 23, 80, 36, 68, 14 [ 52, 23, 80] [ 52, 23 ] [80] [ 52] [23] [ 23, 52] [ 23, 52, 80] [ 14, 23, 36, [36, 68, 14] [36, 68] [14] [36] [68] [36, [14, 52, 68] 36, 68] 68, 80]

合并算法
void Merge ( RecordType r1[],
int low, int mid, int high, RecordType r[])

/*r1[low..mid]和r1[mid+1..high]分别有序,将它们合并 和 分别有序, 分别有序 将它们合并*/

{i=low;j=mid+1; k=low; ; ; ; while ( (i<=mid)&&(j<=high) ) {if ( r1[i].key<=r1[j].key ) {r[k]=r1[i] ; ++i;} ; else {r[k]=r1[j] ; ++j;} ; ++k ; } if ( i<=mid ) r[k..high] =r1[i..mid]; ; if ( j<=high ) r[k..high] =r1[j..high]; ; }

2-路归并排序算法
void MergeSort (RecordType
r1[], int low, int high, RecordType r[])

/*r1[low..high]经排序后放在 经排序后放在r[low..high]中,r2[low..high]为辅助空间 */ 经排序后放在 中 为辅助空间

{ RecordType r2 [hight-low+1] ; if ( low==high ) r[low]=r1[low]; ; else{mid=(low+high)/2; ; MergeSort(r1,low, mid, r2); , , ; MergeSort(r1,mid+1,high, r2); , , ; Merge (r2,low,mid,high, r);} , , , , ; }

稳定? 稳定?

归并排序的复杂度分析: 归并排序的复杂度分析:
容易看出, 容易看出,对 n 个记录进行归并排序的 时间复杂度为Ο 时间复杂度为Ο(nlogn)。即: 。 每一趟归并的时间复杂度为 O(n), , 总共需进行 ?log2n? 趟。 ? 归并排序的空间复杂度较高, 归并排序的空间复杂度较高,需要有长 度为n的辅助数组 即为O(n)。 的辅助数组, 。 度为 的辅助数组,即为

9.6 分配类排序
基数排序是一种借助“多关键字排序” 基数排序是一种借助“多关键字排序” 借助 的思想来实现“单关键字排序” 的思想来实现“单关键字排序”的内部 排序算法。 排序算法。 多关键字的排序 基数排序

一、多关键字的排序
n 个记录的序列 { R1, R2, …,Rn} 对关键字 , 是指: (Ki0, Ki1,…,Kid-1) 有序是指: 有序是指 , 对于序列中任意两个记录R 对于序列中任意两个记录 i 和 Rj (1≤i<j≤n) ≤ ≤ 都满足下列 词典 有序关系: 满足下列 词典)有序关系: 下列(词典 有序关系 (Ki0, Ki1, …,Kid-1) < (Kj0, Kj1, …,Kjd-1) , , 其中: 最主/最高” 其中: K0 被称为 “最主/最高”位关键字 Kd-1 被称为 “最次/最低”位关键字 最次/最低”

实现多关键字排序通常有两种方法: 实现多关键字排序通常有两种方法: 最高位优先MSD法 最高位优先 最低位优先LSD法 最低位优先 法 以扑克牌排序为例: 以扑克牌排序为例:
将扑克牌的排序看成由花色和面值两个关键字 将扑克牌的排序看成由花色和面值两个关键字 花色 进行排序的问题。若规定花色和面值的顺序如下: 进行排序的问题。若规定花色和面值的顺序如下: 花色:梅花★ 方块◆ 红桃● 黑桃▲ 花色:梅花★< 方块◆< 红桃●< 黑桃▲; 面值:A<2 <J<Q<K; 面值:A<2<3<…<10<J<Q<K; <10<J<Q<K 花色的优先级高于面值; 花色的优先级高于面值; 则一副牌从小到大的顺序为: 则一副牌从小到大的顺序为: A,★2,…, A,◆2,…, ★A,★2, ,★K;◆A,◆2, ,◆K; A,●2,…, A,▲2,…, ●A,●2, ,●K;▲A,▲2, ,▲K。

扑克牌的排序过程
访法一(LSD) : 访法一

访法二(MSD): : 访法二

最高位优先MSD法: 最高位优先
进行排序,并按K 先按K0进行排序,并按 0 的不 分成若干子序列, 同值将记录序列分成若干子序列 同值将记录序列分成若干子序列, 之后再分别按 进行排序, 之后再分别按 K1 进行排序,...…, , 依次类推, 直至最后分别按最次位 依次类推 直至最后分别按最次位 分别 关键字K 排序完成为止。 关键字 d-1排序完成为止。

最低位优先LSD法: 法 最低位优先
先按K 进行排序, 先按 d-1 进行排序,然后按 Kd-2 进 排序,依次类推, 行稳定的排序,依次类推,直至按最主 位关键字K0 排序完成为止。 位关键字 排序完成为止。 LSD排序过程中不需要根据 前一个” LSD排序过程中不需要根据 “前一个” 关键字的排序结果, 关键字的排序结果,将记录序列分割成若 干个子序列。 干个子序列。

例:学生记录含三个关键字: 学生记录含三个关键字: 系别、班号和班内的序列号,其中以系别 系别、班号和班内的序列号,其中以系别 为最主位关键字。 为最主位关键字。 LSD的排序过程如下: 的排序过程如下: 的排序过程如下
无序序列 3,2,30 1,2,15 3,1,20 对K2排序 1,2,15 2,3,18 3,1,20 对K1排序 3,1,20 2,1,20 1,2,15 对K0排序 1,2,15 2,1,20 2,3,18
2,3,18
2,1,20

2,1,20
3,2,30

3,2,30 3,1,20

2,3,18 3,2,30

二、基数排序
对于数字型或字符型的单关键字, 对于数字型或字符型的单关键字,可 单关键字 以看成是由多个数位或多个字符 多个数位 字符构成的多 以看成是由多个数位或多个字符构成的多 关键字,而此时每个 关键字” 每个“ 关键字,而此时每个“关键字”的取值范 是原关键字的基数 基数。 围是原关键字的基数。 每个关键字的取值范围相同 取值范围相同时 当每个关键字的取值范围相同时,其排 序可采用“分配”而非“比较”的方法进行。 序可采用“分配”而非“比较”的方法进行。 对于数字型或字符型的“多关键字” 对于数字型或字符型的“多关键字” , 可用LSD法,并采用 “分配-收集”再“分 分配-收集” 可用 法 收集” 的办法实现排序, 这就是基数 的办法实现排序 配-收集”…的办法实现排序 这就是基数 排序。 排序。

例如: 例如:对下列这组关键字 {369,367,167,239,237,138,230,139} , , , , , , ,
个位数” 分配” 首先按其 “个位数” 取值 “分配” 成 10 组, 收集” 在一起; 之后按从 0 至 9 的顺序将各组 “收集” 在一起; 十位数” 分配” 然后按其 “十位数” 取值 “分配” 成 10 组, 的顺序将各组“收集” 起来; 之后再按从 0 至 9 的顺序将各组“收集” 起来; 百位数” 分配” 最后按其 “百位数” 取值 “分配” 成 10 组, 的顺序将各组“收集” 起来。 之后再按从 0 至 9 的顺序将各组“收集” 起来。

实现基数排序时, 实现基数排序时,为减少所需辅助存储 空间,可采用链表作存储结构。 空间,可采用链表作存储结构。

具体方法: 具体方法:
待排序记录以链表为存储结构; 1.待排序记录以链表为存储结构; 分配” 当前“关键字位” 2.“分配” 时,按当前“关键字位”将记录分 链队列” 配到不同的 “链队列” 中,每个队列中记 当前“关键字位” 相同; 录的 当前“关键字位” 相同; 收集” 将各队列按关键字从小到大 按关键字从小到大首 3.“收集”时,将各队列按关键字从小到大首 尾相链构成一个新链表; 尾相链构成一个新链表; 构成一个新链表 对每个关键字位重复2 4.按LSD对每个关键字位重复 、3, 便可获 , 得有序序列。 得有序序列。

例如: 例如:
进行第一次分配
f[0]

p→369→367→167→239→237→138→230→139


f[7]

→230

← r[0]

→367→167→237← r[7] ← r[8]

f[8] →138 f[9]

→369→239→139← r[9] 进行第一次收集
p→230→367→167→237 →138 →369→239→139

p→230→367→167→237→138→369→239→139

进行第二次分配
f[3]


f[6]

→230 →237→138→239→139 ← →367→167→369 ←

r[3] r[6]

进行第二次收集
p→230→237→138→239→139 →367→167→369

p→230→237→138→239→139→367→167→369

进行第三次分配
f[1] f[2] f[3]

→138→139 →167← r[1] →230→237→239← r[2] →367→369 ← r[3]

… 进行第三次收集

p→138→139→167→230→237→239→367→369

已得到记录的有序序列

存储结构: 存储结构:
为有效地存储和重排记录, 为有效地存储和重排记录,算法采用静态 链表,有关数据类型的定义如下: 链表,有关数据类型的定义如下:
RADIX 10 KEY_SIZE 6 LIST_SIZE 20 int KeyType; struct { KeyType keys[KEY_SIZE]; OtherType other_data; int next; } RecordType1; typedef struct { RecordType1 r[LIST_SIZE+1]; int length; int keynum; } SLinkList; typedef int PVector[RADIX]; #define #define #define typedef typedef

/* 子关键字数组 */ /* 其它数据项 */ /* 静态链域 */

r[0]为头结点 /* r[0]为头结点 */

/* 静态链表 */

分配算法: 分配算法:
void Distribute(RecordType1 RecordType1
*/ r[], r[] int i, PVector head, PVector tail) /*数组 已按低位关键字 数组r已按低位关键字 进行了“ 数组 已按低位关键字key[i+1],…,key[d]进行了“低位优先 ”排序 , , 进行了 低位优先”

{ for ( j=0 ; j<=RADIX-1 ; ++j) RADIXRADIX head[j]=0; /* 将RADIX个队列初始化为空队列 */ RADIX个 ; p= r[0].next ; /* p指向链表中的第一个记录 */ 指向链表中的第一个记录 while( p!=0 ) {j=Order(r[p].key[i]); /* 用第 位关键字求相应队列号 */ ; 用第i位关键字求相应队列号 if ( head[j]==0 ) head[j]=p ; /* 将p结点加入第 队列 */ 结点加入第j队列 结点加入第 else r[tail[j]].next=p; ; tail[j]=p; p= r[p].next ;} ; }

收集算法: 收集算法:
void Collect (RecordType RecordType
r[], r[] PVector head, PVector tail) /* 从0到RADIX-1 扫描各队列,将非空队列首尾相接成一个链表 */ 到RADIX- 扫描各队列,

{j=0;while (head[j]==0 ) ++j ; /* 找第一个非空队列 */ ; r[0].next =head[j] ; t=tail[j] ; /* 寻找并串接所有非空队列 */ while ( j<RADIX-1 ) RADIXRADIX {++j ; while ( (j<RADIX-1 ) && (head[j]==0 ) ) RADIXRADIX ++j ; / * 找下一个非空队列 */ if ( head[j]!=0 ) /* 链接非空队列 */ {r[t].next =head[j] ; t=tail[j] ;} } r[t].next =0; /* t指向最后一个非空队列中的最后一个结点 */ 指向最后一个非空队列中的最后一个结点 }

基数排序算法: 基数排序算法:
void RadixSort (RecordType r[],int length ) RecordType /* length个记录存放在数组 中,进行基数排序 length个记录存放在数组 个记录存放在数组r中 进行基数排序*/ { n= length; ; for ( i=0 ; i<= n-1 ; ++i) r[i].next=i+1; /* 构造静态链表 */ ; r[n].next =0 ;d= keynum; keynum; for ( i =d-1 ; i>= 0; --i ) /* 从最低位子关键字开始,进行 趟分配 和 收集 从最低位子关键字开始,进行d趟分配 收集*/ {Distribute(r,i,head,tail); /* 第i趟分配 */ ,, , ; 趟分配 Collect(r,head,tail) /* 第i趟收集 */ , , 趟收集 }}

基数排序的时间复杂度为O(d(n+rd)) 基数排序的时间复杂度为 其中:分配为O(n) 其中:分配为 收集为O(rd)(rd为“基”) 为 收集为 d为“分配 收集”的趟数 为 分配-收集 收集”

9.7 各种排序方法的综合比较 1. 插入类 直接插入排序和希尔排序 直接插入排序和 2. 交换类 3. 选择类 4. 归并类 5. 分配类
起泡排序和快速排序。 起泡排序和快速排序。 简单选择排序和 简单选择排序和堆排序 归并排序 基数排序

一、性能比较
排序方法 *均时间 最坏时间 辅助空间 简单排序 希尔排序 O(n2) O(n3/2) O(n2) O(n2) O(1) O(d[k]) O(logn) O(1) O(n) O(rd) 稳定性

稳定
非稳定 非稳定 非稳定 稳定 稳定

快速排序 O(nlogn) 堆排序

O(nlogn) O(nlogn)

归并排序 O(nlogn) O(nlogn) 基数排序 O(d*n) O(d*n)

通过分析和比较,可以得出以下结论: 通过分析和比较,可以得出以下结论:
简单排序一般只用于n值较小的情况; 简单排序一般只用于n值较小的情况; 归并排序适用于n值较大的情况; 归并排序适用于n值较大的情况; 基数排序适用于n值很大而关键字的位数d 基数排序适用于n值很大而关键字的位数d较 小的序列; 小的序列; 快速排序是排序方法中最好的方法。 快速排序是排序方法中最好的方法。

二、内部排序时间复杂度下限分析
本章讨论的各种排序方法, 本章讨论的各种排序方法,除基数排序 基于“ 外,其它方法都是基于“比较”进行排序 其它方法都是基于 比较” 的排序方法。 的排序方法。 可以证明, 这类排序法可能达到的最快 可以证明 这类排序法可能达到的最快 的时间复杂度为O(nlogn)。(基数排序不是 。 的时间复杂度为

基于 “比较关键字”的排序方法,所以它 不受这个限制。)

例如:对三个关键字进行排序的判定树如下: 例如 对三个关键字进行排序的判定树如下: 对三个关键字进行排序的判定树如下
n
K1<K3 K1<K2 y K2<K3

n
K2< K3 K2<K1<K3

n
K1<K3 K1<K2<K3 K1<K3<K2

n
K3<K2<K1 K2<K3<K1

n
K3<K1<K2

1.树上的每一次“比较”都是必要的; 树上的每一次“比较”都是必要的 每一次 必要 2.树上的叶子代表所有可能的排序结果。 树上的叶子代表所有可能的排序结果。 叶子代表所有可能的排序结果

一般而言, 个关键字进行排序, 一般而言 对n个关键字进行排序 可得 个关键字进行排序 到的结果有n! 个叶子), 由于含n! 到的结果有 种(n! 个叶子 由于含 个 叶子的二叉树的深度不小于? 叶子的二叉树的深度不小于?log2(n!)? +1, ? 所以对 n 个关键字进行排序的比较次数至 斯蒂林*似公式)。 少是 ?log2(n!)? ≈ nlog2n (斯蒂林*似公式 。 ? 斯蒂林*似公式 所以, 基于“比较关键字” 所以 基于“比较关键字”进行排序的 排序方法, 排序方法 可能达到的最快的时间复杂度为 O(nlogn)。 。

9.8 总结与提高
1.了解排序的定义和各种排序方法的特点。 1.了解排序的定义和各种排序方法的特点。 了解排序的定义和各种排序方法的特点 熟练掌握各种排序方法及各种排序方法排 序时每趟的变化过程。 序时每趟的变化过程。 插入排序(希尔);交换排序(快速); 插入排序(希尔);交换排序(快速); );交换排序 选择排序( 选择排序(堆); 归并排序; 归并排序; 基于“分配-收集”的基数排序。 基于“分配-收集”的基数排序。

2、掌握各种排序方法的时间复杂度 、
的分析方法。能从“ 的分析方法。能从“关键字间的比较次 数”分析排序算法的*均情况和最坏情 况的时间性能。 况的时间性能。 按*均时间复杂度划分, 按*均时间复杂度划分,内部排序可分 的简单排序方法、 为三类: 为三类:O(n2) 的简单排序方法、O(nlogn) 的高效排序方法和O(dn)的基数排序方法。 的基数排序方法。 的高效排序方法和 的基数排序方法

3.理解排序方法“稳定”或“不稳定” .理解排序方法“稳定” 不稳定” 的含义, 的含义,弄清楚在什么情况下要求应用 的排序方法必须是稳定的。 的排序方法必须是稳定的。 4. 了解外部排序的基本过程及其时间 分析。 分析。

典型例题: 典型例题:
设有10000个元素,要求找出最小的10 10000个元素 10个 例1 :设有10000个元素,要求找出最小的10个, 选择合适的排序方法。 选择合适的排序方法。

堆排序! 堆排序!
例 2: n=7时,给出快速排序最好情况的初始序列。 时 给出快速排序最好情况的初始序列。 [ 4,1,3,2,6,5,7 ] , , , , , , 例3 哈希排序:设有300个记录,其关键字均为 哈希排序:设有300个记录, 300个记录 小于1000的正整数,且互不相等。 1000的正整数 小于1000的正整数,且互不相等。设计一排序 方法,比较移动次数尽可能少。 方法,比较移动次数尽可能少。
设置辅助数组b[1..999],按哈希法将记录分配, 设置辅助数组b[1..999],按哈希法将记录分配,再回收 b[1..999],按哈希法将记录分配

例4 荷兰国旗问题: 荷兰国旗问题:
设有一个仅由红、 设有一个仅由红、白、蓝三种颜色的色 条组成的序列,要求在O(n) 条组成的序列,要求在O(n) 的时间内将其排 列成荷兰国旗。 列成荷兰国旗。 例如:初始序列为[ 例如:初始序列为[蓝,白,红,白,蓝,红,白,白,红,蓝]
要求排列结果为[红,红,红,白,白,白,白,蓝,蓝,蓝] 要求排列结果为[

算法选择: 算法选择:1、简单选择排序思想; 简单选择排序思想;
两趟选择:第1趟选红色,第2趟选白色。

快速排序思想; 2、快速排序思想;
算法见P333.

基数排序思想。 3、基数排序思想。
经过1趟分配、收集即可。

荷兰国旗问题的快速排序算法
个指示器r,w,b, 指示各区下一个单元;初始时: 设3个指示器r,w,b, 指示各区下一个单元;初始时: r=w=0;b=n-1,w相当于low,b相当于high处理 相当于low,b相当于high处理; r=w=0;b=n-1,w相当于low,b相当于high处理; 最终:[1..r-1]红色,[r..w-1]白色,[w..n-1]蓝色。 最终:[1..r-1]红色,[r..w-1]白色,[w..n-1]蓝色。 :[1..r 红色,[r..w 白色 蓝色 Void sord(int L[ ], int n) {int x,r,w,b; r=w=0;b=n-1 while(w<=b) {x=L[W];if (x==1) {L[w]=L[r]; w++; L[r]=x; r+=;} else if (x==2) w++; else {L[w]=L[b]; L[b]=x; b--;} }}

第九章结束


相关文档

  • 西安邮电学院 《数据结构》曾艳 第2章 线性表
  • 西安邮电学院 《数据结构》曾艳 第5章 数组
  • 西安邮电学院 《数据结构》曾艳 第3章 栈和队列
  • 西安邮电学院 《数据结构》曾艳 第6章 树和二叉树
  • 西安邮电学院 《数据结构》曾艳 第1章 绪论
  • 数据结构教程 第9章 排序
  • 数据结构:第9章 排序
  • 数据结构与算法 第9章 排序
  • 数据结构教程 第九章 排序
  • 数据结构第9章-排序
  • 猜你喜欢

  • 贵州省紫望高速公路火花互通立交方案选型与设计
  • 大学生的三下乡心得体会范文
  • 2019年-小学主题班会课件:文明礼貌伴我终身-文档资料-PPT精选文档
  • 广东省深圳市宝安中学-学年第一学期高二化学期中试题
  • 人教版八下文学常识选择题
  • 蜂鸣器的驱动电路设计及原理分析
  • 东莞市辉炫建筑装饰工程有限公司企业信息报告-天眼查
  • 被ef 汉化雷到了
  • 香港华杨国际集团证券投资有限公司企业信用报告-天眼查
  • 最新部编版语文一年级上册期末测试卷及答案(2019-2020学年)
  • 【发展战略】加快推进我国城乡一体化发展进程的思考
  • mysql varchar 转 decimal
  • 厦门科宝商贸有限公司企业信用报告-天眼查
  • 华东垃圾焚烧发电厂建设可行性研究报告-广州中撰咨询
  • 沟通,从心开始 师德交流材料
  • 发改委调查药品出厂价 新一波降价潮箭在弦上
  • 牛奶美容
  • 肥城市五金交电化工公司企业信用报告-天眼查
  • 今天我作业未完成作文【小学六年级1000字】
  • 敖力布皋镇中心学校2018-2019学年四年级下学期数学期中模拟试卷含解析(1)
  • 小学开学典礼五年级同学代表发言稿
  • html中js函数定义方式,JavaScript深入理解函数 - 函数的定义
  • 2019年1月自考西方政治制度部分试题答案
  • 行业分析2018-2023年中国畜牧机械制造行业市场发展预测及投资咨询报告(目录)
  • 爱的哲理句子
  • 如何上好高中英语阅读课
  • 福州汀鑫商贸有限公司企业信用报告-天眼查
  • 微软与曙光签署高性能计算领域全面合作备忘录
  • 学生会新学期工作规划学生会新学期纳新的工作计划
  • 【作文】关于寓言童话作文:颜色拍买会
  • 川教初中历史八上《第14课全国抗日战争的开始》PPT课件 (5)
  • 产业转移与中部地区招商引资模式转换分析
  • 中兴通讯技术杂志社北京迎春联谊会隆重召开
  • 县级供电公司纪检监察干部能力与素质提升研究
  • 六年级语文【下册】开学检测试题 沪教版D卷 附答案
  • 体坛英语新闻:Robinho could return to play against Cagliari
  • 高二作文《你自己的样子》800字(共10页PPT)
  • CCI和KDJ指标搜股公式
  • 【java基础】IO流是啥?有啥用?(上)
  • 2016届高考化学一轮复习方案课件(人教版)第2讲_物质的量在化学实验和化学计算中的应用(1)
  • 第二学期小学语文教研组工作计划范文
  • 【最新2018】房屋租赁合同3页 (3000字)-word范文模板 (2页)
  • 电脑版