排序算法二 归并排序和快速排序

目录

归并排序

快速排序

1 挖坑法​编辑

2 Hoare法

快排的优化

快排的非递归方法

七大排序算法复杂度及稳定性分析


归并排序

归并排序是建立在归并操作上的一种有效的排序算法,将以有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,在使子序列段间有序.若将两个有序的序列合并成一个有序表,成为二路归并.

归并排序的递归写法:

1:  首先建行区间一分为二,分裂点 : mid = ( left + right ) / 2;

2:  递归的对两个子区间array[left..mid] 和 array[mid+1 ... right]进行归并排序.递归的终止条件是子区间的长度为1.

3:  将两个子区间归并为一个有序的空间.但我们归并右树的时候不是从原来数组的0下标开始,所以我们在归并的时候要加上他原来数组所在的下标 即 array[i + start] = tmp[i];

代码:

public void mergeSort(int[] array) {sort(array,0,array.length-1)}private void sort(int[] array,int left,int right) {if(left >= right) {return;}int mid = (left + right) / 2;sort(array,left,mid);sort(array,mid+1,right);//合并merge(array,left,right,mid);}//合并private void merge(int[] array,int start,int end,int mid) {int s1 = start;int s2 = mid + 1;int[] tmp = new int[end - start + 1];int k = 0;while(s1 <= mid && s2 <= end) {if(array[s1] <= array[s2]) {tmp[k++] = array[s1++];} else {tmp[k++] = array[s2++];}}while(s1 <= mid) {tmp[k++] = array[s1++]}while(s2 <= end) {tmp[k++] = array[s2++];}for (int i = 0; i < tmp.length; i++) {array[i + start] = tmp[i];}}
}

归并排序的非递归写法:

首先将一组序列的每个元素看做一个单独的序列,进行比较之后排好序,然后在每两个一组进行比较,直到组数和和序列的个数相同,序列就拍好序了

归并排序的特性总结 :

归并排序的时间复杂度是O(N* log₂N),空间复杂度是O(N),稳定性是稳定的排序

快速排序

快速排序是一种二叉树结构的交换排序方法,其基本思想是任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序结合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后按照左右子序列重复该过程,直到所有元素排列在相应位置上位置.

动图展示

快速排序有很多方法,在这里我主要讲两种方法

1 挖坑法

首先我们在这个排序序列中随便找一个基准值,通常为了方便,以第一个数作为基准值,然后我们从后往前找比基准值小的元素,找到后把这个元素放到基准值的位置

然后我们从前往后找比基准值大的元素,然后把这个元素放到坑里.会出现一个新的坑

然后重复上面操作直到将left和right相遇,我们把基准值放到坑位里面.

代码展示

大家想想,我们在内层while循环中, <= 和 >=能换成> 和 < 吗?

答案是不可以的 

当最后一个元素和第一个元素大小相等的时候,如果取 > 和 < 的情况下,是要进行和基准值交换的,当从后往前走完后,从前往后走,又满足交换条件,这样就成了死循环.

Hoare法

同样的方法我们先找一个基准,然后从后往前找比基准值小的,找到后从前往后找比基准值大的,找到后交换两个的位置

然后重复上面的操作直到lleft和right相遇

然后让array[left] 和基准值交换位置,我们发现比基准值小的都在基准值的左边,比基准值大的都在基准值的右边

根据两种方法的比较,我们会发现两种序列的顺序是不一样的,

当我们左边找基准值的时候,为什么要从右边先走呢?

以Hoare法为例,当我们先从左边走,在走右边,交换后right位置的值一定比基准值大,当Left和right相遇的时候,将左边的值和基准值交换,较大值就排到前面去了,就不满足基准值左边的都比基准值小的性质了

快速排序的基本特性

快速排序是一种二叉树结构的交换排序方法.

时间复杂度: 最好的情况  O(N * log₂ N)  ,最坏的情况给的序列本来就有序,在递归的时候只会是一棵单支树,树的高度就为N,时间复杂度为O(N ^ 2),

空间复杂度:  最好情况: O(log₂ N), 最坏情况 : O(N)

稳定性: 不稳定的

快速排序需要再系统内部用一个栈来实现递归,每层递归调用时的指针和参数均需要用栈来存放,快速排序的递归过程可以用一颗二叉树来表示,当数据量较大时,在最坏的情况时,可能会发生栈溢出异常,所以我们要对快速排序进行优化.

快排的优化

三数取中法

在一组排序序列中,我们选取三个数,分别是第一个数,中间位置的数和最后一个数,在这三个数中选取中间大的数作为基准数. 这样就不会出现单支树的情况. 

如何在三个数中找中间大的数呢?

快速排序是一种二叉树结构的交换排序方法.在二叉树中,层数越多,下面的节点数就越多,也趋于有序,在后面两层可以直接使用直接插入法进行排序,减少递归的次数.

 public void quickSort(int[] array) {quick(array,0,array.length-1);}private void quick(int[]array,int start, int end) {if(start >= end) {return ;}if(end - start + 1 <= 14) {//插入排序insertSoft2(array,start,end);return;}int index = midThree(array,start,end);swap(array,index,start);int piovt = partition(array,start,end);quick(array,start,piovt-1);quick(array,piovt+1,end);}private int partition(int[] array,int left,int right) {int tmp = array[left];int i = left;while(left < right) {while(left < right && array[right] >= tmp) {right--;}array[left] = array[right];while(left < right && array[left] <= tmp) {left++;}swap(array,left,right);}swap(array,left,i);return left;}public static void insertSoft2(int[] array,int left,int right) {for(int i = left+1; i <= right;i++) {int tmp = array[i];int j = i -1;for(j =i-1; j >= left ;j--) {if(array[j] > tmp) {array[j+1] = array[j];} else {array[j+1] = tmp;break;}}array[j+1] = tmp;}}

快排的非递归方法

在第一次找到基准值之后,我们将基准值左边和右边的下标放到栈中,第一次弹出栈顶元素给到right在弹出栈顶元素给left.重新找基准值,找到后把基准值左右两边重新入栈,重复上述操作但当基准值左右两边只有一个元素的时候,就不需要再入栈,此时已经是有序的了,把最开始的基准值右边的排完后,排基准值左边的.,直到栈为空的时候,排完序.

第一次弹出栈顶元素给到right在弹出栈顶元素给left.重新找基准值,找到后把基准值左右两边重新入栈,重复上述操作但当栈为空的时候排序完成

public void quickSort(int[] array) {Deque<Integer> stack = new LinkedList<>();int left = 0;int right = array.length - 1;int pivot = partition(array,left,right);if(pivot > left + 1) {stack.push(left);stack.push(pivot -1);}if(pivot < right- 1) {stack.push(pivot+ 1);stack.push(right);}while(!stack.isEmpty()) {right = stack.pop();left = stack.pop();pivot = partition(array,left,right);if(pivot > left + 1) {stack.push(left);stack.push(pivot -1);}if(pivot < right- 1) {stack.push(pivot+ 1);stack.push(right);}}
}
private int partition(int[] array,int left,int right) {int tmp = array[left];while(left < right) { while(left < right && array[right] >= tmp) {right--;}array[left] = array[right];while(left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}}

七大排序算法复杂度及稳定性分析

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

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

相关文章

virtualbox无界面打开linux虚拟机的bat脚本,以及idea(代替Xshell)连接linux虚拟机的方法

virtualbox无界面打开linux虚拟机的bat脚本&#xff0c;以及idea连接linux虚拟机的方法 命令行运行代码成功运行的效果图 idea连接linux虚拟机的方法【重要】查看虚拟机的IP地址idea中选择菜单&#xff08;该功能可代替Xshell软件&#xff09;配置设置连接成功进入idea中的命令…

2018-2022年盟浪 ESG数据

2018-2022年盟浪 ESG数据 1、时间&#xff1a;2018-2022年 2、指标&#xff1a;证券代码、证券简称、盟浪ESG评级、省份、城市、所属证监会行业名称[交易日期] 最新收盘日[行业级别] 大类行业、所属证监会行业代码[交易日期] 最新收盘日[行业级别] 大类行业 3、范围&#xf…

ISE_ChipScope Pro的使用

1.ChipScope Pro Core Inserter 使用流程 在之前以及编译好的流水灯实验上进行学习 ChipScope的使用。 一、新建一个ChipScope 核 点击Next,然后在下一个框中选择 Finish&#xff0c;你就会在项目菜单中看到有XX.cdc核文件。 二、对核文件进行设置 右键“Synthesize – XST” …

【LeetCode热题100】--53.最大子数组和

53.最大子数组和 使用动态规划&#xff1a; 状态定义&#xff1a;设动态规划列表dp&#xff0c;dp[i]代表以元素nums[i]为结尾的连续子数组最大和 转移方程&#xff1a;若dp[i-1]≤0,说明dp[i-1]对dp[i]产生负贡献&#xff0c;即dp[i-1]nums[i]还不如nums[i]本身大 初始状态&…

vue+element项目创建步骤

一、创建vue项目步骤 要创建一个Vue Element UI的项目&#xff0c;你可以按照以下步骤进行操作&#xff1a; 1.确保你已经安装了Node.js和npm&#xff08;Node.js的包管理器&#xff09;。你可以在命令行中运行以下命令来检查它们是否已经安装&#xff1a; node -vnpm -v2.使…

打开深度学习的锁:(2)单隐藏层的神经网络

打开深度学习的锁 导言PS&#xff1a;神经网络的训练过程一、数据集和包的说明1.1准备文件1.2 需要导入的包 二、构建神经网络的架构三、初始化函数四、激活函数4.1 tanh&#xff08;双曲正切函数&#xff09;函数 五&#xff0c;前向传播六、损失函数七、后向传播八、梯度下降…

vite + vue3 + js 搭建组件库 + 核心配置与使用

vite.config.js 这个官网有写 import { defineConfig } from vite import vue from vitejs/plugin-vue import path from "path" // https://vitejs.dev/config/ export default defineConfig({plugins: [vue()],server:{open:true, //自动打开浏览port:8088 //默认…

适用于初学者,毕业设计的5个c语言项目,代码已开源

C语言项目集 项目介绍 该项目适用于初学者学习c语言&#xff0c;也适用于高校学生课程设计&#xff0c;毕业设计参考。 项目并不能满足所有人的需求&#xff0c;可进行项目指导&#xff0c;定制开发。 开源地址 c语言项目代码地址 项目列表 该项目包含如下5个管理系统&am…

游戏录屏软件推荐,教你录制高清游戏视频

“有没有好用的游戏录屏软件推荐呀&#xff0c;最近当上了游戏主播&#xff0c;平台要求每天都要发一个游戏视频&#xff0c;可是我的游戏录屏软件太拉胯了&#xff0c;录制出来的视频非常糊&#xff0c;导致平台审核不通过&#xff0c;所以想问问大家有没有游戏录屏软件推荐一…

Vue的单文件组件(Single File Components):优势与实例

Vue的单文件组件&#xff08;Single File Components&#xff09;&#xff1a;优势与实例 Vue.js 是一款流行的前端 JavaScript 框架&#xff0c;它采用了一种特殊的组件化开发方式&#xff0c;被称为单文件组件&#xff08;Single File Components&#xff0c;简称 SFC&#…

Eclipse初步学习使用

1.配置自动填充 window->preference 2.自动判断错误&#xff0c;并给出解决方法 3.创建可执行文件&#xff1a; 新建package&#xff0c; 包内新建 javaclass&#xff0c;选择psvm&#xff0c; 4.编写程序&#xff0c;进行执行 右键&#xff0c;选择 run as applic…

ideogram.ai 不同风格的效果图

https://ideogram.ai/ 提示词&#xff1a; French bulldog with sunglasses, playing skateboarding, speed up, happiness, front viewPhoto 相片 正常照片 Poster 海报 偏绘画&#xff0c;清晰的勾线 3D Render 3D 渲染 胶质感&#xff0c;像 3D 模型 Typography …

MySQL学习笔记15

1、内连接查询&#xff08;重点&#xff09;&#xff1a; 基本语法&#xff1a; select 数据表1.字段列表,数据表2.字段列表 from 数据表1 inner join 数据表2 on 连接条件; 案例&#xff1a;获取产品表中每个产品的分类信息&#xff1a; mysql> select * from tb_goods …

Linux-文件和目录权限

文章目录 权限的作用普通文本文件的权限作用目录文件权限功能作用 文件权限的设置 权限的作用 权限对于普通文件和目录文件的作用是不一样的。 普通文本文件的权限作用 drwxr-xr-x第二个字母开始是文件的权限表示9列权限&#xff0c;前三列表示文件的"拥有者"对该…

vue组件样式 scoped 冲突

vue组件样式 冲突 <template><div class"base-one">BaseOne</div> </template><script> export default {}; </script>/* 1.style中的样式 默认是作用到全局的2.加上scoped可以让样式变成局部样式组件都应该有独立的样式&…

如何将前后端分离的项目部署在服务器上

宝塔Linux部署&#xff1a; 因为要部署前端我们先下个nigx Tomcat,下载这个只是为了java&#xff0c;它里面包含java的 前端 在去添加站点&#xff0c;域名暂时是自己的公网 然后打开新建的站点&#xff0c;把里面的文件全删掉&#xff0c;再把自己的前端dist里的文件全选拖…

使用ALU,RAM,寄存器打造一个CPU

CPU简介 计算机的心脏是中央处理单元&#xff0c;简称“CPU” 。这篇文章就利用前几篇文章中提到过的ALU,RAM,寄存器组件做一个CPU。 CPU负责运行程序&#xff0c;程序是由一个个操作组成的&#xff0c;这些操作叫做指令&#xff0c;因为他们“指示”计算机要做什么. CPU能做什…

算法通过村第九关-二分(中序遍历)黄金笔记|二叉搜索树

文章目录 前言1. 有序数组转二叉搜索树2. 寻找连个正序数组的中位数总结 前言 提示&#xff1a;有时候&#xff0c;我感觉自己一辈子活在两个闹钟之间&#xff0c;早上的第一次闹钟&#xff0c;以及5分钟之后的第二次闹钟。 --奥利弗萨克斯《意识的河流》 每个专题都有简单题&a…

上海亚商投顾:沪指震荡反弹 汽车产业链全天强势

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 大小指数昨日集体反弹&#xff0c;沪指3100点失而复得&#xff0c;创业板指一度涨超1.5%&#xff0c;随后涨幅…

echarts学习总结

一、新建一个简单的Echarts 首先新建一个vue2的项目&#xff0c;项目中安装Echarts cnpm install echarts --save1、title标题组件&#xff0c;包含主标题和副标题。 2、tooltip提示框组件 3、 legend图例组件 4、 series