详解常见排序

目录

​编辑

插入排序

希尔排序(缩小增量排序)

选择排序

冒泡排序

堆排序

快速排序

hoare版

 挖坑法

前后指针法

非递归版

归并排序

递归版

非递归版

计数排序


声明:以下排序代码由Java实现!!!

插入排序

步骤:

1.我们可以认为数组的第一个元素已经被排好序,因此只需考虑对后面的元素进行插入排序;

2.取下一个位置的元素val,让它和它之前的元素进行比较,顺序为从右向左;

3.如果该元素大于val,则将该元素移动到该元素所处位置的下一个位置;

4.重复步骤3,知道找到已排好序的序列中小于等于val的元素;

5.将值val放到该位置的下一个位置,如果已排好序的所有元素的值都大于val,则将val存放到数组下标为0的位置;

6.重复2~5步骤。

动画演示:

代码如下:

public static void insertSort(int[] array){for(int i=1;i<array.length;i++){int tmp=array[i];int j=i-1;for(;j>=0;j--){if(array[j]>tmp)array[j+1]=array[j];elsebreak;}array[j+1]=tmp;}
}
折半插入排序 

在该值为val的元素找合适的位置时,是在已排好序的序列中进行找的,因此该过程可以使用二分查找(折半查找)来进行优化。

代码如下:

public static void bsInsertSort(int[] array){for(int i=0;i<array.length;i++){int tmp=array[i];int left=0,right=i;while(left<right){int mid=(left+right)>>1;if(tmp>=array[mid])left=mid+1;elseright=mid;}for(int j=i;j>left;j--)array[j]=array[j-1];array[left]=tmp;}
}

时间复杂度:最好情况下为O(N),此时待排数组为升序,或者说非常接近升序;

                     最坏情况下为O(N^N),此时待排数组为降序,或者说非常接近降序。

空间复杂度:O(1)

稳定性:稳定

希尔排序(缩小增量排序)

思想:

先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素划分在同一组,对每组的元素进行直接插入排序,然后再选取一个比第一增量小的整数作为第二增量gap,然后将所有距离为gap的元素划分在同一组,对每组的元素进行直接插入排序,以此类推.........,直到增量减小为1时,此时就相当于整个数组被划分为一组,进行一次直接插入排序即可。

增量gap大于1时,称为“预排序”,使得待排数组接近有序;增量gap为1时,称为直接插入排序。

动画演示

代码如下:

public static void shellSort(int[] array){int gap=array.length;while(gap>1){gap=gap/3+1;shell(array,gap);}
}private static void shell(int[] array,int gap){for(int i=gap;i<array.length;i++){int tmp=array[i];int j=i-gap;for(;j>=0;j-=gap){if(array[j]>tmp)array[j+gap]=array[j];elsebreak;}array[j+gap]=tmp;}
}

平均时间复杂度:O(N^1.3)

空间复杂度:O(1)

选择排序

每一次从待排序列中选出最小(或者最大)的一个元素,存放在待排序列的起始位置,同时将待排序列原来起始位置的值放到待排序列中最小元素的位置,直到待排数据全部排完序。

动画演示

代码如下:

public static void selectSort(int[] array){for(int i=0;i<array.length;i++){int minIndex=i;for(int j=i+1;j<array.length;j++)if(array[j]<array[minIndex])minIndex=j;swap(array,i,minIndex);}
}private static void swap(int[] array,int i,int j){int ret=array[i];array[i]=array[j];array[j]=ret;
}

实际上,我们可以每一趟同时选择出待排序列中的最小值和最大值,然后将最小值放待排序列起始位置,将最大值放到待排序列的末尾,直到待排数据全部排完序,这样的话比前一种方法快一倍。

代码如下:

public static void DoubleSelectSort(int[] array){int left=0,right=array.length-1;while(left<right){int minIndex=left,maxIndex=left;for(int i=left+1;i<=right;i++){if(array[i]>array[maxIndex])maxIndex=i;if(array[i]<array[minIndex])minIndex=i;}swap(array,left,minIndex);if(maxIndex==left)maxIndex=minIndex;swap(array,right,maxIndex);left++;right--;}
}private static void swap(int[] array,int i,int j){int ret=array[i];array[i]=array[j];array[j]=ret;
}

时间复杂度:O(N^2)

空间复杂度:O(1)

冒泡排序

进行N趟,每一趟中,如果前一个位置的元素大于后一个位置的元素,则交换两个位置的元素。

动画演示

代码如下:

public static void bubbleSort(int[] array){for(int i=0;i<array.length;i++){boolean flag=false;for(int j=0;j<array.length-1-i;j++){if(array[j]>array[j+1]) {swap(array, j, j + 1);flag=true;}}if(!flag)break;}
}

时间复杂度:O(N^2)

空间复杂度:O(1)

堆排序

排升序建大根堆,排降序建小根堆。

以排升序为例,先对数组建立大根堆,然后将堆顶元素和堆最后一个元素交换,然后从堆顶进行向下调整,不过此时堆的大小要 -1,因为已经把最大的元素找出来并放在数组的末尾了,不断重复上述操作,直到将整个数组的元素排完序。

动画演示:

代码如下:

public static void heapSort(int[] array){createBigHeap(array);int end=array.length-1;while(end>0){swap(array,0,end);shiftDown(array,0,end);end--;}
}private static void createBigHeap(int[] array){for(int parent=array.length-1-1;parent>=0;parent--)shiftDown(array,parent,array.length);
}private static void shiftDown(int[] array,int parent,int end){int child=2*parent+1;while(child<end){if(child+1<end && array[child+1]>array[child])child++;if(array[parent]<array[child]){swap(array,parent,child);parent=child;child=2*parent+1;}elsebreak;}
}private static void swap(int[] array,int i,int j){int ret=array[i];array[i]=array[j];array[j]=ret;
}

时间复杂度:O(N*logN)

空间复杂度:O(1)

快速排序
hoare版

步骤:

1.选定一个值Key,下标记为Keyi,通常是最左边的元素或者最右边的元素;

2.定义两个指针begin和end,being从左往右走,end从右往左走;

3.若选定的Key值是最左边的元素,需要end先走,若选定的Key值是最右边的元素,需要begin先走;

4.在走的过程中,当end遇到小于Key的数,才停下;然后begin开始走,直到遇到大于Key的数,然后交换位于begin和end位置的值,然后end再走,规则如上,直到begin和end相遇,此时再将位于Keyi位置的Key值和begin和end相遇点的值进行交换;

5.此时,Key左边的值都是小于等于Key的数,Key右边的值都是大于等于Key的数;

6.然后再对Key左边的数以及Key右边的数分别进行如上操作,直到待排序列只有一个元素为止。

动画演示:

代码如下: 

因为该方法包含大量的递归,当数据量较大时会发生栈溢出,因此做一些优化,包括【三数取中】和【当待排区间长度小于某个常数时,不再递归进行快排,而是使用直接插入排序】

public static void quickSort(int[] array){quick(array,0,array.length-1);
}private static void quick(int[] array,int start,int end){if(start>=end) return;if(end-start<=7){insertSortRange(array,start,end);return;}int pivot=partitionHoare(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);
}private static void insertSortRange(int[] array,int begin,int end) {for (int i = begin+1; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= begin ; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {break;}}array[j+1] = tmp;}
}private static int midOfThree(int[] array, int left, int right) {int mid = (left+right) / 2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {return right;}else {return mid;}}
}private static int partitionHoare(int[] array,int left,int right){int key=array[left];int keyi=left;while(left<right){while(left<right && array[right]>=key)right--;while(left<right && array[left]<=key)left++;swap(array,left,right);}swap(array,keyi,left);return left;
}private static void swap(int[] array,int i,int j){int ret=array[i];array[i]=array[j];array[j]=ret;
}

时间复杂度:O(N*logN)

空间复杂度:O(1) 

 挖坑法

步骤:

1.选定一个Key值,通常是位于最左边或者是最右边,在该位置形成一个坑;

2.定义两个指针left和right,left从左向右走,right从左向左走;

3.如果Key值位于数组最左边,需要right先走;如果Key值位于数组组右边,需要left先走;

4.在走的过程中,当end遇到小于Key的数,才停下,然后将right位置的值填放到坑位置,此时right位置处形成一个坑;然后begin开始走,直到遇到大于Key的数,然后将left位置的值填放到坑位置,此时left位置处形成一个坑;然后right再走,规则如上,直到left和right相遇,此时再将位于Key值填放到坑位置处;

5.此时,Key左边的值都是小于等于Key的数,Key右边的值都是大于等于Key的数;

6.然后再对Key左边的数以及Key右边的数分别进行如上操作,直到待排序列只有一个元素为止。

动画演示:

代码如下: 

因为该方法包含大量的递归,当数据量较大时会发生栈溢出,因此做一些优化,包括【三数取中】和【当待排区间长度小于某个常数时,不再递归进行快排,而是使用直接插入排序】

public static void quickSort(int[] array){quick(array,0,array.length-1);
}private static void quick(int[] array,int start,int end){if(start>=end) return;if(end-start<=7){insertSortRange(array,start,end);return;}int pivot=partitionHole(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);
}private static void insertSortRange(int[] array,int begin,int end) {for (int i = begin+1; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= begin ; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {break;}}array[j+1] = tmp;}
}private static int midOfThree(int[] array, int left, int right) {int mid = (left+right) / 2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {return right;}else {return mid;}}
}private static int partitionHole(int[] array,int left,int right){int key=array[left];while(left<right){while(left<right && array[right]>=key)right--;array[left]=array[right];while(left<right && array[left]<=key)left++;array[right]=array[left];}array[left]=key;return left;
}private static void swap(int[] array,int i,int j){int ret=array[i];array[i]=array[j];array[j]=ret;
}

时间复杂度:O(N*logN)

空间复杂度:O(1) 

前后指针法

步骤:

1.选定数组最左边的值为基准值;

2.定义两个指针prev和cur,开始时prev在最左边,cur在prev的下一个位置;

3.让cur向右走,如果cur位置的值大于基准值,只需cur继续向右移动,直到遇到比基准值小的值;

4.如果cur位置的值小于基准值,先让prev向右移动一个位置,然后交换prev位置的值和cur位置的值,直到cur走到数组末尾。

代码如下:

因为该方法包含大量的递归,当数据量较大时会发生栈溢出,因此做一些优化,包括【三数取中】和【当待排区间长度小于某个常数时,不再递归进行快排,而是使用直接插入排序】

public static void quickSort(int[] array){quick(array,0,array.length-1);
}private static void quick(int[] array,int start,int end){if(start>=end) return;if(end-start<=7){insertSortRange(array,start,end);return;}int pivot=partitionDouble(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);
}private static void insertSortRange(int[] array,int begin,int end) {for (int i = begin+1; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= begin ; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {break;}}array[j+1] = tmp;}
}private static int midOfThree(int[] array, int left, int right) {int mid = (left+right) / 2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {return right;}else {return mid;}}
}private static int partitionDouble(int[] array,int left,int right){int prev=left,cur=prev+1;while(cur<array.length){if(array[cur]<array[left] && array[++prev]!=array[cur])swap(array,prev,cur);cur++;}swap(array,prev,left);return prev;
}private static void swap(int[] array,int i,int j){int ret=array[i];array[i]=array[j];array[j]=ret;
}

时间复杂度:O(N*logN)

空间复杂度:O(1) 

非递归版

代码如下:

public static void quickSortNor(int[] array) {Stack<Integer> stack = new Stack<>();int left = 0;int right = array.length-1;int piovt = partitionHole(array,left,right);if(piovt - 1 > left) {stack.push(left);stack.push(piovt-1);}if(piovt + 1 < right) {stack.push(piovt+1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();piovt = partitionHole(array,left,right);if(piovt - 1 > left) {stack.push(left);stack.push(piovt-1);}if(piovt + 1 < right) {stack.push(piovt+1);stack.push(right);}}
}
归并排序
递归版

使用递归不断将区间二分,直到区间只有一个元素为止,然后将两个区间进行排序合并,直到将所有区间合并完。

代码如下:

public static void mergeSort(int[] array){int[] dst=new int[array.length];dst= Arrays.copyOf(array,array.length);merge(array,dst,0,array.length-1);for(int i=0;i<array.length;i++)array[i]=dst[i];
}private static void merge(int[] src,int[] dst,int start,int end){if(start>=end) return;int mid=(start+end)>>1;merge(dst,src,start,mid);merge(dst,src,mid+1,end);int i=start,j=mid+1,k=start;while(i<=mid || j<=end){if(j>end || (i<=mid && src[i]<src[j]))dst[k++]=src[i++];elsedst[k++]=src[j++];}
}

时间复杂度:O(N*logN)

空间复杂度:O(N) 

非递归版

将整个区间划分为长度为1,2,4,8,..........最大为N的小区间,然后对相邻的长度为1,2,4,8,..........最大为N的小区间分别进行排序合并,最终就排好序了。

代码如下:

public static void mergeSortNor(int[] array){int[] src=array;int[] dst=new int[array.length];for(int step=1;step<array.length;step+=step){for(int start=0;start<array.length;start+=step*2){int mid=Math.min(start+step-1,array.length-1);int end=Math.min(start+2*step-1,array.length-1);int i=start,j=mid+1,k=start;while(i<=mid || j<=end){if(j>end || (i<=mid && src[i]<src[j]))dst[k++]=src[i++];elsedst[k++]=src[j++];}}int[] tmp=src;src=dst;dst=tmp;}for(int i=0;i<array.length;i++)array[i]=src[i];
}

时间复杂度:O(N*logN)

空间复杂度:O(N) 

计数排序

先求出序列中的最大值maxVal和最小值minVal,然后开辟一个长度为maxVal-minVal+1的数组,值全都初始化为0,然后遍历整个数组,将下标为每个位置的值减去minVal处的值++,然后再重复将每个位置的值表示的次数次,将对应的值【下标+minVal】存放到原数组中。

动画演示:

代码如下: 

public static void countSort(int[] array) {int minVal = array[0];int maxVal = array[0];for (int i = 1; i < array.length; i++) {if(array[i] < minVal) {minVal = array[i];}if(array[i] > maxVal) {maxVal = array[i];}}int[] count = new int[maxVal-minVal+1];for (int i = 0; i < array.length; i++) {count[array[i]-minVal]++;}int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {array[index] = i+minVal;index++;count[i]--;}}
}

时间复杂度:O(N)

空间复杂度:O(N) 

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Python教程: 变量类型

Python 变量类型 变量存储在内存中的值。这就意味着在创建变量时会在内存中开辟一个空间。 基于变量的数据类型&#xff0c;解释器会分配指定内存&#xff0c;并决定什么数据可以被存储在内存中。 因此&#xff0c;变量可以指定不同的数据类型&#xff0c;这些变量可以存储整…

【计网】从零开始掌握序列化 --- 基础知识储备与程序重构

从零开始掌握序列化与反序列化 1 初识序列化与反序列化2 再谈Tcp协议3 程序重构3.1 Socket类3.2 回调函数设计3.3 最终的Tcp服务器类 1 初识序列化与反序列化 在刚学习计算机网络时&#xff0c;我们谈到过网络协议栈&#xff0c;其中最上层的就是应用层&#xff0c;那么这个应…

97、配置 VXLAN 不同子网互访 (分布式网关)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、基础配置SW1SW2IGP IS-IS 二、VXLAN1.引入库 总结 前言 一、基础配置 SW1 vlan 10 vlan 20interface GigabitEthernet0/0/1port link-type accessport de…

springboot+阿里云物联网教程

需求背景 最近有一个项目,需要用到阿里云物联网,不是MQ。发现使用原来EMQX的代码去连接阿里云MQTT直接报错,试了很多种方案都不行。最终还是把错误分析和教程都整理一下。 需要注意的是,阿里云物联网平台和MQ不一样。方向别走偏了。 概念描述 EMQX和阿里云MQTT有什么区别…

python编程开发“人机猜拳”游戏

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

利用Accelerate()进行pytorch的多GPU加速

简介 官方Github&#xff1a;https://github.com/huggingface/accelerate Accelerate 是为喜欢编写PyTorch模型的训练循环但不愿意编写和维护使用多GPU/TPU/fp16所需的样板代码的PyTorch用户创建的。 它可以仅加速与多 GPU/TPU/fp16 相关的样板代码&#xff0c;并保持其余代…

代码提交消息自动生成助手 | OPENAIGC开发者大赛高校组AI创新之星奖

在第二届拯救者杯OPENAIGC开发者大赛中&#xff0c;涌现出一批技术突出、创意卓越的作品。为了让这些优秀项目被更多人看到&#xff0c;我们特意开设了优秀作品报道专栏&#xff0c;旨在展示其独特之处和开发者的精彩故事。 无论您是技术专家还是爱好者&#xff0c;希望能带给…

hive建表指定列分隔符为多字符分隔符实战(默认只支持单字符)_hive row formate ###

网上学习资料一大堆,但如果学到的知识不成体系,遇到问题时只是浅尝辄止,不再深入研究,那么很难做到真正的技术提升。 需要这份系统化资料的朋友,可以戳这里获取 一个人可以走的很快,但一群人才能走的更远!不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人,都欢迎…

我国以人名命名的城市有哪些?

我国幅员辽阔&#xff0c;国内的城市非常多&#xff0c;每个城市的名字或许都有其背后的故事。 其中不乏一些以人物之名命名的城市&#xff0c;有些是上古传说中的人物&#xff0c;有些则是历史上有重要影响的人物。 湖北神农架林区&#xff0c;因炎帝神农氏而得名 而我国198…

【Linux网络 —— 网络基础概念】

Linux网络 —— 网络基础概念 计算机网络背景网络发展 初始协议协议分层协议分层的好处 OSI七层模型TCP/IP五层(或四层)模型 再识协议为什么要有TCP/IP协议&#xff1f;什么是TCP/IP协议&#xff1f;TCP/IP协议与操作系统的关系所以究竟什么是协议&#xff1f; 网络传输基本流程…

软件供应链安全管理实践之中国联通

软件供应链安全管理是保护软件开发和交付过程中所有组件的安全性和完整性的重要环节&#xff0c;软件供应链安全国家标准及政策的发布&#xff0c;为企业软件供应链安全管理提供了依据。 本文摘选自软件供应链安全推进工作组指导、苏州棱镜七彩信息科技有限公司主笔的《2023软…

编曲为什么这么难学 编曲应该从何下手,想要学习编曲,一定要有扎实的乐理基础知识

很多小伙伴在刚刚接触编曲的时候&#xff0c;可能会感觉只是学习怎么创作旋律&#xff0c;并不会很难。但在真正开始接触编曲的时候&#xff0c;却发现想要创作出好的曲目&#xff0c;要学习的知识实在是太多了&#xff0c;因此小伙伴也会感慨编曲太难学了。下面给大家详细讲解…

Python画笔案例-062 绘制彩花之太阳花

1、绘制彩花之太阳花 通过 python 的turtle 库绘制 彩花之太阳花,如下图: 2、实现代码 绘制 彩花之太阳花,以下为实现代码: """彩花之太阳花.py本程序需要coloradd模块支持,安装方法:pip install coloradd""" import turtle from coloradd…

【研赛D题成品论文】24华为杯数学建模研赛D题成品论文(第一问)+可运行代码丨免费分享

2024华为杯研究生数学建模竞赛D题精品成品论文已出&#xff01; D题 大数据驱动的地理综合问题 一、问题分析 问题一&#xff1a;目标&#xff1a;利用1990-2020年的数据&#xff0c;针对降水量和土地利用的时空演化特征进行描述。数据&#xff1a;两个核心变量&#xff0c;一…

XBOX掌机和新主机或于26年推出

原文转载修改自&#xff08;更多互联网新闻/搞机小知识&#xff09;&#xff1a; XBOX掌机和新主机或于2026年发布&#xff0c;比PS6“早点” XBOX掌机成真 关于下一代XBOX主机&#xff0c;微软相关负责人就曾坦言下一代 Xbox 将是该平台 “最大的技术飞跃”&#xff0c;在饱…

18722 稀疏矩阵的运算

思路&#xff1a; 快速转置算法的基本思想是预先计算出转置后的三元组在新数组中的位置&#xff0c;然后直接将元素放到对应的位置上。这样做的好处是只需要遍历一次原数组&#xff0c;就可以完成转置操作。 步骤如下&#xff1a; 1. 初始化一个新的三元组数组&#xff0c;用于…

“咨询+数智化”双剑合璧,毕马威与用友的“最强拍档” | 商业创新同行者

作为全球“四大”会计师事务所之一&#xff0c;毕马威被很多人熟知&#xff0c;是因为其为很多上市公司提供了财务报告的审计服务。 实际上&#xff0c;审计业务并不是毕马威的全部&#xff0c;甚至不是其最大的业务版块。在审计、税务和咨询这三大业务中&#xff0c;咨询的营…

ABB 机器人与 Profinet 转 EthernetIP 网关的高效连接

Profinet转EthernetIP网关在工业自动化领域发挥着至关重要的作用。它主要的功能就是实现不同网络协议之间的数据交互&#xff0c;为各种设备的连接与协同工作搭建了桥梁。 以连接ABB机器人为例&#xff0c;Profinet转EthernetIP网关能够将ABB机器人高效地接入到不同的网络系统…

基于Java的建筑节能监测系统+公共建筑能耗监测系统+建筑能耗监测系统+节能监测系统

建筑节能监测系统公共建筑能耗监测系统建筑能耗监测系统节能监测系统能耗监测建筑能耗监测能耗分析能耗管理能耗预测能耗监控能耗监测平台建筑能耗 介绍 建筑节能监测系统是基于计算机网络、物联网、大数据和数据可视化等多种技术融合形成的一套节能监测系统 系统实现了对建…

k8s中,pod生命周期,初始化容器,容器探针,事件处理函数,理解其设计思路及作用

k8s中&#xff0c;为什么要设计pod 平台直接管理容器不是挺好的吗 为什么要以pod为单位进行管理&#xff0c; 然后把容器放在pod里面 那么有pod和没pod的区别是什么 也就是pod提供了什么作用 这个可以考虑从pod生命周期管理的角度去思考 如图&#xff0c;pod主容器在运行…