第2章 分治策略3快速排序
时间：2025-05-02
算法课件 改自MIT
2.5 快速排序问题 QuickSort由著名计算机科学家霍尔(C.A.R.Hoare)给出。 由著名计算机科学家霍尔 给出。 给出 把原序列分成两个子问题， 把原序列分成两个子问题，在被分成的两个子 问题以后不再需要归并。 问题以后不再需要归并。 被分成的两个子问题必须满足一子问题中的所 有元素都小于或等于另一子问题的任何一个元 素。
算法课件 改自MIT
QuickSortSelect a pivot (partitioning element) Rearrange the list so that all the elements in the positions before the pivot are smaller than or equal to the pivot and those after the pivot are larger than the pivot Exchange the pivot with the last element in the first (i.e., ≤ sublist) – the pivot is now in its final position Sort the two sublists2
算法课件 改自MIT
2.5 快速排序问题基本策略是： 基本策略是：
将数组A[1:n]分解成两个子数组 分解成两个子数组B[1:p]和 将数组 分解成两个子数组 和 B[p+1:n],使得 ，使得B[1:p]中的元素均不大于 中的元素均不大于 B[p+1:n]中的元素，然后分别对这里两个 中的元素， 中的元素 数组中的元素进行排序(非降的), ),最后 数组中的元素进行排序(非降的),最后 再把两个排好序的数组接起来即可。 再把两个排好序的数组接起来即可。p A[i]≤p A[i]>p
算法课件 改自MIT
2.5 快速排序问题
选取A的某个元素 选取 的某个元素t=A(s),然后将其他元素重 的某个元素 ， 新排列， 中所有在t以前出现的元素都 新排列，使A(1:n)中所有在 以前出现的元素都 中所有在 小于或等于t,而在t之后出现的元素都大于或 小于或等于 ，而在 之后出现的元素都大于或 等于t。 等于 。A(1) A(2) … A(s-1) A(s) A(s+1) … A(n)
经过一次划分后
t
划分元素
A(1)
A(2)
…
A(j)
t
A(k)
…
A(n)
每个元素都小于或等于t 每个元素都小于或等于
每个元素都大于或等于t 每个元素都大于或等于4
算法课件 改自MIT
The partition algorithm
算法课件 改自MIT
2.5快速排序问题 快速排序问题
算法步骤分解(Divide):以a[p]为基准元素将 以 为基准元素将a[p:r]划分成 划分成3 分解 为基准元素将 划分成 使得a[p:q-1]中任何一 段a[p:q-1],a[q]和a[q+1:r],使得 和 使得 中任何一 个小于等于a[q],下标 在划分过程中确定。 下标q在划分过程中确定 个小于等于a[q],下标q在划分过程中确定。 递归求解(conquer):通过递归调用快速排序算法 递归求解 通过递归调用快速排序算法 分别对a[p:q-1]和a[q+1:r]进行排序。 进行排序。 分别对 和 进行排序 合并(Merge):由于对 由于对a[p:q-1]和a[q+1:r]的排序是 合并 由于对 和 的排序是 就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好 就地进行的，所以在 和 都已排好 的序后步需执行任何计算a[p:r]就已排好序。 就已排好序。 的序后步需执行任何计算 就已排好序6
算法课件 改自MIT
2.5快速
排序问题 快速排序问题 快速排序问题
快速排序template<class Type> void QuickSort(Type a[ ], int p,int r) a的终止位置 的终止位置 { if(p<r) Partition函数负责将 函数负责将 { a进行一次分割，返 进行一次分割， 进行一次分割 int q=Partition(a,p,r); 回分割元素的位置 QuickSort(a,p,q-1);//对左半段排序 对左半段排序 QuickSort(a,q+1,r);//对右半段排序 对右半段排序 } }7
a的起始位 的起始位 置
算法课件 改自MIT
2.5快速排序问题 快速排序问题 快速排序问题
划分过程Partition的过程中，首先要选择一个元素，根 的过程中，首先要选择一个元素， 的过程中 据其值划分数组。称该元素为中轴。 据其值划分数组。称该元素为中轴。 选择中轴有许多不同的策略， 选择中轴有许多不同的策略，我们使用最简单 的策略，选择第一个元素： 的策略，选择第一个元素：s = a[p]。 。
算法课件 改自MIT
2.5快速排序问题 快速排序问题 快速排序问题
划分举例(1) 65 65 (2) 70 45 (3) 75 75 (4) 80 80 (5) 85 85 (6) 60 60 (7) 55 55 (8) 50 50 (9) 45 70 (10) +∞ +∞ i 2 3 p 9 8
65
45
50
80
85
60
55
75
70
+∞
4
7
65
45
50
55
85
60
80
75
70
+∞
5
6
65
45
50
55
60
85
80
75
70
+∞
6
5
60
45
50
55
65
85
80
75
70
+∞
Figure 2-1
算法课件 改自MIT
2.5快速排序问题 快速排序问题 快速排序问题
划分的过程使用一种两次扫描子数组的方法:一次是从左到右,另 使用一种两次扫描子数组的方法 一次是从左到右 另 一次是从左到右 一次是从右到左 从右到左,每次都把子数组的元素和中轴进行 一次是从右到左 每次都把子数组的元素和中轴进行 比较。 比较。 从左到右的扫描从第二个元素开始,希望小于中轴的 从左到右的扫描从第二个元素开始 希望小于中轴的 从第二个元素开始 元素位于子数组的第一部分， 元素位于子数组的第一部分，扫描会忽略小于中轴的 元素，直到遇到第一个大于等于中轴的元素才会停止。 元素，直到遇到第一个大于等于中轴的元素才会停止。 从右到左的扫描从最后一个元素开始， 从右到左的扫描从最后一个元素开始，因为我 …… 此处隐藏：2908字，全部文档内容请下载后查看。喜欢就下载吧 ……
第2章 分治策略3快速排序.doc
将本文的Word文档下载到电脑
