亲宝软件园·资讯

展开

数据结构与算法系列十一(冒泡排序)

小杨【0和1】 人气:0

1.引子

1.1.为什么要学习数据结构与算法?

有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!

有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?

于是问题来了:为什么还要学习数据结构与算法呢?

#理由一:
    面试的时候,千万不要被数据结构与算法拖了后腿
#理由二:
    你真的愿意做一辈子CRUD Boy吗
#理由三:
    不想写出开源框架,中间件的工程师,不是好厨子

1.2.如何系统化学习数据结构与算法?

我想好了,还是需要学习数据结构与算法。但是我有两个困惑:

1.如何着手学习呢?

2.有哪些内容要学习呢?

学习方法推荐:

#学习方法
1.从基础开始,系统化学习
2.多动手,每一种数据结构与算法,都自己用代码实现出来
3.思路更重要:理解实现思想,不要背代码
4.与日常开发结合,对应应用场景

学习内容推荐:

数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法

#学习内容:
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
    数组、链表、栈、队列
    散列表、二叉树、堆
    跳表、图
5.常用算法
    递归、排序、二分查找
    搜索、哈希、贪心、分治
    动态规划、字符串匹配

2.考考你

在上一篇:数据结构与算法系列十(排序概述)中,我们列举了常用的排序算法,以及分析了如何综合衡量排序算法的优劣。如果你还没有看上一篇的内容,可以去看一看,应该会有所收获。

从这一篇开始,我们把每一种排序算法,从算法的思想,到代码实现都做一个分享。那么你准备好了吗?

我们这一篇的主角是:冒泡排序

#考考你:
1.你知道冒泡排序的核心思想吗?
2.你能用java实现冒泡排序吗?
3.你能写出更优秀的冒泡排序代码吗?

 

3.案例

3.1.冒泡排序思想

假设有一个待排序序列:[4, 5, 6, 3, 2, 1]。我们需要按照升序进行排序,排序后的序列是这样的:[1, 2, 3, 4, 5, 6]。

如何通过冒泡排序实现呢?

这里我们先来理解冒泡排序中的冒泡两个字。所谓冒泡就像平静的水面,鱼儿从水底吹气一样,一个一个的水泡向上冒,很诗情画意,我们都向往这样的生活环境对吧。

那么请保持这个美好的姿势,我们一起来理解冒泡排序的思想,先看一个图:

 

 

 

冒泡排序核心思想:

假设待排序序列有n个元素,需要经过n次冒泡,每一次冒泡过程中依次比较交换相邻的两个元素,一次冒泡结束,都会有1个元素到达指定的目标位置。这里的关键词有:

1.n个元素,n次冒泡
2.比较交换相邻元素

3.2.冒泡排序代码实现

3.2.1.排序代码

/**
* 冒泡排序:普通实现版本
* @param array:待排序数组
* @param n:待排序数组大小
*/
public static void sort_1(Integer [] array,int n){
  // 如果排序数组规模小于等于1,直接返回
  if(n <= 1){
    return;
  }

  // 有n个元素,进行n次冒泡
  for(int i = 0; i < n; i++){

    // 每一次冒泡,比较交换相邻两个元素
    for(int j = 0; j < n-i-1; j++){
       if(array[j] > array[j+1]){
         int tmp = array[j];
         array[j] = array[j+1];
         array[j+1] = tmp;
        }
      }
    }

}

3.2.2.测试代码

public static void main(String[] args) {
 // 初始化测试数组
 Integer[] array = {4,5,6,3,2,1};
 // 排序前
 System.out.println("1.排序前数组:" + Arrays.deepToString(array));

 // 排序后
 sort_1(array,array.length);

 // 排序后
 System.out.println("2.排序后数组:" + Arrays.deepToString(array));

}

测试结果:

D:\02teach\01soft\jdk8\bin\java 
com.anan.algorithm.sort.BubbleSort
1.排序前数组:[4, 5, 6, 3, 2, 1]
2.排序后数组:[1, 2, 3, 4, 5, 6]

Process finished with exit code 0

3.3.冒泡排序实现优化

3.3.1.优化分析

在3.2.1节冒泡排序普通实现版本,我们严格按照冒泡排序的思想:n个元素、n次冒泡,每一次冒泡依次比较交换相邻元素。实现了一个冒泡排序。

在这里,请你先简单思考一下:有没有更优化的实现方式呢?

我们先来分析一下冒泡排序算法的时间复杂度,结合代码我们发现冒泡排序的时间复杂度是:O(n^2),有两次for循环,这不是一个高效的算法对吧。如果说我们能够减少冒泡的次数,则可以极大提升算法的执行效率。

问题来了:什么情况下可以减少冒泡次数呢?

其实我们只要结合冒泡排序算法的核心思想后半部分:比较交换相邻的元素。如果说在一次冒泡中,没有发生相邻元素的交换,那说明待排序序列已经有序了,不管后面还剩下多少次冒泡,我们都不需要再进行冒泡下去了。这样是不是就减少冒泡的次数了呢

关于减少冒泡次数的分析,如果你暂时没有理解过来的话,没有关系。请看我们下面的代码实现,相信结合代码你会恍然大悟。

3.3.2.优化代码实现

/**
* 冒泡排序:优化实现版本
* @param array:待排序数组
* @param n:待排序数组大小
*/
public static void sort_2(Integer [] array,int n){
  // 如果排序数组规模小于等于1,直接返回
  if(n <= 1){
     return;
  }

  // 优化标识
  // 如果某一次冒泡过程中,没有发生数据交换
  // 则说明已经排好了序,不需要在继续冒泡
  boolean flag = false;

  // n个元素,n次冒泡
  for(int i = 0; i < n; i++){
            
    // 重置是否发生交换标识
    flag = false;
            
    // 每一次冒泡中,比较交换相邻元素
    for(int j = 0; j < n-i-1; j++){
      if(array[j] > array[j+1]){
         int tmp = array[j];
         array[j] = array[j+1];
         array[j+1] = tmp;

         // 发生了数据交换
         flag = true;
        }
      }

     // 一次冒泡结束,检查是否发生了数据交换
     // 如果没有发生数据交换,说明序列已经有序,不需要再继续冒泡了
     System.out.println("第【" + (i+1) + "】次冒泡.");
     if( !flag){
        break;
      }

    }

}

3.3.3.测试代码

public static void main(String[] args) {
 // 初始化测试数组
 Integer[] array = {4,5,6,3,2,1};
 // 排序前
 System.out.println("1.排序前数组:" + Arrays.deepToString(array));

 // 第一次排序
 System.out.println("2.第一次排序-------------------------------start");
 sort_2(array,array.length);
 System.out.println("3.第一次排序后数组:" + Arrays.deepToString(array));

 // 第二次排序
 System.out.println("4.第二次排序-------------------------------start");
 sort_2(array,array.length);
 System.out.println("5.第二次排序后数组:" + Arrays.deepToString(array));

}

测试结果:

 

 

4.讨论分享

#考考你答案:
1.你知道冒泡排序的核心思想吗?
  1.1.假设待排序序列有n个元素
  1.2.整个排序过程中,需要n次冒泡
  1.3.每一次冒泡过程中,依次比较交换相邻两个元素
  1.4.一次冒泡结束,都会有一个元素到达指定的位置
  
2.你能用java实现冒泡排序吗?
  2.1.参考【3.2】节案例实现
  
3.你能写出更优秀的冒泡排序代码吗?
  3.1.结合冒泡排序算法的核心思想:n个元素、n次冒泡,每一次冒泡依次比较交换相邻的两个元素
  3.2.如果在某一次冒泡中,没有发生元素交换
  3.3.说明待排序序列已经有序,不需要再进行冒泡下去

 

加载全部内容

相关教程
猜你喜欢
用户评论