数据结构 第10章 排序2-快速排序

数据结构

数据结构讲义 第10章 排序 10章- 快速排序

数据结构

10.3 交换排序交换排序的基本思想是：两两比较待排序记录的关键 交换排序的基本思想是： 如果发生逆序( 码，如果发生逆序(即排列顺序与排序后的次序正好 相反),则交换之，直到所有记录都排好序为止。 ),则交换之 相反),则交换之，直到所有记录都排好序为止。 交换排序的主要算法有： 交换排序的主要算法有： 1) 冒泡排序 2) 快速排序

数据结构

1) 冒泡排序基本思路：每趟不断将记录两两比较，并按“前小后大” 基本思路：每趟不断将记录两两比较，并按“前小后大” 前大后小” 规则交换。 (或“前大后小”)规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素； 还能同时部分理顺其他元素；一旦下趟没有交换发 还可以提前结束排序。 生，还可以提前结束排序。 前提：顺序存储结构 前提： ),请写出 例：关键字序列 T=(21,25,49,25*,16,08),请写出 ， , , , , ), 冒泡排序的具体实现过程。 冒泡排序的具体实现过程。初态： 初态： 第1趟 趟 第2趟 趟 第3趟 趟 第4趟 趟 第5趟 趟

21,25,49, 25*,16, 08 , , , , , 21,25,25*,16, 08 , 49 , , , , 21,25, 16, 08 ,25*,49 , , , , 21,16, 08 ,25, 25*,49 , , , , 16,08 ,21, 25, 25*,49 , , , , 08,16, 21, 25, 25*,49 , , , , ,

数据结构

冒泡排序练习设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排 列。冒泡排序一趟扫描的结果是 。 ( H, C, Q, P, A, M, S, R, D, F, X , Y )

数据结构

void bubble_sort(SqList *L) { int m,i,j,flag=1; RecordType x; m=nm=n-1; while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(L->r[j].key>Lif(L->r[j].key>L->r[j+1].key) } }

{

flag=1; x=Lx=L->r[j]; L->r[j]=L->r[j+1]; >r[j]=LL->r[j+1]=x;

} m--; --;

数据结构

冒泡排序的算法分析时间效率： 时间效率：O(n2) —因为要考虑最坏情况 空间效率：O(1) —只在交换时用到一个缓冲单元 空间效率： 稳 定 性： 稳定 —25和25*在排序前后的次序未改变 25和 详细分析： 详细分析： 最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 最好情况： 最好情况 初始排列已经有序，只执行一趟起泡， 次关键码比较，不移动对象。 次关键码比较，不移动对象。 最坏情形：初始排列逆序，算法要执行 1趟起泡，第i趟 最坏情形： 最坏情形 初始排列逆序，算法要执行n-1趟起泡， 趟 (1≤ i< n) 做了 i 次关键码比较，执行了 做了n- 次关键码比较，执行了n-i 次对象交换。 次对象交换。 ≤ < 此

时的比较总次数KCN和记录移动次数 和记录移动次数RMN为： 此时的比较总次数 和记录移动次数 为1 KCN = ∑(n i) = n(n 1) 2 i =1 RM = 3∑(n i) = Ni =1 n 1 n 1

3 n(n 1) 2

数据结构

2) 快速排序基本思想： 从待排序列中任取一个元素 (例如取第一 基本思想：

个) 作为中心，所有比它小的元素一律前放，所 作为中心，所有比它小的元素一律前放， 有比它大的元素一律后放，形成左右两个子表； 有比它大的元素一律后放，形成左右两个子表； 然后再对各子表重新选择中心元素并依此规则调 直到每个子表的元素只剩一个。 整，直到每个子表的元素只剩一个。此时便为有 序序列了。 序序列了。 优点：因为每趟可以确定不止一个元素的位置， 优点：因为每趟可以确定不止一个元素的位置，而且 呈指数增加，所以特别快！ 呈指数增加，所以特别快！ 前提： 前提：顺序存储结构

数据结构

例1:关键字序列 T=(21,25,49,25*,16,08), T=(21,25,49,25*,16,08), 请写出快速排序的算法步骤。 请写出快速排序的算法步骤。设以首元素为枢轴中心

, , , , , 初态： 初态： 21, 25, 49, 25*,16, 08第1趟：( 16,08 ), 21 ,( 25,25*,49 ) 趟 第2趟： 趟 第3趟： 趟

(08),16,21, 25,(25*,49) , , 08,16,21,25, 25*,(49) , , , , ,

问题： 问题：1. 这种不断划分子表的过程，计算机如何自动实现？ 这种不断划分子表的过程，计算机如何自动实现？ 2. “快速排序”是否真的比任何排序算法都快？ 快速排序”是否真的比任何排序算法都快？

数据结构

1.这种不断划分子表的过程， 1.这种不断划分子表的过程，计算机如何自动 这种不断划分子表的过程 实现？ 实现？

编程时： 编程时： ①每一趟的子表的形成是采用从两头向中间交 替式逼近法； 替式逼近法； 由于每趟中对各子表的操作都相似， ②由于每趟中对各子表的操作都相似，主程序 可采用递归算法。 可采用递归算法。 具体程序可见教材P275 具体程序可见教材P275

数据结构

例2:关键字序列 T=(21,25,49,25*,16,08),请 T=(21,25,49,25*,16,08), ),请 写出快速排序算法的一趟实现过程。 写出快速排序算法的一趟实现过程。 high pivotkey=21 lowr[i]初态 第1趟 趟 21 0 1 2

3 4921 49

4

5

6

2108

2516 25

25*25*

1649 16

0825 08

( 08 ,16 ) 21 Low=high=3 本趟停止， Low=high=3,本趟停止，将 支点定位并返回位置信息

( 25* , 49, 25 ) 25 跑到了前面，不稳定！ 跑到了前面，不稳定！*

数据结构

快速排序练习设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排 列。快速排序一趟扫描的结果是 。 ( F, H, C, D, P, A, M, Q,

R, S, Y, X )

数据结构

快速排序算法详细分析： 快速排序算法详细分析： 快速排序是递归的，需要有一个栈存放每层递归调用 快速排序是递归的， 快速排序是递归的 时的指针和参数(新的low high) low和 时的指针和参数(新的low和high)。 可以证明，函数 可以证明，函数quicksort的平均计算时间也是 可以证明 的平均计算时间也是 O(nlog2n)。实验结果表明：就平均计算时间而言，快 。实验结果表明：就平均计算时间而言， 速排序是我们所讨论的所有内排序方法中最好的一个。 速排序是我们所讨论的所有内排序方法中最好的一个。 最大递归调用层次数与递归树的深度一致，理想情况 最大递归调用层次数与递归树的深度一致， 最大递归调用层次数与递归树的深度一致 因此， 为 log2(n+1) 。因此，要求存储开销为 o(log2n)。 。 如果每次划分对一个对象定位后，该对象的左侧子序 如果每次划分对一个对象定位后， 如果每次划分对一个对象定位后 列与右侧子序列的长度相同， 列与右侧子序列的长度相同，则下一步将是对两个长度 减半的子序列进行排序，这是最理想的情况。此时，快 减半的子序列进行排序，这是最理想的情况。此时， 速排序的趟数最少。 速排序的趟数最少。

数据结构

在最坏的情况，即待排序对象序列已经按 在最坏的情况， 在最坏的情况 其关键码从小到大排好序的情况下， 其关键码从小到大排好序的情况下，其递 归树成为单支树， 归树成为单支树，每次划分只得到一个比 上一次少一个对象的子序列。这样， 上一次少一个对象的子序列。这样，必须 经过 n-1 趟才能把所有对象定位，而且第 趟才 …… 此处隐藏：3109字，全部文档内容请下载后查看。喜欢就下载吧 ……