长期做网站应该购买稳定的空间,网站开发7个基本流程,wordpress仪表盘地址,周口市住房和城市建设局网站快速排序 C
本文图示借鉴自清华大学邓俊辉老师数据结构课程。
快速排序的思想
快速排序是分治思想的典型应用。该排序算法可以原地实现#xff0c;即空间复杂度为 O(1)O(1)O(1)#xff0c;而时间复杂度为 O(nlogn)O(nlogn)O(nlogn) 。
算法将待排序的序列 SSS 分为两个子…快速排序 C
本文图示借鉴自清华大学邓俊辉老师数据结构课程。
快速排序的思想
快速排序是分治思想的典型应用。该排序算法可以原地实现即空间复杂度为 O(1)O(1)O(1)而时间复杂度为 O(nlogn)O(nlogn)O(nlogn) 。
算法将待排序的序列 SSS 分为两个子序列 SLS_LSL 和 SRS_RSR 随着这种子序列的划分可以保证问题的规模在不断缩小即有 max(∣SL∣,∣SR∣)nmax(|S_L|,|S_R|) n max(∣SL∣,∣SR∣)n 并要求左侧子序列 SLS_LSL 中的最大值不大于右侧子序列 SRS_RSR 中的最小值即有 max(SL)≤min(SR)max(S_L)\le min(S_R) max(SL)≤min(SR) 这样在递归地再对子序列进行划分之后原序列自然有序。递归的终止条件为划分子序列的平凡情况即子序列的规模为1。 我们将划分两个子序列的点称为 pivot轴点 在轴点左侧的元素均不比它更大在轴点右侧的元素均不比它更小。轴点的位置即为该元素在最终排序完成的序列中的位置。
即将原序列按如下划分 [l,r][l,pivot)pivot(pivot,r][\ l, r\ ][\ l, pivot\ )pivot(\ pivot,r\ ] [ l,r ][ l,pivot )pivot( pivot,r ] 但是对于待排序的序列我们并不知道谁是轴点甚至有可能原序列中所有元素都不是轴点比如将一个已排序的序列循环右移一位则此时所有元素都不在自己的排序位置上都不是轴点。
好在我们可以通过对待排序的序列的元素进行移动交换从而使得某个元素成为轴点在递归之后所有元素都成为轴点这时所有元素都位于自己的排序位置上整个排序算法完成。
可以看到整个算法的框架是递归地选取轴点并划分子序列究竟怎样划分怎样划分效率更高是快排算法的关键之处。
算法框架
我们先给出整个快排算法的递归框架其中关键的 partition 划分函数我们会在后面详细介绍整体框架是一个递归函数
void quickSort(vectorint vec, int l, int r) {if (lr) {int pivot partition(vec, l, r);quickSort(vec, l, pivot-1);quickSort(vec, pivot1, r);}
}当 l 不小于 r 时即 l 已经等于 r此时即为递归退出的平凡情况子序列只有一个元素。在此之前我们都需要不断地执行 if 语句中的内容得到传入序列的一个轴点并分别递归地处理该轴点两侧的子序列。
最终当传入的子序列规模为1是即 lr 的判断条件不成立达到返回条件整个递归过程开始返回。
partition
版本1
接下来我们来介绍最为关键的 partition 函数。 我们先任选一个元素作为轴点的 “培养对象” 并备份在我们划分完毕之后该元素可以 “名正言顺” 地位于自己应该处于的最终排序位置不妨就取序列的最左端元素。
然后将两个指针分别放在整个序列的左右两端分别向中间靠拢。
我们将
未确定区域称为 UUU 图中粉色部分初始为全集确定大于轴点的部分称为 GGG 图中蓝色部分初始为空集确定小于轴点的部分称为 LLL 图中绿色部分初始为空集
交替地将左右两端的指针向中间移动分别检查移动时当前元素与轴点 pivot 的大小关系若小于轴点则归入 LLL若大于轴点则归入 RRR 。
当左右两指针相等时该位置即为我们的 “培养对象” 轴点应该处于的排序位置将备份的轴点放入该位置即可。最后同样返回轴点位置。
整个过程中左右指针所指的位置交替空闲。所谓空闲即是指其中元素可以被覆盖。一开始时我们将 ”培养对象“ 备份故其位置是 “空闲” 的在随后的交还过程中左右指针总有一个所指的位置是空闲的。 可以参考上图图中紫色部分即为 “空闲” 的。红色的 lo、hi 分别对应我们描述中的左右指针。
代码实现如下
int partition(vectorint vec, int l, int r) {int pivot vec[l];while(l r) {while (lr pivotvec[r]) r--;swap(vec[r], vec[l]);while (lr pivotvec[l]) l;swap(vec[r], vec[l]);}vec[l] pivot;return l;
}版本2
对于 partition 函数还有一种实现的方式可以称为 LGU 的方式在这种方式中L 仍旧排在原序列的最左端而中间是 G 最右端是 U。 同样可以选取最左端的元素作为 pivot 。
然后一根指针从序列的最左端遍历到最右端分别判断每个当前元素与 pivot 的关系并分别划分到 L 或 G 中。
如果是划分到 G 中直接将 k 即可而如果是划分到 L 中则需要将 G 滚动后移一个元素并将当前元素交换到 L 的末尾。
代码实现如下
int partition(vectorint vec, int l, int r) {int m l, pivot vec[l];for (int kl1; kr; k) {if (pivot vec[k])swap(vec[m], vec[k]);}swap(vec[l], vec[m]);return m;
}这里中间判断中的 if 分支是判断当前元素小于轴点 pivot 需要将当前元素加入到 L 中将当前元素 vec[k] 与 L 的最后一个元素 vec[m] 互换然后k而它对应的 else 分支即当前元素小于轴点 pivot需要将当前元素加入到 G 中此时只需将 k。两个分支都需要 k直接放在循环变量的更新中。
最后同样返回轴点位置。
