数据结构与算法 12. 排序 2021-07-29 浏览量 617 暂无评论 [TOC] ## 12.1 快速排序:算法A 分而治之 将序列分为两个子序列:$S = S_L + S_R,max(S_L) \le min(S_R)$ 在子序列递归地排序之后,原序列自然有序:$sorted(S) = sorted(S_L) + sorted(S_R)$ 与归并的区别在于: - 归并的计算量和难点在于**合** - 快排在于**分** ### 轴点 在序列中的特殊元素:左/右侧元素,均不比它大/小 若能知道轴点,则 ```cpp template void Vector::quickSort(Rank lo, Rank hi) { if (hi - lo < 2) return; Rank mi = partition(lo, hi - 1); quickSort(lo, mi); quickSort(mi + 1, hi); } ``` 然而轴点未必存在 快排就是将所有元素逐个转换为轴点的过程 ### 构造轴点 ```cpp template Rank Vector::partition(Rank lo, Rank hi) { // 随机选取候选轴点 swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]); pro = _elem[lo]; while (lo < hi) { // 仍要加上lo < hi,避免空闲位置产生影响,比如4[4]9,此时4<=5,lo仍会加1,指向9 // 但是可以把 <= 改为<吧,不行,这不是等不等于的事 // 更一般地讲,如果最后lo=hi指向的元素仍小于pro,则lo会再加1 while (lo < hi && pro <= _elem[hi]) hi--; _elem[lo] = _elem[hi]; while (lo < hi && elem[lo] <= pro) lo++; _elem[hi] = _elem[lo]; } // 这一步之前,lo=hi的位置元素是小于等于pro的,那就和pro交换 _elem[hi] = pro; return hi; } ``` **缺点**: - 不稳定 - 划分不均衡 划分均衡的情况下,接近归并排序,$O(nlogn)$ 划分极不均衡的情况下,与冒泡相当,$O(n^2)$ 平均性能:$O(nlogn)$ 就算使用随机选取的方法,也只是降低最坏情况的概率,不能杜绝 ### 变种 #### 不变性 $$ S = [lo] + L(lo, mi] + G(mi, k) + U[k, hi] \\ L \lt pivot \leq G $$ #### 单调性 ![在这里插入图片描述](https://img-blog.csdnimg.cn/0c6d40cadbae4dc899be53c0bdab8bee.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) #### 实现 ```cpp template Rank Vector::partition(lo, hi) { swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]; pivot = _elem[lo]; Rank mi = lo; for (Rank k = lo + 1; k <= hi; k++) if (_elem[k] < pivot) swap(_elem[++m], _elem[k]); swap(_elem[lo], _elem[mi]); return mi; } ``` #### 实例 ![在这里插入图片描述](https://img-blog.csdnimg.cn/8e239a30cc54472885e561ff7d4b67e6.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) #### 综合评价 - 就地算法 - 线性复杂度 - 稳定性不能保证 ## 12.2 选取:众数 - 第k个大的元素 - 中位数 - 众数 如何绕开排序,直接选取? **众数**:无序向量中,若有**一半以上**元素为m,则称之为众数。 **必要性**:众数若存在,则亦必为中位数。 **减而治之:** 每次迭代移出某元素占一半的前缀P,则若众数存在,必在剩下的向量中 ```cpp template T majEleCandidate(Vector A) { T maj; // c为前缀中首元素数量与其他元素数量的差值,差值为0表明可以剪去 for (int c = 0, i = 0; i < A.size(); i++) if (c == 0) { maj = A[i]; c = 1; } else maj == A[i] ? c++ : c--; return maj; // } ``` ### 通用算法 #### 堆A 建堆:线性O(n) delMin() * k:O(klogn) #### 堆B 随机选取k个元素组织为大顶堆,插入、删除 #### 堆C 两个堆 #### quickSelect 减而治之,经过partition找到一个轴点后,若该轴点大于k,则剪去轴点之后的元素,若小于k,则剪去之前的元素。 ```cpp template void quickSelect(Vector & A, Rank k) { for (Rank lo = 0, hi = A.size() - 1; lo < hi;) { Rank i = lo, j = hi; T pivot = A[lo]; while (i < j) { while (i < j && pivot <= A[j]) j--; A[i] = A[j]; while (i < j && A[i] <= pivot) i++; A[j] = A[i]; } A[i] = pivot; if (k <= i) hi = i - 1; if (i <= k) lo = i + 1; } } ``` #### linearSelect 最坏的情况下,也只需要线性时间 把整个向量分成Q份,求每份的中位数,再求这些中位数的中位数,直到平凡情况,使用普通方法,按小于、等于、大于中位数分别放进L、E、G。 新问题的规模都不会超过此前规模的75% ![在这里插入图片描述](https://img-blog.csdnimg.cn/f338014cf46b44218b0f8ccf72914a16.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ##### 复杂度 为保证线性,$1/Q + 3/4 < 1$ 可取Q=5 ## 12.3 希尔排序 将整个序列视作一个矩阵,逐列各自排序`w-sorting` 怎么视作一个矩阵呢?列怎么分呢? **递减增量** - 由粗到细:重排矩阵,使其更窄,再次逐列排序`w-ordered` - 逐步求精:如此往复,直至矩阵变成一列`1-sorting` **步长序列**:由各矩阵宽度构成的**逆序列** 不同的步长序列会得到不同的算法 ### 几个问题: 1. 既然最终还是要做一次`1-sorting`,那此前的排序有何意义呢? 2. 如何实现矩阵重排?不用使用二维向量,一维足矣,第i列,$a[i + kw], 0 \le k \lt n/w$ 3. 各列内部如何排序?**输入敏感**,插入排序,取决于输入序列中逆序对的数量 ### 初始希尔序列 ${1, 2, 4, ...}$ 都为偶数,那么每次重组后的每列中都来自同一子串,互不相关 ![在这里插入图片描述](https://img-blog.csdnimg.cn/a80128aebfc44348b01a9f8c8c7b3ff1.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **相邻项要互素才好** 数论?呜呜呜 ![在这里插入图片描述](https://img-blog.csdnimg.cn/9135f0868141469fa1cf727e6e78977a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) `h-ordered`:$S[i] \le S[i + h], \space for \space 0 \le i \lt n - h$ 那么1-ordered就是全局有序的。 `h-sorting`:一个`h-ordered`的序列可以由以下步骤得到: 1. 将序列排成h列(逻辑上的,并不创建新的矩阵) 2. 对每列分别排序 **性质**: 1. 此前`g-ordered`序列在经过下一次`h-sorting`后,`g-ordered`仍然保持 2. 如果一个序列既是`g-ordered`,又是`h-ordered`,那么它一定是`(g + h)-ordered`,并且对任意的m, n, 也一定是`(mg + nh)-ordered` 逆序对可能出现的地方为秩小于等于`(g - 1)·(h - 1)`的区间 赞赏 微信支付 支付宝支付