1.算法的评判标准
在讲解排序算法之前,我们首先来了解一下评判一个算法一般都是从哪些角度来评判的。
这个只要是稍微懂一点算法的小伙伴一定知道。「这两个标准就是时间复杂度和空间复杂度」
并且一般情况下,时间复杂度是我们最注重的,毕竟类比到我们平常生活中我们一般在乎的都是这个软件运行速度怎么样,是不是快,慢的离谱之后,用户的体验就会特别的差.一般不会说这东西怎么又吃了我多少内存空间.
其次另外一点就是 「时间复杂度是体现一个算法的最核心的地方」,毕竟空间复杂度稍微大一点还是可以接受的,但是如果算法的时间复杂度降不下来,就算再怎么加空间也是解决不了问题的.
这个数据结构就是HashMap,HashMap就是一种采取牺牲空间换时间的数据结构.「Map能够直接获取到你想要键的元素」.
知道HashMap这么强大之后,大家就能知道为啥大厂问到数据结构的源码的时候一般都是会问HashMap的源码了,因为它这样设计是真的流弊.
2.排序算法的分类
了解完上述算法的评判标准之后,我们就需要来看看这些排序算法又是怎么进行分类的了. 主要有这么两种分类的方式.
排序类型
在这里插入图片描述
这里的比较就和大家平常理解的比较是一个意思,就是主要是通过比较来进行排序的.
这里的稳定就需要和大家稍微说一说了,这里的稳定指的是相同的元素在排序之后的相对位置对比排序之前是否是一样的,如果没有发生变化的,那么就称这个算法是稳定的.这样说的话,大家可能不是很能理解,这里我们还是通过下面的图来帮助大家加深印象.
了解完上面这些概念之后,接下来我们讲解排序算法的时候提出的一些概念大家就能比较好的理解了.
3.十大经典排序算法-冒泡排序,选择排序,插入排序
3.1-冒泡排序
算法思想:
说到冒泡,大家的第一反应可能就是下图里面金鱼吐泡泡的画面
在画面里面我们就能看出来,泡泡是越往上泡泡越大.这个就是冒泡排序的核心思想:每次循环都找出剩余排序序列中的一个最大值或最小值,并且将它置换到序列的最末尾或者是最开始的位置.举下面这个简单的例子,大家就能理解了:
这就是冒泡排序的基本思想.并且我们能稍微总结一下冒泡排序的特点:
算法图解:
在这里插入图片描述
示例代码:
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- for(int i=0;i<num.length-1;i++) {
- for(int j=0;j<num.length-1-i;j++) {
- if(num[j]>num[j+1]) {
- int temp=num[j+1];
- num[j+1]=num[j];
- num[j]=temp;
- }
- }
- System.out.print("第"+(i+1)+"次排序结果:");
- for(int j=0;j<num.length;j++)
- System.out.print(num[j]+" ");
- System.out.println();
- }
- long endTime=System.currentTimeMillis();
- System.out.println("程序运行时间: "+(endTime-startTime)+"ms");
- }
在这里插入图片描述
复杂度分析:
理解完冒泡排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
这个我们也可以看到我们整个排序的过程中值增加了一个空间,这个空间就是我们定义的temp,主要就是帮助我们进行元素的交换的.所以冒泡排序的空间复杂度即为O(1)
3.2-选择排序
算法思想: 选择排序的重点就是选择,选择的方式就是每次循环选出最小的元素,然后将最小的元素与排序序列中的队头元素进行置换.还是老样子,通过下面的图来让大家更好的理解这一个选择的过程:
这是我们基本就能理解选择排序的基本概念.这里我们「需要和上面的冒泡排序区分一点」的就是,选择排序「在比较结束之后并不会直接交换两个元素的位置,只是记录当前序列中的最小元素」 ,当找到最小的元素之后,在将该最小元素与队头的元素进行置换. 了解完这些之后,我们也来稍微说一下选择排序的特点:
算法图解:
在这里插入图片描述
示例代码:
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- for(int i=0;i<num.length-1;i++) {
- int min=i;
- for(int j=i+1;j<num.length;j++) {
- if(num[min]>num[j]) {
- min=j;
- }
- }
- if(i!=min) {
- int temp=num[i];
- num[i]=num[min];
- num[min]=temp;
- }
- System.out.print("第"+(i+1)+"次排序结果:");
- for(int j=0;j<num.length;j++)
- System.out.print(num[j]+" ");
- System.out.println();
- }
- long endTime=System.currentTimeMillis();
- System.out.println("程序运行时间: "+(endTime-startTime)+"ms");
- }
复杂度分析:
理解完选择排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
这个我们也可以看到我们整个排序的过程中值增加了两个个空间,这个空间就是我们定义的temp和min,所以选择排序的空间复杂度也是常量级别的即为O(1)
3.3-插入排序
算法思想: 插入排序的算法思想则是将整个序列划分成两段,一段时已经排序完成的序列,另一端序列则是仍然无需的状态.就比方下图所示:
分成这样两个序列之后,插入序列每次都是挑选待排序序列的队头元素插入到已有序的序列之中,从有序序列的队尾开始比较,如果比该元素大的话,将该元素后移,一旦出现小于该元素的元素,插入当前的位置.这个就是插入排序名字的由来.
说了半天大家可能还是不太了解,还是通过下面的图来详细讲解一下该算法的执行过程吧:
理解完插入排序算法的基本思想之后我们再来看看该算法的特点:
算法图解:
在这里插入图片描述
示例代码:
- public static void main(String[] args) {
- int []num ={7,4,9,3,2,1,8,6,5,10};
- long startTime=System.currentTimeMillis();
- for(int i=1;i<num.length;i++) {
- int temp=num[i];
- int j=i;
- while(j>0&&temp<num[j-1]) {
- num[j]=num[j-1];
- j--;
- }
- if(j!=i) {
- num[j]=temp;
- }
- System.out.print("第"+i+"次排序结果:");
- for(int k=0;k<num.length;k++)
- System.out.print(num[k]+" ");
- System.out.println();
- }
- long endTime=System.currentTimeMillis();
- System.out.println("程序运行时间: "+(endTime-startTime)+"ms");
- }
在这里插入图片描述
复杂度分析:
理解完插入排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
这个我们也可以看到我们整个排序的过程中值增加了两个个空间,这个空间就是我们定义的temp和j,所以选择排序的空间复杂度也是常量级别的即为O(1)
本文转载自微信公众号「萌萌哒的瓤瓤」,可以通过以下二维码关注。转载本文请联系萌萌哒的瓤瓤公众号。
作者:小傅哥 博客: https://bugstack.cn 沉淀、分享、成长,让自己和他人都能...
本文转载自微信公众号「Java大数据与数据仓库」,作者老董。转载本文请联系Java...
在使用裸金属服务器前,您需要完成本文中的准备工作。 注册华为云并实名认证 为...
网络配置 设置“网络”:在下拉列表中选择可用的虚拟私有云、子网,并设置私有IP...
1. 接口描述 接口请求域名: cvm.tencentcloudapi.com 。 本接口 (AssociateInst...
背景介绍 监控告警系统作为最为常用的服务 能够让开发运维人员时刻了解服务的当...
今天,国际权威AI基准测试MLPerf公布了2021年最新推理测试榜单。 图像分类性能测...
真正的数据价值取决于对业务的洞察力。 数据分析是企业拥有的最强大的资源之一。...
腾讯 云虚拟主机 叫什么?腾讯云现在基本搜不到 虚拟主机 了,像阿里云也不怎么...
云服务器 内存最大多少?内存是决定 云服务器 性能的非常重要的一个参数,内存最...