【数据结构(邓俊辉)学习笔记】向量05——排序器

2024-05-01 08:28

本文主要是介绍【数据结构(邓俊辉)学习笔记】向量05——排序器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 0. 概述
  • 1.统一入口
  • 2. 起泡排序
    • 2.1 起泡排序(基础版)
      • 2.1.1 算法分析
      • 2.1.2 算法实现
      • 2.1.3 重复元素与稳定性
      • 2.1.4 复杂度分析
  • 3. 归并排序
    • 3.1 有序向量的二路归并
    • 3.2 分治策略
    • 3.3 实例
    • 3.4 二路归并接口的实现
    • 3.5 归并时间
    • 3.6 排序时间
  • 4.综合评价

0. 概述

介绍下有序向量的排序器,包括起泡排序和归并排序。

1.统一入口

这类接口也是将无序向量转换为有序向量的基本方法和主要途径
在这里插入图片描述

2. 起泡排序

2.1 起泡排序(基础版)

2.1.1 算法分析

在这里插入图片描述

2.1.2 算法实现

反复调用单趟扫描交换算法,直至逆序现象完全消除。

template <typename T> //向量的起泡排序
void Vector<T>::bubbleSort ( Rank lo, Rank hi ) //assert: 0 <= lo < hi <= size
{ while ( !bubble( lo, hi-- ) ); } //逐趟做扫描交换,直至全序

算法思想:依次比较各对相邻元素,每当发现逆序即令二者彼此交换;一旦经过某趟扫描之后未发现任何逆序的相邻元素,即意味着排序任务已经完成,则通过返回标志“sorted”,以便主算法及时终止。

template <typename T>
void Vector<T>::bubble ( Rank lo, Rank hi) { //0 <= nbool sorted = true; //整体排序标志while ( ++lo < hi ) { //自左向右,逐一检查各队相邻元素if ( _elem[lo - 1] > _elem[lo] ) { //若逆序,则sorted = false; //因整体排序不能保证,需要清除排序标志swap ( _elem[lo - 1], _elem[lo]); //交换}}return sorted;
} //借助布尔型标志位sorted,可及时提前退出,而不致总是蛮力地做n - 1趟扫描交换

2.1.3 重复元素与稳定性

稳定算法的特征是,重复元素之间的相对次序在排序前后保持一致。

该起泡排序过程中元素相对位置有所调整的唯一可能是,某元素_elem[i - 1]严格大于其后继_elem[i]。也就是说,在这种亦步亦趋的交换过程中,重复元素虽可能相互靠拢,但绝对不会相互跨越。由此可知,起泡排序属于稳定算法。

2.1.4 复杂度分析

在这里插入图片描述
如图,前r个元素无序,后n-r元素按顺序排列并严格就位。

bubble()算法由内、外两层循环组成。内循环从前向后,依次比较各对相邻元素,如有必要则将其交换。

扫描交换的趟数不会超过O( r ),算法总体消耗时间不会超过O(n *r)次。

故乱序元素仅限于 A[0, n \sqrt n n )区间,最坏情况下仍需调用 bubblesort1A ()做 Ω \Omega Ω( n \sqrt n n )次调用,共做 Ω \Omega Ω(n)次交换操作和 Ω \Omega Ω(n 3 2 ^{\frac 32} 23)次比较操作,因此累计运行 Ω \Omega Ω(n 3 2 ^{\frac 32} 23)时间。
该算法可进一步优化,详见算法设计优化——起泡排序

3. 归并排序

在这里插入图片描述

3.1 有序向量的二路归并

二路归并属于迭代式算法。每步迭代中,只需比较两个待归并向量的首元素,将小者取出并追加到输出向量的末尾,该元素在原向量中的后继则成为新的首元素。如此往复,直到某一向量为空。最后,将另一非空的向量整体接至输出向量的末尾。

在这里插入图片描述
二路归并算法在任何时刻只需载入两个向量的首元素,故除了归并输出的向量外,仅需要常数规模的辅助空间。

3.2 分治策略

算法思想:通过递归调用将二者分别转换为有序向量,即可借助二路归并算法,得到与原向量S对应的整个有序向量
在这里插入图片描述

template <typename T> //向量归并排序
void Vector<T>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= sizeif ( hi - lo < 2 ) return; //递归基,单元素区间自然有序,否则...int mi = ( lo + hi ) >> 1; //以中点为界 mergeSort ( lo, mi ); //对前半段排序 mergeSort ( mi, hi ); //对后半段排序 merge ( lo, mi, hi ); //归并
}

3.3 实例

在这里插入图片描述

3.4 二路归并接口的实现

算法思想:创建临时数组B存放数组A的[ lo,mi)元素,数组C指向数组A的[mi,hi),调用二路归并算法,将有序向量存放在A中。在这里插入图片描述

template <typename T> //有序向量的归并
void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ) { //各自有序的子向量[lo, mi)和[mi, hi)T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi)int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi)for ( Rank i = 0; i < lb; B[i] = A[i++] ); //复制前子向量int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi)for ( Rank i = 0, j = 0, k = 0; ( j < lb ) || ( k < lc ); ) { //B[j]和C[k]中的小者续至A末尾if ( ( j < lb ) && ( ! ( k < lc ) || ( B[j] <= C[k] ) ) ) A[i++] = B[j++];if ( ( k < lc ) && ( ! ( j < lb ) || ( C[k] < B[j] ) ) ) A[i++] = C[k++];}delete [] B; //释放临时空间B
} //递归后得到完整的有序向量[lo, hi)
  • 若将后一句中的“C[k] < B[j]”改为“C[k] <= B[j]”,对算法将有何影响?

~~~~     经如此调整之后,虽不致影响算法的正确性(仍可排序),但不再能够保证各趟二路归并的稳定性,整个归并排序算法的稳定性也因此不能保证。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~                                                  
~~~~     原算法的控制逻辑可以保证稳定性。实际上,若两个子区间当前接受比较的元素分别为B[j]和C[k],则唯有在前者严格大于后者时,才会将后者转移至A[i++];反之,只要前者不大于后者(包含二者相等的情况),都会优先转移前者。由此可见,无论是子区间内部(相邻)的重复元素,还是子区间之间的重复元素,在归并之后依然能够保持其在原向量中的相对次序。

  • 若将前一句中的“B[j] <= C[k]”改为“B[j] < C[k]”,对算法将有何影响?

当待归并的子向量之间有重复元素时,循环体内的两条处理语句均会失效,两个子向量的首
元素都不会被转移,算法将在此处进入死循环。

3.5 归并时间

在这里插入图片描述
二路归并只需线性时间的结论,并不限于相邻且等长的子向量。实际上,即便子向量在物理空间上并非前后衔接(列表),且长度相差悬殊,该算法也依然可行且仅需线性时间。

3.6 排序时间

在这里插入图片描述
故:
在这里插入图片描述

不足:
路归幵算法 merge(),反复地通过 new 和 delete 操作申请和释放辅助空间。然而实验统计表明,这类操作的实际时间成本,大约是常规运算的 100 倍,故往往成为制约效率提高的瓶颈。
改进点:
可以在算法启动时,统一申请一个足够大的缓冲区作为辅助向量B[],并作为全局变量为所有递归实例公用;归并算法完成之后,再统一释放。
如此可以将动态空间申请的次数降至O(1),而不再与递归实例的总数O(n)相关。当然,这样会在一定程度上降低代码的规范性和简洁性,代码调试的难度也会有所增加。

4.综合评价

  • 起泡排序最坏情况总需要O( n 2 n^2 n2)
  • 归并排序最坏情况下为O(nlogn)

这篇关于【数据结构(邓俊辉)学习笔记】向量05——排序器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/951189

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时