(排序11)排序的时间复杂度,空间复杂度,稳定性总结

news/2024/5/19 18:58:25/

图片总结

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

内排序时间复杂度总结

  1. 内部排序:数据元素全部放在内存中的排序。
  2. . 在内排序当中比较快的有希尔排序,堆排序,快速排序,归并排序,这四个排序的时间复杂度都是O(n*logn)。其中希尔排序的时间复杂度更加准确的来说是O(n的1.3次方),对于希尔排序来说,它的时间复杂度计算非常之困难,所以直接记结论;对于堆排序来说,他的时间复杂度计算是通过错位相减法而算出来的;对于归并排序来说,它的时间复杂度倒是比快速排序稳定多了,还真就是雷打不动的O(logN)
  3. 然后直接插入排序,选择排序,冒泡排序时间复杂度都是O(N^2)
  4. 在四个比较快的排序当中,快速排序总体来说是最优的,虽然快速排序的时间复杂度受到单趟排序之后key最终落在的位置是否偏向于中间,乃至于快速排序在极端情况之下可以慢到O(N^2),但是好在有抢救方法,比如说三数取中。在最终测试完之后快速排序还是占优。
  5. 在这三个比较慢的排序当中,之前也有提到过,对于直接插入排序而言,不存在最好与最坏情况,都是雷打不动的O(N^ 2)。
  6. 对于冒泡排序而言,它最好的情况是O(N),对于直接插入排序而言,它最好的情况也是O(N)。那么这两个又怎么区分伯仲呢?总体而言是直接插入排序比冒泡排序更好,首先,如果这个待排序的数组是顺序有序的话,那么此时两者匹敌一样;如果说是接近有序的话,对于直接插入排序而言,也只需要在个别插入的过程后进行稍微微调一下;但对于冒泡排序的话,假设在某趟过后,整个数组已经是有序的情况之下,他又需要再去遍历一趟去确定已是有序,因此比直接插入排序要慢一点;两者最大的差距体现在部分有序的情况之下,与直接插入排序而言,当一个新元素需要融入到已经有序的数组当中的时候,在某些情况之下可以直接尾部插入而不用融入过程,可以省掉大量的步骤,对于冒泡排序而言,他对于部分有序并不敏感,因为他每一趟跑一次,只确定下来一个数放到最末尾,尽管你是部分有序,基本上还是接近了O(N^2)

外排序(文件排序)

  1. 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
  2. 对于外部排序而言,唯一的解药就是归并思想,用归并排序,与此同时,不要用递归版本,不然的话你懂的,把子文件数据在无限细分下去不是要分死了吗?因此需要用非递归的归并排序。具体的细节看我之前写的博客文件排序。
  3. 再回顾一下大概的过程:你说我现在在磁盘里面有1000个的数据,假设我内存里面最多能放得下100个数据。那我首先先从磁盘里面读100个数据到内存里面,然后在内存里面用快速排序,先把这100个数据给他排好,把这个读出来的,并且排好了的100个数据再放回新文件当中,然后再从磁盘里面剩下的900个数据当中再去读100个到内存里面来,然后再在内存里面用快速排序给他排好,然后再给他放到一个文件当中,然后现在已经有两个文件里面都是有序的数字,这时候用文件与文件的归并(跟内存已经没有关系了,内存里面是放不下的),然后继续不断向后再去读,再去归并…

排序的空间复杂度总结

  1. 对于直接插入排序,希尔排序,选择排序,冒泡排序,他们都是在原先的数组上进行直接改动,因此他们的空间复杂度都是O(1),不需要额外去创建一个新的辅助空间。
  2. 对于快速排序而言,我们知道由于它是一个递归,递归的话是必须要在原先函数的函数栈帧的低地址的地方再去不断的创建函数栈帧,再去不断的创建函数栈帧。递归有它的一个深度,这也是说为什么当递归层次太深的时候会发生栈溢出。如果是理想化的状态的话,我们知道整个快速排序递归的深度是O(logN),然后不排除极端恶心情况,此时递归的深度能够到O(N),因此他的空间复杂度介于O(logN)-O(N)。注意在每一层快速排序递归而创建的函数栈帧当中,在函数栈帧里面的各种变量啊什么的,他们的空间占用都可以算成O(1),也就是说单单就一个函数栈帧里面,其实也没有啥,主要是他在递归,在不断地向下拓展函数栈帧,这就有空间复杂度的增加了
  3. 对于归并排序而言,他也是在进行递归_MergeSort,它的递归的深度的话是标标准准的logN,但是对于递归而言,在外层非递归函数MergeSort,事先开辟了一个n个空间的额外辅助空间,N肯定是比logN大,因此总的空间复杂度就是O(N)

排序稳定性总结

  1. 在排序当中的稳定性,它并不是指这个性能稳不稳定。
  2. 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
  3. 比如说来打个简单的比方,在一个数组当中有两个5,在原先的乱序数组当中,可能两个5是隔开的,但也有一前一后之分。但是当排完序之后这两个5肯定是挨在一起了的,如果说这两个5的相对位置仍然保持不变,那么就叫这个排序是稳定的,否则就是不稳定。稳定性就是指相同数据的相对位置在排序之后是否会发生改变;如果不能保证相对位置不变,那么就是不稳定,否则就是稳定的。
  4. 直接插入排序是稳定的,因为直接插入排序相当于是一个新的数tmp不断的从右边想要融入到已经有序的这么一个数组当中,然后在融入的过程当中,如果说右边的数tmp小于已经有序数组的end所指向的数,那么这时候需要把end所指向的数向后移动一位,然后如果与end指向的数相等的话就直接融入进来,因此两个相等的数也根本就没有任何机会去进行前后交换
  5. 希尔排序是不稳定的,你去想想在一开始的预排序当中,两个相同的数据可能会被分到不同的组,然后进行预排序,然后一开始这个gap又那么大,很容易某个数据就飘到后面去了,控制不住了
  6. 选择排序也是不稳定的,给你举个反例就可以:
    在这里插入图片描述
  7. 堆排序也超级不稳定,给你画个图,举个反例:
    在这里插入图片描述
  8. 冒泡排序肯定是稳定的,冒泡排序就是一趟一趟一趟的去走,然后对于每一趟是两个相邻的数,两个相邻的数这么比下去,如果说我需要升序排列的话,当两个相邻的数当中,左边的数大于右边的数的话,两个数就要发生交换,然后如果说对于数组当中两个具有相同的值的数的话,根本就没有任何机会去进行前后交换,所以说是稳定的
  9. 快速排序也不稳定,给你画个图举个反例:
    在这里插入图片描述
  10. 归并排序是稳定的,当然要把那个等号加上
while(begin1<=end1 && begin2<=end2)
{                //这边这个等号是关键if (arr[begin1]<=arr[begin2]){tmp[k++]=arr[begin1++];}.........
}

http://www.ppmy.cn/news/47477.html

相关文章

Windows实现在桌面上双击图标,自动进入到指定网址

功能实现步骤 创建一个快捷方式&#xff0c;右键点击桌面上的空白区域&#xff0c;选择“新建”->“快捷方式”。在弹出的“创建快捷方式”对话框中&#xff0c;输入你想要打开的网站的URL&#xff0c;例如 https://www.bing.com/?mktzh-cn&mktzh-CN &#xff0c;然后…

轻松掌握Qt FTP 机制:实现高效文件传输

轻松掌握Qt FTP&#xff1a;实现高效文件传输 一、简介&#xff08;Introduction&#xff09;1.1 文件传输协议&#xff08;FTP&#xff09;Qt及其网络模块&#xff08;Qt and its Network Module&#xff09; QNetwork:二、QNetworkAccessManager上传实例&#xff08;Qt FTP U…

Ubuntu中使用vscode+cmake进行编译调试

首先新建一个文件夹作为工作空间 mkdir test 进入工作空间文件夹&#xff0c;在vscode中打开 cd test code . 创建一个c文件 #include<iostream>using namespace std;int main(){int a 23;int b a3;for(int i 0; i<10; i){cout<<"hello vs code &a…

《程序员面试金典(第6版)》面试题 16.01. 交换数字(位运算符,异或性质)

题目描述 编写一个函数&#xff0c;不用临时变量&#xff0c;直接交换numbers [a, b]中a与b的值。 示例&#xff1a; 输入: numbers [1,2]输出: [2,1] 提示&#xff1a; numbers.length 2-2147483647 < numbers[i] < 2147483647 解题思路与代码 这道题不让使用额外…

linux_管道学习-pipe函数-管道的读写-fpathconf函数

接上一篇&#xff1a;linux_何为IPC-进程间常用的通信方式 今天来分享linux的管道学习&#xff0c;希望我的笔记能对大家有用&#xff0c;开始上菜&#xff1a; 目录 1.管道的概念&#xff1a;2.pipe函数3.管道的读写行为4.管道缓冲区大小5.管道的优劣 1.管道的概念&#xff1…

云通讯服务商有哪些?

随着语聊、视频通话、直播等行业的兴起&#xff0c;云通讯厂商的作用越来越凸显&#xff0c;解决画面卡顿、解决声音延迟以及基于互动领域更多的行业解决方案已经成为开发者和企业所需。 从长远来看&#xff0c;随着5G的不断普及&#xff0c;低延迟、高质量的网络环境不断催生线…

kafka--python

文章目录 1、kafka是什么2、docker上部署kafka3、在kafka容器内部署python&#xff0c;并跑通生产者-消费者简单代码4、最新接口4.1、kafka_config.py4.2、kafka_interface.py4.3、run.py4、测试 1、kafka是什么 Producer&#xff1a;即生产者&#xff0c;消息的产生者&#xf…

编译和引用so库

编译和引用so库 1.两种编译方式 ndk-build Android.mk Application.mkCMake CMakeList 2.Android.mk Application.mk (1)javac java文件的绝对路径 → 生成so库 (2)javah com.xxx.xxx.tesAdd → 生成头文件 (3) 修改头文件的后缀&#xff0c;并添加实现 (4)Applicat…

git教程

Git是目前最流行的分布式版本控制系统之一&#xff0c;它可以帮助开发者更好地管理代码和协作开发。以下是Git教程的一些内容&#xff1a; Git入门&#xff1a;介绍Git的基本概念、Git工作流程和Git常用命令。 Git分支&#xff1a;讲解Git分支的用法&#xff0c;包括新建分支、…

Flutter与Android开发:构建跨平台移动应用的新选择

Flutter与Android开发&#xff1a;构建跨平台移动应用的新选择 本文内容提纲如下&#xff1a; 介绍Flutter技术&#xff1a;Flutter是一种由Google推出的开源UI工具包&#xff0c;用于构建高性能、跨平台的移动应用。文章将介绍Flutter的基本概念、特点和优势&#xff0c;包括其…

Python面向对象详解(非常详细)

非常详细的讲解&#xff08;爆肝1w字&#xff09;&#x1f44f;&#x1f3fb;&#x1f44f;&#x1f3fb;&#x1f44f;&#x1f3fb; 零基础一样学得会&#x1f44c;&#x1f3fb; 干货满满不看后悔&#x1f44d;&#x1f44d;&#x1f44d; &#x1f4dd;个人主页→数据…

可能你已经刷了很多01背包的题,但是真的对01背包领悟透彻了吗?,看我这一篇,使君对01背包的理解更进一步【代码+图解+文字描述】

一.概念理解&#xff1a;什么是01背包 关于01背包的概念理解如下&#xff1a;01背包是在M件物品取出若干件放在空间为W的背包里&#xff0c;每件物品的体积为W1&#xff0c;W2至Wn&#xff0c;与之相对应的价值为P1,P2至Pn。001背包的约束条件是给定几种物品&#xff0c;每种物…

数组篇刷题总结

二分查找&#xff1a; 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target …

win11下载配置Python环境+pycharm下载

前两天快乐的把我重装的win10升级成win11&#xff0c;升级的时候超怕不能成功&#xff0c;但效果还不错&#xff0c;然后突然想学一学Python&#xff0c;所以首先来配置环境吧 一、下载安装包 建议去官网&#xff0c;因为自从有了Python3之后&#xff0c;Python2就慢慢的被淘汰…

Difference between HTTP3 and HTTP2

HTTP3目前还在不断更新中。一般每个新版本的优化&#xff0c;都会主要针对上一个版本的缺点。 对HTTP2&#xff0c;有二进制编码、头部压缩、多路复用、服务器推送等新特性去弥补了HTTP1.1中的不足。不过HTTP2基于TCP实现的&#xff0c;带3个缺陷&#xff1a;① TCP层面的队头阻…

常见的注册中心Nacos、Eureka

常见的注册中心 1.Eureka&#xff08;原生&#xff0c;2.0遇到瓶颈&#xff0c;停止维护&#xff09; 2.Zookeeper&#xff08;支持&#xff0c;专业的独立产品。例如&#xff1a;dubbo&#xff09; 3.Consul&#xff08;原生&#xff0c;GO语言开发&#xff09; 4.Nacos …

Vue CLI 浏览器兼容性

Vue CLI 浏览器兼容性 browserslist 你会发现有 package.json 文件里的 browserslist 字段 (或一个单独的 .browserslistrc 文件)&#xff0c;指定了项目的目标浏览器的范围。这个值会被 babel/preset-env 和 Autoprefixer 用来确定需要转译的 JavaScript 特性和需要添加的 CS…

康耐视Designer,通过VC5与西门子S7-1200 PLCProfinet通讯详细

测试使用软件版本 Designer Version: 2.7 GSD: GSDML-V2.3-Cognex-VC5-20140828STEP 7 Professional V14Network Configurator Version: 3.56测试使用硬件 Cognex Vision Controller VC5CIC-5000Siemens PLC: S7-1200 CPU 1214C DC/DC/RLY1.PLC端设置 1.新建一个项目,添加对应…

WxGL应用实例:绘制高精度的3D太阳系模型

文章目录 1 坐标系的选择1.1 黄道坐标系1.2 三维空间直角坐标系 2 使用JPL星历表计算轨道2.1 日期时间2.2 特定时刻天体的位置2.3 天体运行轨道 3 太阳系模型3. 1 全家福3.2 时间、距离和半径的缩放3.3 黄道坐标系模型 天何所沓&#xff1f;十二焉分&#xff1f;日月安属&#…

做好Python工程师,首先你需要做好的几件事

做好Python工程师&#xff0c;需要做好的几件事&#xff0c;我想分享给大家。首先千万不要做事周折。在你提问之前&#xff0c;先好好想一想&#xff0c;这个问题自己能不能解决。如果能解决&#xff0c;尽量自己解决&#xff1b;如果解决不了&#xff0c;那就要把你的问题描述…