算法 | 作为开发竟然不懂算法 - 冒泡排序

vlambda
2021-06-09

算法 | 作为开发竟然不懂算法 - 冒泡排序

关注 ▲程序员漫话编程▲ 看漫画，学编程。

编者荐语：

大家好，我是你们的朋友朋哥.

说起算法其实大家都知道重要，但是真正理解算法需要在实际开发中使用。

最近开始做算法的有关东西，发现一些不太重视的算法，其实是所有算法逻辑的基础。

很多复杂和庞大的逻辑都是这些小小的算法堆积起来的。

比如我最近就遇到很多使用冒泡排序，今天分享给大家。

有问题请留言。

简介

基本思想：比较前后相邻的两个数据，如果前面数据大于后面的数据，就将这二个数据交换。这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第 N-1 个位置。N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。

场景：数据量不大，对稳定性有要求，且数据基本有序的情况。

步骤：

1、比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。

3、针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。

4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。

复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：所以，冒泡排序最好的时间复杂度为

O(n)

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值:

冒泡排序的最坏时间复杂度为

O(n^2)

综上，因此冒泡排序总的平均时间复杂度为

O(n^2)

空间复杂度为

O(1)

核心代码示例：

 
   
   
 
  
    
    
   
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  
  
    
    
  public static void ArraySortTest() { int[] ages= {20,22,30,15,50,12,16,45}; System.out.println(Arrays.toString(ages)); //控制比较轮数 for(int i=1;i<ages.length;i++) { //每轮比较多少 for(int j=0;j<ages.length-i;j++) { if(ages[j]>ages[j+1]) { int tmp=0; tmp=ages[j]; ages[j]=ages[j+1]; ages[j+1]=tmp;  } } } System.out.println(Arrays.toString(ages));}