8. 数据结构—排序

目录

一、插入排序

1） 直接插入排序

优化： 折半插入排序

2）希尔排序

二、 交换排序

1）冒泡排序

2）快速排序——递归实现

三、选择排序

1）简单选择排序

 2）堆排序

四、归并排序

五. 各个排序性能分析

一、插入排序

1） 直接插入排序

更适用于基本有序的排序表和数据量不大的排序表。

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
//直接插入排序
//思路：分为两部分(已排序和未排序) 
//每一趟将一个未排序的数插入到已排序的合适位置(要走n-1趟) 
//A[0]不存放数据，作为哨兵 
void InsertSort(ElemType A[],int n){int i,j;for(i=2;i<=n;i++){ //排序n-1趟，i表示待排序数的位置 if(A[i]<A[i-1]){A[0]=A[i];  //哨兵//因为稳定性，遇到相同数时循环就该停下来，也就是插入到相同的后面 for(j=i-1;A[j]>A[0];j--){   //从后往前查找插入位置 A[j+1]=A[j];  //向后移位		}A[j+1]=A[0]; }}
}
int main(void){int A[7]={0,1,455,-234,45,566,21}; //参与比较的只有A[1]-A[6] InsertSort(A,6);for(int i=1;i<7;i++)cout<<A[i]<<" ";return 0;
}
  •  时间复杂度：O(n^2)   

最好情况下：序列已经有序，每次向有序子表中插入元素时，只需要比较1次，总共比较n-1次，时间复杂度O(n)

最坏情况下:  序列整体逆序，总的比较次数和移动次数均达到最大， 时间复杂度为O(n^2)。

平均情况下：O(n^2)

tips:无特别说明下，时间复杂度指的是最坏时间复杂度

  • 空间复杂度：O(1) 

仅仅只是使用了常数个辅助空间(哨兵)，故空间复杂度为O(1） 

  • 稳定性：稳定 

从代码中我们可以看到，每次插入的时候从后往前比较，遇到相同的数时，总插在相同数的后面，即相同数的相对位置不会发生改变。

优化： 折半插入排序

与直接插入排序相比，在找插入排序位置的时候，使用折半插入减少了比较次数 O(nlogn)，但移动次数并未发生改变 O(n^2)，故时间复杂度还是O(n^2)。

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
//折半插入排序
//思路：分为两部分(已排序和未排序) 
//每一趟将一个未排序的数插入到已排序的合适位置(要走n-1趟) 
//A[0]不存放数据，作为哨兵 
void InsertSort(ElemType A[],int n){for(int i=2;i<=n;i++){A[0]=A[i];  //哨兵存放待排数 //1.找到插入位置int low=1,high=i-1; while(low<=high){int mid=(low+high)/2;if(A[0]<A[mid])    //左半子表 high=mid-1; else           //右半子表(为保持稳定性=时候需要到右半子表) low=mid+1; }//当low>high时候退出循环，low所指位置就是要插入的地方 //2.[low,i]位置均向后移动一位for(int j=i-1;j>=low;j--)A[j+1]=A[j];A[low]=A[0];   //插入 }}
int main(void){int A[7]={0,1,455,-234,45,566,21}; //参与比较的只有A[1]-A[6] InsertSort(A,6);for(int i=1;i<7;i++)cout<<A[i]<<" ";return 0;
}

2）希尔排序

基本思想：把相隔某个“增量”的记录组成一个子表，对各个子表进行直接插入排序，当整个表中的元素呈现“基本有序”时，再对全体记录进行一次直接插入排序。

  • 时间复杂度：依赖于增量序列的函数 (并不确定）

最坏情况下:  时间复杂度为O(n^2)。

  • 空间复杂度：O(1) 

仅仅只是使用了常数个辅助空间，故空间复杂度为O(1） 

  • 稳定性：不稳定 

二、 交换排序

1）冒泡排序

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;//冒泡排序
//最多排序n-1趟，每趟将确定一个最小的放在队头 
//第i趟比较n-i次(从后往前找最小)
//添加了一个flag标记位用来记录每趟是否存在交换，若不存在则说明排序结束 
void BubbleSort(ElemType A[],int n){for(int i=0;i<n-1;i++){  //n-1趟排序 bool flag=false;  //标记此趟是否存在交换for(int j=n-1;j>i;j--){  //每趟从后往前 if(A[j-1]>A[j]){ElemType t=A[j-1];A[j-1]=A[j];A[j]=t;flag=true;} }if(!flag)   //如果没有发生交换，说明已经有序了 return;} 
}int main(void){int a[5]={34,-13,24,324,21};BubbleSort(a,5); for(int i=0;i<5;i++)cout<<a[i]<<" ";return 0;
}
  •  时间复杂度：O(n^2)   

最好情况下：序列整体有序，第一趟比较n-1次之后即可完成排序，复杂度O(n)

最坏情况下:  序列整体逆序，需要比较n-1趟，第i趟排序比较n-i次关键字，复杂度O(n^2）

tips:无特别说明下，时间复杂度指的是最坏时间复杂度

  • 空间复杂度：O(1) 

仅仅只是使用了常数个辅助空间(两数交换的时候)，故空间复杂度为O(1） 

  • 稳定性：稳定 

从代码中，我们可以看到，当两数相等时，我们并不交换其位置，所以冒泡算法稳定。 

2）快速排序——递归实现

快速排序是所有内部排序算法中平均性能最优的排序算法。

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;//选择排序(递归实现)
//每一次确定一个位置的主要代码 
int partition(ElemType A[],int low,int high){ElemType pivot=A[low];  //将表中第一个需要排序的元素做为基准元素while(low<high){  //当low==high,该次结束 while(low<high&&A[high]>=pivot)high--;A[low]=A[high];while(low<high&&A[low]<=pivot)low++;A[high]=A[low]; }A[low]=pivot;  //最终确认的位置return low; //返回该位置 
}//快排主代码 
void QuickSort(ElemType A[],int low,int high){if(low<high){  //排序并未结束 int mid=partition(A,low,high);   //整个序列排序QuickSort(A,low,mid-1);QuickSort(A,mid+1,high); }
} 
int main(void){int A[6]={23,-24,345,27,34,13};QuickSort(A,0,5);for(int i=0;i<6;i++){cout<<A[i]<<" ";}return 0;
}
  • 时间复杂度：O(n*递归层数)   

最好情况下：选取基准够好，刚好将其划分成了一个类似完全二叉树，时间复杂度O(nlogn) 

最坏情况下:  选取基准最差，直接划分成了一个单支树，时间复杂度O(n^2)

  • 空间复杂度：O(递归层数) 

由于快速排序是递归的，所以需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大层数一致。

最坏情况下：O(n）

最好情况下：O(logn)

平均情况下：O(logn) 

  • 稳定性：不稳定 

例如表{3，2 ，2}，以1为基准的时候，经过一趟排序之后，就变成了{2，2，3}，相对位置发生了改变。

三、选择排序

每一趟在待排序元素中选择关键字最小(或最大)的元素加入有序子序列。

1）简单选择排序

适用于顺序存储和链式存储的线性表，以及关键字较少的情况。

#include<bits/stdc++.h>
using namespace std;typedef int ElemType;//简单选择排序
//每次找到待排序中最小的，然后进行交换 
void SelectSort(ElemType A[],int n){for(int i=0;i<n-1;i++){  //进行n-1趟即可int min=i;  //最小值的下标 for(int j=i+1;j<n;j++)if(A[j]<A[min])min=j;//将min和i位置对应的值进行交换swap(A[min],A[i]);//swap也就是下面3句代码，需要移动3次 
//		ElemType t=A[min];
//		A[min]=A[i];
//		A[i]=t; } 
}int main(void){int A[6]={1,455,-234,45,566,21}; //参与比较的是[0]-A[5] SelectSort(A,6);for(int i=0;i<6;i++)cout<<A[i]<<" ";return 0;
}
  • 时间复杂度：O(n^2)   

元素的移动次数：很少，不会超过 3*(n-1), 最好的情况0次

元素的比较次数： 与序列的初始状态无关，始终是 n(n-1)/2。

故时间复杂度为O(n^2)  

  • 空间复杂度：O(1) 

仅使用常数个辅助单元。

  • 稳定性：不稳定 

例如表{5，6，5 ，2}，经过经过一趟简单选择排序之后，就变成了{2，6，5 ，5}，相对位置发生了改变。

 2）堆排序

  • 时间复杂度：O(nlogn)   

堆排序分为两步：

1. 建立初始堆: 时间复杂度为O(n)

2. 排序(选择堆顶和最后一个待排元素交换，然后再调整剩余堆):

    需要进行n-1趟(每次选择最大元素放在堆底)，每趟最多向下调整h-1层，每层最多比较2次，故时间复杂度O(nh),也就是O(nlogn)

总时间复杂度 O(nlogn+n) 也就是O(nlogn)

  • 空间复杂度：O(1) 

仅使用常数个辅助单元。

  • 稳定性：不稳定 

例如堆{1，2 ，2}，经过堆排序之后，就变成了{1，2 ，2}，相对位置发生了改变。

四、归并排序

例子：

考点：对于两个长度分别为n和m的链表进行二路归并操作，最少的比较次数min(m,n),最多的比较次数m+n-1。

  •  时间复杂度：O(nlogn)   

二路归并的“归并树”可以看做是一个倒立的二叉树，

1. 需要归并h-1趟，时间复杂度O(logn) 。

因为二叉树第h层最多有2^(h-1)个元素 =》 n<=2^(h-1)   =》 h-1=logn向上取整

2. 每趟归并遍历元素，时间复杂度O(n)

所以总的时间复杂度为O(nlogn），最好、最坏和平均情况下均为O(nlogn)。

  • 空间复杂度：O(n) 

1. 在归并过程中，借助了n个辅助空间来归并，时间复杂度为O(n）

2. 使用递归实现，时间复杂度O(h),也就是O(logn)

总的来看，空间复杂度也就是O(n+logn),取大头，也就是O(n)

  • 稳定性：稳定 

二路归并在Merge() 操作时，不会改变相同关键字记录的相对次序。

五. 各个排序性能分析

算法种类

时间复杂度

空间复杂度

是否稳定

最好情况

平均情况

最坏情况

最好情况

平均情况

最坏情况

插入

排序

直接插入排序

O(n)

O(n^2)

O(n^2)

O(1)

O(1)

O(1)

稳定

折半插入排序

O(n)

O(n^2)

O(n^2)

O(1)

O(1)

O(1)

稳定

希尔排序

O(1)

O(1)

O(1)

不稳定

交换排序

冒泡排序

O(n)

O(n^2)

O(n^2)

O(1)

O(1)

O(1)

稳定

快速排序

O(nlogn)

O(nlogn)

O(n^2)

O(logn)

O(logn)

O(n)

不稳定

选择排序

简单选择排序

O(n^2)

O(n^2)

O(n^2)

O(1)

O(1)

O(1)

不稳定

堆排序

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

O(1)

O(1)

不稳定

归并排序

二路归并排序

O(nlogn)

O(nlogn)

O(nlogn)

O(n)

O(n)

O(n)

稳定

 这些都是自己总结的，有什么问题欢迎指正。

都看到这里了，点个赞再走吧！！！(*^_^*)

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/457791.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

论文笔记（五十一）Challenges for Monocular 6-D Object Pose Estimation in Robotics

论文笔记（五十一）Challenges for Monocular 6-D Object Pose Estimation in Robotics

Challenges for Monocular 6-D Object Pose Estimation in Robotics 文章概括摘要I. 介绍II. 正在进行的研究和常见数据集A. 数据集B. 正在进行的研究问题 III. 未来挑战A. 物体本体B. 可变形和关节物体C. 场景级一致性D. 基准现实性E. 环境影响F. 通用物体操控 IV. 结论 Estim…
阅读更多...
Telephony中ITelephony的AIDL调用关系

Telephony中ITelephony的AIDL调用关系

以Android14.0源码讲解 ITelephony来自framework下的com.android.internal.telephony包下 frameworks/base/telephony/java/com/android/internal/telephony/ITelephony.aidl这个接口用于与Phone交互的界面&#xff0c;主要由TelephonyManager类使用&#xff0c;一些地方仍在…
阅读更多...
多元线性回归【正规方程/sklearn】

多元线性回归【正规方程/sklearn】

多元线性回归【正规方程/sklearn】 1. 基本概念1.1 线性回归1.2 一元简单线性回归1.3 最优解1.4 多元线性回归 2. 正规方程求最优解2.1 线性回归的损失函数&#xff08;最小二乘法&#xff09;2.2 推导正规方程2.3 正规方程练习2.4 使用sklearn计算多元线性方程2.5 凸函数 3. 线…
阅读更多...
InternVL-1.1: Enhance Chinese and OCR Capabilities

InternVL-1.1: Enhance Chinese and OCR Capabilities

Blog：https://internvl.github.io/blog/2024-01-24-InternVL-1.1/ 指南：https://internvl.readthedocs.io/en/latest/internvl1.1/introduction.html InternVL-Chat-V1-1 结构类似于 LLaVA，包括一个 ViT、一个 MLP 投影器和一个 LLM。如上图所示，我们通过一个简单的 MLP …
阅读更多...
JAVA篇之类和对象

JAVA篇之类和对象

目录 一. 面向对象 1.1 面向对象和面向过程 二. 类的定义和使用 2.1 什么是类 2.2 类的定义格式 三. 类的实例化 四. this引用 4.1 this引用的作用 五. 构造方法 5.1 构造方法重载 5.2 通过this调用其他构造方法 5.3 默认初始化 结语 一. 面向对象 Java 是一门面向对…
阅读更多...
面向对象与设计模式第二节：设计模式实战

面向对象与设计模式第二节：设计模式实战

第三章&#xff1a;面向对象与设计模式 第二节&#xff1a;设计模式实战 设计模式是软件工程中的一项重要实践&#xff0c;它为解决常见的设计问题提供了经过验证的解决方案。本课将深入探讨几种常见的设计模式&#xff0c;并通过实际案例分析其在项目中的应用。 1. 每种设计…
阅读更多...
JavaEE初阶---文件IO总结

JavaEE初阶---文件IO总结

文章目录 1.文件初识2.java针对于文件的操作2.1文件系统的操作---file类2.2文件内容的操作---流对象的分类2.4字符流的操作》文本文件2.4.1异常的说明2.4.2第一种文件内容的读取方式2.4.3第二种读取方式2.4.4close的方法的介绍2.4.5close的使用优化操作2.4.6内容的写入 2.3字节…
阅读更多...
无需依赖闭源模型！司南CompassJudger为AI评测带来新选择

无需依赖闭源模型！司南CompassJudger为AI评测带来新选择

前沿科技速递&#x1f680; 近期&#xff0c;司南OpenCompass团队发布了一款开源的全能评价模型——CompassJudger。这是全球首个全能开源的 All-in-one Judge Model&#xff0c;不仅支持主流的双向对比&#xff08;pair-wise&#xff09;和单向评分&#xff08;point-wise&…
阅读更多...
软件工程--需求分析与用例模型

软件工程--需求分析与用例模型

面向对象分析(ObjectOrientedAnalysis&#xff0c;简称OOA) 分析和理解问题域&#xff0c;找出描述问题域所需的类和对象&#xff0c;分析它们的内部构成和外部关系&#xff0c;建立独立于实现的OOA模型&#xff0c;暂时忽略与系统实现有关的问题。 主要使用UML中的以下几种图…
阅读更多...
全球知名度最高的华人起名大师颜廷利：世界顶级思想哲学教育家

全球知名度最高的华人起名大师颜廷利：世界顶级思想哲学教育家

全国给孩子起名最好的大师颜廷利教授在其最新的哲学探索中&#xff0c;提出了《升命学说》这一前沿理论观点&#xff0c;该理论不仅深刻地回应了古今中外众多哲学流派和思想体系的精髓&#xff0c;还巧妙地融合了实用主义、理想主义以及经验主义的核心理念。通过这一独特的视角…
阅读更多...
我准备写一份Stable Diffusion入门指南-part1

我准备写一份Stable Diffusion入门指南-part1

我准备写个SD自学指南&#xff0c;当然也是第一次写&#xff0c;可能有点凌乱&#xff0c;后续我会持续更新不断优化&#xff0c;我是生产队的驴&#xff0c;欢迎监督。 Stable Diffusion WebUI 入门指南 Stable Diffusion WebUI 是一款基于 Stable Diffusion 模型的用户界面…
阅读更多...
力扣 中等 740.删除并获得点数

力扣 中等 740.删除并获得点数

文章目录 题目介绍题解 题目介绍 题解 由题意可知&#xff0c;在选择了数组中元素 a 后&#xff0c;该元素以及所有等于 a−1 和 a1 的元素都会从数组中删去&#xff0c;并获得 a 的点数。若还有多个值为 a的元素&#xff0c;由于所有等于 a−1 或 a1 的元素已经被删除&#x…
阅读更多...
三种材料的金相图及金相图解析材料

三种材料的金相图及金相图解析材料

3. 二&#xff0e;不同温度下三种材料&#xff08;铸铁&#xff0c;铝&#xff0c;低碳钢&#xff09;的低温脆性&#xff0c;相关材料&#xff0c;文献引用 三&#xff0e;三种材料在汽车制造中可能的应用 &#xff08;如捷豹用铝合金降低车身重量&#xff09;.三种材料哪个材…
阅读更多...
Linux: Shell编程入门

Linux: Shell编程入门

Shell 编程入门 1 ) Shell 概念 shell 是 在英语中 壳, 外壳的意思可以把它想象成嵌入在linux这样的操作系统里面的一个微型的编程语言不像C语言, C 或 Java 等编程语言那么完整&#xff0c;它可以帮我们完成很多自动化任务例如保存数据监测系统的负载等等&#xff0c;我们同样…
阅读更多...
AI博士人手10篇顶会，遭质疑。。。

AI博士人手10篇顶会，遭质疑。。。

B站&#xff1a;啥都会一点的研究生公众号&#xff1a;啥都会一点的研究生 AI科技圈又发生了啥新鲜事&#xff1f; “稚晖君”灵犀X1全球开源&#xff0c;推动人形机器人技术共享 智元机器人宣布其人形机器人灵犀X1正式面向全球开源&#xff0c;提供了超过1.2GB的软硬件全套…
阅读更多...
【LeetCode】11.盛最多水的容器

【LeetCode】11.盛最多水的容器

思路&#xff1a; 利用双指针法进行移动&#xff0c;一个在头一个在尾&#xff0c;此时宽度最宽&#xff0c;当宽度缩小时&#xff0c;高度发生变化&#xff0c;从而可以找到最大值。 代码&#xff1a; int maxArea(int* height, int heightSize) {int* left height;int* …
阅读更多...
android——渐变色

android——渐变色

1、xml的方式实现渐变色 效果图&#xff1a; xml的代码&#xff1a; <?xml version"1.0" encoding"utf-8"?> <shape xmlns:android"http://schemas.android.com/apk/res/android"xmlns:tools"http://schemas.android.com/tools…
阅读更多...
Java常见数据结构

Java常见数据结构

数组 数组的特性存储空间是连续的长度是不可变的只能存储 相同的类型(不严谨)可以通过下标访问数组的内容 a[10] 复杂度是O1每个元素的默认是为零值 0 null false -> 一个对象的基本的数据域的初始化也是这样的 Student 类中的username属性 默认值 链表 查找麻烦 插入和删…
阅读更多...
logback日志导入使用

logback日志导入使用

1导入配置 <!-- 日志 &#xff0c; 会自动传递slf4j门面--> <dependency><groupId>ch.qos.logback</groupId><artifactId>logback-classic</artifactId><version>1.2.3</version> </dependency>2 引入配置 Logback要求…
阅读更多...
开源实时数仓的构建

开源实时数仓的构建

设计计思路 基本思路 开源数据平台的设计思路是通过 Flink SQL Batch、StartRocks SQL 、StartRocks物化视图 的能力实现一个离线任务的开发&#xff1b;使用 DolphinScheduler 进行离线工作流编排和调度&#xff1b;通过 Flink CDC 和 Flink SQL 实现流处理能力&#xff0c;进…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023