1。算法判断标准在讲解排序算法之前，我们先来了解一下一个算法一般从哪些角度来判断。对算法稍有了解的人一定知道这一点。“这两个标准是时间复杂度和空间复杂度”Timecomplexity时间复杂度，这个其实很好理解，从字面意思我们可以很好理解，就是整个算法执行完需要多长时间那里是这个时间复杂度的两个判断标准。其实严格来说就是三种，即“bestcase，averagecase，worstcase”，但是一般我们不讨论bestcase，因为这个没有意义。所以我们一般讨论平均情况和最坏情况。而且总的来说，时间复杂度是我们最关注的。毕竟在我们的日常生活中，我们关心的是软件运行的速度有多快，快不快，慢到离谱之后，用户体验会特别差。一般不会说这个东西吃掉多少内存空间。第二点是“时间复杂度是一个算法的核心”，毕竟空间复杂度稍微大一点是可以接受的，但是如果不能降低算法的时间复杂度，无论增加多少空间，问题都无法解决得到解决。Spacecomplexity空间复杂度其实很好理解，指的是“在算法执行过程中，算法占用了多少内存空间？一般情况下你不会特别关心空间复杂度。但是这里举一个数据结构的例子给大家，让大家第一时间理解这个概念，这个数据结构就是HashMap，而HashMap是一个牺牲空间换取时间的数据结构，“Map可以直接获取到你想要key的元素”。在知道HashMap是这样之后强大，大家就知道为什么大厂要问数据结构的源码了，一般我会问HashMap的源码，因为它的设计实在是太烂了。以上算法，我们要看看这些排序算法是如何分类的没错，主要有两种分类方式，这里插入排序类型来描述图片e.这里的比较和大家平时理解的比较是同一个意思，就是主要通过比较来进行排序。这里稳定不稳定。跟大家说一下，这里的稳定性指的是同一个元素排序后的相对位置是否和排序前一样。如果没有变化，则称该算法是稳定的。这样一来，您可能无法很好地理解它。这里我们还是用下图来帮助大家加深印象。理解了以上概念后，你就可以理解我们在讲解排序算法时提出的一些概念了。3、十大经典排序算法——冒泡排序、选择排序、插入排序3.1——冒泡排序算法思想：说到冒泡，大家的第一反应可能是下图中金鱼吐泡泡的画面。可以看出泡沫比较多泡沫越大。这就是冒泡排序的核心思想：每次循环在剩余的排序序列中寻找一个最大值或最小值，并将其替换到序列的末尾或开头。举下面这个简单的例子，大家就明白了：这就是冒泡排序的基本思想。而我们可以简单总结一下冒泡排序的特点：每次排序都可以“至少确定一个元素的最终位置”Bubble冒泡排序是“稳定的”，“只有当元素的大小不同时，元素之间的位置才会beexchanged”，使得排序前后相同元素的相对位置不变，冒泡排序是稳定的。冒泡排序存在“极端情况”。如果“我们规定的排序方式是从大到小”，“但是原序列的顺序是从小到大”，那么朋友们这时候就会发现，我们“每次比较元素后，需要交换这两个元素”时间”。这种情况是冒泡排序最极端的情况。算法图：此处插入图片描述示例代码：publicstaticvoidmain(String[]args){int[]num={7,4,9,3,2,1,8,6,5,10};longstartTime=System.currentTimeMillis();for(inti=0;inum[j+1]){inttemp=num[j+1];num[j+1]=num[j];num[j]=temp;}}System.out.print("th"+(i+1)+"第二次排序结果：");for(intj=0;jnum[j+1])的过程，这个过程就是我们两层for循环的平均次数，我们可以计算出这个是n*(n-1)/2，我们走到最大次数，可以看到时间复杂度是O(n*n)worstcase最坏情况就是我们上面说的极端情况。但是在极端情况下，交换元素的操作比我们的平均情况执行的多，但是比较的次数总是一样的，所以时间复杂度也是O(n*n)空间复杂度。这个我们也可以看到，在我们整个排序过程中，值都加了一个空格。这个空间就是我们定义的temp，主要是帮助我们交换元素。因此，冒泡排序的空间复杂度为O(1)3.2-选择排序算法的思想：选择排序的关键点在于选择。选择方法是每次循环选择最小的元素，然后用排序序列中的头元素替换最小的元素。还是一样，通过下图让大家更好的理解这个选择排序的过程：这是我们基本可以理解选择排序的基本概念。这里我们“需要和上面的冒泡排序稍微区别一下”的是，选择排序“不会直接交换两个元素的位置，只是记录当前序列中最小的元素”。当找到最小元素时，将最小元素替换为队列头部的元素。了解了这些，再稍微说说选择排序的特点：“每次循环必须能够确定一个元素的最终位置”，这和冒泡排序是一样的。选择排序也是不稳定的。这里你可能不明白。下面我们还是照例通过图片来掩盖一下，大家就明白了：算法图：这里插入图片说明示例代码：publicstaticvoidmain(String[]args){int[]num={7,4,9,3,2,1,8,6,5,10};longstartTime=System.currentTimeMillis();for(inti=0;inum[j]){min=j;}}if(i!=min){inttemp=num[i];num[i]=num[min];num[min]=temp;}系统.out.print("th"+(i+1)+"排序结果：");for(intj=0;jnum[j])的过程，这个过程就是我们两层for循环的平均次数，我们可以计算出这个是n*(n-1)/2，我们去最大次数，可以看到时间复杂度是O(n*n)worstcase最坏情况和我们的平均情况本质上是一样的，因为不管是平均情况还是最坏情况，他们只替换了最小元素和末尾的头元素的位置，比较的次数是一样的，所以时间复杂度也是O(n*n)空间复杂度。我们也可以看到我们整个排序过程中给值加了两个空格。这个空间就是我们定义的temp和min，所以选择排序的空间复杂度也是一个常数级的，也就是O(1)3.3-插入排序算法思想：插入排序的算法思想是是除法整个序列分成两段，已经排序了一段时间的序列，另一端的序列还处于不需要的状态。例如，如下图：分为这样的两个序列后，每次都选择插入序列进行排序将序列的头部元素插入到有序序列中，从有序序列的尾部开始比较，如果比元素大，则元素向后移动，一旦出现比元素小的元素，就插入到当前位置。这就是插入排序名称的由来。说了半天，你可能还是听不懂。下面通过下图来详细解释一下算法的执行过程：了解了插入排序算法的基本思想后，我们来看看算法。Features：这个其实是“不是一个特征”，但是对比上面两个算法可以发现算法不像上面的冒泡和选择排序一样，每次循环排序可以确定一个元素的最终位置。“插入排序不能唯一确定一个元素在每次循环排序后的最终位置。它只能在每次循环后确定某些元素的相对位置。”插入排序和冒泡排序也有“极端排序情况”，不过冒泡排序的极端情况是最差的情况，而插入排序的极端情况是最酷的情况。在序列基本有序的情况下，插入排序是最快的，时间复杂度可以达到O(n)，属于线性级别。“因为一旦顺序排列好了，for循环还是要执行的，但是在while循环中根本就不用了。”Executed”，这是插入排序线性层次的关键。相对于冒泡和选择排序，“都是通过两层for循环执行的，但是插入排序的第二层循环是通过while，并且有相应的终止条件”，这使得插入排序的性能相对好于上述两种。当然，“这种情况只存在于序列已经基本有序的情况下”。算法图：在此插入图片描述示例代码：publicstaticvoidmain(String[]args){int[]num={7,4,9,3,2,1,8,6,5,10};longstartTime=System.currentTimeMillis();for(inti=1;i0&&temp
