【数据结构】关于快速排序,归并排序,计数排序,基数排序,你到底了解多少???(超详解)

本文主要是介绍【数据结构】关于快速排序,归并排序,计数排序,基数排序,你到底了解多少???(超详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

🌟🌟Hello家人们,这期继续讲解排序算法的原理,希望你能帮到屏幕前的你。

🌈上期博客在这里:http://t.csdnimg.cn/g7PyB

🌈感兴趣的小伙伴看一看小编主页:GGBondlctrl-CSDN博客

目录

📚️1.比较排序与非比较排序

📚️2.比较排序

2.1快速排序

1.递归基本思想:

2.非递归基本思想 :

 3.Hoare法:

4.挖坑法:

5.双指针(了解):

 6.快速排序总结:

2.2归并排序

1.递归基本思想:

2.非递归基本思想:

3.实现合并:

4.归并排序总结:

📚️3.非比较排序

3.1计数排序

3.2基数排序

📚️4.总结


📚️1.比较排序与非比较排序

排序算法主要分为比较排序和非比较排序两大类:
1.比较排序:

比较算法通过比较元素的大小来确定它们的相对顺序。常见的比较排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等,本期小编将讲述快速排序,归并排序。

2.非比较排序:

非比较排序算法则不依赖于元素之间的直接比较来确定顺序。例如,计数排序、桶排序、基数排序等,小编这期将
 两者的区别:


1.比较排序的优点是其思想相对简单直观,易于理解和实现。但它的缺点也较为明显,比较操作的次数通常与待排序元素的数量呈特定的函数关系,导致其时间复杂度在最坏情况下可能较高。
 
2.非比较排序的优势在于在某些特定情况下,能够在较低的时间复杂度内完成排序。但它们往往需要额外的空间来辅助排序,并且对数据的特征有一定要求。

总的来说,比较排序适用于一般性的排序需求,而非比较排序在数据具有特定特征或对时间复杂度有极高要求时表现出色。具体使用哪种排序算法,取决于数据的特点、问题的规模以及对时间和空间复杂度的权衡。

📚️2.比较排序

2.1快速排序

1.递归基本思想:

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

这里就要每次根据基准来进行递归,实现快速排序:

图解:

代码实现:

public static void Quick(int[] array,int start,int end){if(start>=end)return;int privot=privot2(array,start,end);Quick(array,start,privot-1);Quick(array,privot+1, end);}

 这里要规定开始的索引下标,以及结束的索引下标; 

2.非递归基本思想 :

在非递归思想就是要运用栈这个结构,我们要找到实现基准查找的左右指针,先导入第一次基准后,进行循环,实现右树基准的查找,这里每次要进行出栈进行基准查找,找完之后进栈左右指针。

代码实现:

  public static void Quicknor(int[] array){Stack<Integer> stack=new Stack<>();int left=0;int right= array.length-1;int privot=privot1(array,left,right);if (privot-1>left){stack.push(left);stack.push(privot-1);}if(privot+1<right){stack.push(privot+1);stack.push(right);}while (!stack.isEmpty()){right=stack.pop();left=stack.pop();privot=privot1(array,left,right);if (privot-1>left){stack.push(left);stack.push(privot-1);}if(privot+1<right){stack.push(privot+1);stack.push(right);}}}

注意:这里要判断基准的左右是否还存在至少两个数据,存在才进栈,否则不进入。 

上述已经完成了基本的递归思想,那么接下来就要进行基准的实现了~~~

 3.Hoare法:

查找基准思路:

设置两个最左端索引(left),和最右端索引(right),和一个关键下标表示key;最右端索引进行向前遍历,若所表示的值大于key,那么right--,如果发现了大于key的值,那么就进行left向前遍历,若小于key,那么left++,直到发现比key大的数据,然后交换right和left,直到两者相遇,最后与key进行交换。

图解: 

代码实现:

 public static int privot(int[] array,int left,int right){int key=array[left];int i=left;while (right>left){while (array[right]>=key&&left<right){right--;}while (array[left]<=key&&left<right){left++;}swap(right,left,array);}swap(i,left,array);return left;}
4.挖坑法:

查找基本思路:

和上述Hoare思想基本一致,但是当right索引发现比key小的数值时,left索引所指向的数值就为right索引所指的值,当left索引发现比key大的数值时,right索引所指向的数值就为left索引所指的值,两者相遇后与最初始的left索引所指的数值进行交换。

 图解:

代码实现:

 public static int  privot1(int[] array,int left,int right){int privot=array[left];while (left<right){while (array[right]>=privot&&left<right){right--;}array[left]=array[right];while (array[left]<=privot&&left<right){left++;}array[right]=array[left];}array[left]=privot;return left;}
5.双指针(了解):

代码实现:

 public static int privot2(int[] array,int left,int right){int prev=left;int k=array[prev];int cur=left+1;while (cur<=right){if(array[cur]<k&&(++prev)!=cur){swap(cur,prev,array);}cur++;}swap(prev,left,array);return prev;}

这里的双指针法了解就好,小编不再赘述,可以画图理解一下。

 6.快速排序总结:


1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序


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


3. 空间复杂度:O(logN)


4. 稳定性:不稳定

2.2归并排序

1.递归基本思想:

运用递归实现,我们需要进行查找中间索引,进行两两拆分直到只有一个数据,再实现两两合并。

图解: 

代码实现: 

public static void Merge(int[] array,int left,int right){if(left>=right){return;}int mid=(left+right)/2;Merge(array,left,mid);Merge(array,mid+1,right);mergeCore(array,left,right,mid);}
2.非递归基本思想:

即分组进行合并排序,先是一个和一个,再次为二和二到最后全部合并(这里的合并是排好序的)

图解:

代码实现:

public static void Mergenor(int[] array){int left;int right;int gap=1;int mid;while (gap<array.length){for (int i = 0; i < array.length; i+=2*gap) {left=i;mid=left+gap-1;right=mid+gap;if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}mergeCore(array,left,right,mid);}gap*=2;}}
3.实现合并:

实现合并思想:

小编在这里认为当两个数组进行合并时,第一个数组的第一个元素与第二个数组的第一个元素进行比较,如果那个更小,在与另一个数组下标加一后的值进行比较,直到索引越界。

图解: 

代码实现 :

 public static void mergeCore(int[] array,int left,int right,int mid){int[] tmp=new int[right-left+1];int k=0;int s1=left;int s2=mid+1;while (s1<=mid&&s2<=right){if(array[s1]<=array[s2]){tmp[k]=array[s1];k++;s1++;}else {tmp[k]=array[s2];k++;s2++;}}while (s1>mid&&s2<=right){tmp[k]=array[s2];s2++;k++;}while (s2>right&&s1<=mid){tmp[k]=array[s1];k++;s1++;}for (int i = 0; i <k ; i++) {array[i+left]=tmp[i];}}
4.归并排序总结:

1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(N)
4. 稳定性:稳定

📚️3.非比较排序

3.1计数排序

思路步骤:

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

图解: 

代码实现: 

 public static void CountSort(int[] array){int max=array[0];int min=array[0];for (int i = 1; i < array.length; i++) {if (array[i]<min){min=array[i];}if(array[i]>max){max=array[i];}}int[] tmp=new int[max-min+1];for (int i = 0; i < array.length ; i++) {tmp[array[i]-min]++;}for (int i = 0; i < tmp.length ; i++) {while (tmp[i]!=0){System.out.print(i+min+" ");tmp[i]--;}}}

注意:若为90-100区间,不可能申请100个长度,这样会造成浪费,所以数组长度是最大值减去最小值加1;所以0下标的值就为数据0+数据最小值,1下标的值为1+最小值。

计数排序总结:

1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度: O(MAX(N, 范围 ))
3. 空间复杂度: O( 范围 )
4. 稳定性:稳定

3.2基数排序

思路:

通过二维数组进行存储,导入对应位置的数值,然后再设置一个一维数组进行每行个数的值,进行打印,循环最大数的长度,就能在最后一次打印中取得顺序数组。

 图解:

代码如下: 

 public static void BaseSort(int[] array){int max=max(array);int maxLength=0;while (max!=0){max/=10;maxLength++;}int[][] bucket = new int[10][array.length-1];int[] elementCount = new int[10];int n=1;for (int i = 0; i < maxLength; i++) {for (int j = 0; j < array.length ; j++) {int element=array[j]/n%10;bucket[element][elementCount[element]]=array[j];elementCount[element]++;}//拿出数据int index=0;for (int j = 0; j <elementCount.length ; j++) {if(elementCount[j]!=0){for (int k = 0; k < elementCount[j]; k++) {array[index]=bucket[j][k];index++;}}elementCount[j]=0;}n*=10;}}public static int max(int[] array){int max=array[0];for (int i = 1; i < array.length ; i++) {if(array[i]>max){max=array[i];}}return max;}
}

注意:这里不仅要求最大值,还要求最大值的长度来表示循环次数,每次循环条件是要变化的,依次按照位数来进行操作,每次输出后再重新载入到二维数组中。

📚️4.总结

💬💬小编这期讲解了关于比较排序的最后两个排序:快速排序,归并排序,关于他们的代码以及思路都罗列了出来,还有包括非比较排序的基数排序,计数排序的思路原理和代码实现。

对于每个排序都要掌握它的基本原理,对于以上两个比较排序来说,还要了解二叉树的概念。

🌅🌅🌅~~~~最后希望与诸君共勉,共同进步!!!


                               💪💪💪以上就是本期内容了, 感兴趣的话,就关注小编吧。

                                                         😊😊  期待你的关注~~~ 

 

这篇关于【数据结构】关于快速排序,归并排序,计数排序,基数排序,你到底了解多少???(超详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl