HTML5学派-Coder:本期继续进入算法-冒泡排序。冒泡排序算法比较简单,使用方便,稳定性也比较高。它是一个很好理解的算法,也是面试官经常问的算法之一。Tips:关于“算法”和“排序”的基础知识,在前面的“选择排序法”中已经详细讲解过了。冒泡排序法的原理基本原理是从序列的头部开始遍历,两两比较。如果前者大于后者,则交换位置,直到最大的数(本次排序中最大的数)交换到最后的无序序列。尾巴,从而成为有序序列的一部分;下一次遍历时,前一次遍历后的最大数不再参与排序;多次重复此操作,直到序列排序完成。因为在排序的过程中,总是小数点往前,大数往后放,类似于气泡逐渐往上飘,所以叫冒泡排序。示意图提示:蓝色表示在一轮排序中等待交换,黑色表示本轮排序中交换已经完成,红色表示排序已经完成步骤分解实现冒泡使用for循环来确定排序的个数因为只有当待排序的数列还剩可以确定下一个数的顺序时,就不需要排序了。因此,排序的次数为序列长度-1。每次排序的比较次数控制每次排序。序列中的多个数字需要成对比较。多重比较需要使用for语句来实现。for循环嵌套在排序次数的for循环中(形成一个doublefor的嵌套)。Tips:j需要设置为小于len-i-1,减去i的原因是已经排序的数不再参与比较。之所以要减1,是因为数组下标的索引值是从0开始的。核心功能——比较两个数,根据情况交换位置,比较两个数的大小。如果前者大于后者,则交换值,即交换位置。冒泡排序法完整代码冒泡排序法优化如果序列的数据为:[0,1,2,3,4,5];用上面的冒泡排序方式排序,结果肯定没问题,但是,待排序的序列是有序的,理论上不需要遍历排序。目前的算法不管初始序列是否有序都会进行遍历排序,效率会比较低。因此,目前的排序算法需要优化。在下面的算法中,引入了一个swap变量,在每次排序前都初始化为false;如果交换了两个数字,则将其设置为true。每次排序结束时,判断swap是否为false。如果是,则说明该序列已经排好序或者该序列本身就是一个有序序列,不进行下一次排序。通过这种方法,减少了不必要的比较和位置交换,进一步提高了算法的性能。冒泡排序法效率和时间复杂度的最佳状态:待排序序列本身就是有序序列,根据优化代码可以得出排序次数为n-1次,时间复杂度为在);坏情况:要排序的序列是倒序的。这时候需要排序1+2+3...(n-1)=n(n-1)/2次,时间复杂度为O(n^2)。空间复杂度冒泡排序方法需要额外的空间(temp变量)来交换元素的位置,所以空间复杂度为O(1)。算法的稳定性当相邻元素相等时,不需要交换位置,相同元素的顺序不会发生变化,因此是一种稳定排序。欧是什么?!时间复杂度,更准确地说,描述了算法随着问题规模的增加而增长的曲线。因此,这些数量级的增长并不是一个准确的性能评估,可以理解为一个近似值。(空间复杂度也是如此)O(n2)表示当n很大时,复杂度约等于Cn2,C为常数。简单地说,当n足够大时,复杂度会随着n线性增加而增加。正方形生长。O(n)表示当n很大时,复杂度约等于Cn,C是某个常数。简而言之:随着n线性增长,复杂度也沿着线性水平增长。O(1)表示当n很大时,复杂度基本不会增加。简而言之:随着n线性增长,复杂度与n无关,沿着一个恒定的水平(这里的常数是1)。Tips:图中的O(1)靠近X轴,看不清楚。Tips:本图来自“StackOverflow”网站。相关文章链接算法之旅|SelectionSortMethodHappy生活辛苦,代码不易,但别忘了微笑!版权声明:本图来自《【美国】LizCremer(作者)》一书《你今天真好看》
