数据结构与算法系列十一（冒泡排序）
小杨【0和1】 人气:01.引子
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.说明待排序序列已经有序，不需要再进行冒泡下去
加载全部内容