前言
说到前面，我们已经详解了几种数据结构、包括数组、链表、二叉树、B树、B+树等基本数据结构、当然，我们这节课也叫做数据结构与算法、肯定会包含算法的相关知识、因为在之前已经了解和学习过有关时间复杂度的相关内容。当然也是和算法密切相关的。时间复杂度和空间复杂度共同决定一个算法的好坏、本节，我们将学习有关数组元素排序的几种常用算法。以及使用图画的方式展示出来。为了我们更好的理解与使用。
冒泡排序
听这个名字可以大概猜到。就像湖底水草上面的水泡一样，从水底到水面的一个过程。就是排序的其中一轮。我们来画图理解一下：
假设我们有这样一个长度的数组：需要将元素 顺序排列（从小到大）
指定一个本轮循环的元素j 与 j+1 元素 进行比较。若大于则换位。
这里明显 49>38 调换位置。
指针位移，再次开始与 i+1 个元素比较；
65>49 很显然，不进行换位。下移一位。
97>65 则不进行换位。位移下一位。
发现这里需要进行换位操作。因为97>76
位移下一位。
比较后，进行换位操作。
位移下一位。。。。这里省略步骤 到最后一步我们会发现
当指针到达(len-1)位置的时候，其实已经比较完了。所以我们通过这一轮的冒泡排序。一个最大的元素已经被确认出来了。
重复以上的过程，从第二个元素继续开始。再次重复这样的过程。实现排序。
下次的终止位置。则只需要比较到上一次位置-1处即可。
JAVA 代码示例。
第一版
int[] arrays = {49, 38, 65, 97, 76, 13, 27, 49};
public static void sort1(int[] arrays) {
int allChange = 0;
for (int i = 0;i<arrays.length;i++) {
for (int j = 0 ;j<arrays.length-i-1;j++) {
if (arrays[j] > arrays[j+1]) {
int temp = arrays[j];
arrays[j] = arrays[j+1];
arrays[j+1] = temp;
}
allChange++;
}
System.out.println(Arrays.toString(arrays));
}
System.out.println("总比较次数："+allChange);
}
第一版的冒泡排序通过两个FOR 循环的形式实现
外层 for循环用于控制整体程序的运行次数。也就是数组的长度。
内层 for用于与后面一位数比较大小。从而实现交换的逻辑。
如此一来，第一版冒泡排序的时间复杂度为
O(N的平方)
[38, 49, 65, 76, 13, 27, 49, 97]
[38, 49, 65, 13, 27, 49, 76, 97]
[38, 49, 13, 27, 49, 65, 76, 97]
[38, 13, 27, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
----------------------------------注意这段分隔符的意义
[13, 27, 38, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
总比较次数：28
第二版
通过观察控制台的输出，我们发现，其实在循环进行到第5次的时候，其实数组已经变得井然有序了。但是我们的算法仍然兢兢业业的做4次无用功。所以这里就是一个需要优化的地方。
通过加入一个isChange的变量。用来记录本次循环是否发生了变化。若没有发生元素的交换。则后面的循环直接跳出即可。
int[] arrays = {49, 38, 65, 97, 76, 13, 27, 49};
public static void sort2(int[] arrays) {
int allChange = 0;
for (int i = 0; i < arrays.length; i++) {
boolean isChange = true;
for (int j = 0; j < arrays.length - i - 1; j++) {
if (arrays[j] > arrays[j + 1]) {
int temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
isChange = false;
}
allChange++;
}
System.out.println(Arrays.toString(arrays));
if (isChange) {
break;
}
}
System.out.println("总比较次数："+allChange);
}
通过控制台输出的内容我们不难发现。其实循环在第五次的时候，已经完成了元素的交换，但是为何又输出了一遍？
[38, 49, 65, 76, 13, 27, 49, 97]
[38, 49, 65, 13, 27, 49, 76, 97]
[38, 49, 13, 27, 49, 65, 76, 97]
[38, 13, 27, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
--------------------------------
[13, 27, 38, 49, 49, 65, 76, 97]
其实在第四遍走完后，排序已经是完成了的。但是因为不知道下次时候会有元素的交换，所以在此走了一遍，因为没有交换元素，则在第五遍执行完毕后，跳出循环。
再次优化，有序长度的界定
何谓有序长度的界定呢？我们重新选择一个数组来打印一次，发现这里面需要优化的位置点。
选定一个特殊数组：[3,4,2,1,5,6,7,8]
通过短暂的观察，我们可以发现，5,6,7,8 这几位元素已经是处于一个有序的状态的。那么我们现有的算法，怎么去对于这些有序序列的比较。从而优化性能呢？我们先用这个数组来跑一遍
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
通过测试后发现，现有的算法对于数据的比较只需要三次即可排列好这个数组，但是我们会发现。在执行第一遍的时候，若遇到一些有序的元素。
例如：第一遍已经产生的 [4, 5, 6, 7, 8] 算法还是在第二遍执行的时候，重复进行了比较。我们能不能想个办法。跳过这些重复的内容呢？
我们可以控制内层比较的长度啊！！！
想要跳过一些元素的比较，那么就需要得到这个有序内容的长度。从而控制第二层循环，不要比较这些有序长度即可。
如何确定有序长度。
当然是若发生比较的时候，
public static void sort3(int[] array) {
//用来记录最后一次发生变化的位置
int lastChangeIndex = 0;
//用来表示需要比较的长度。只需要比较到之前即可
int sortLength = array.length - 1;
int allChange = 0;
for (int i = 0; i < array.length; i++) {
boolean isChange = true;
for (int j = 0;j< sortLength;j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
isChange = false;
//记录发生变化的位置
lastChangeIndex = j;
}
//用于记录比较次数
allChange++;
}
sortLength = lastChangeIndex;
System.out.println(Arrays.toString(array));
//若无改变则跳出循环
if (isChange) {
break;
}
}
System.out.println("总比较次数："+allChange);
}
最终我们得出，我们的算法只需要运行10次比较。即可排序完成。再来看看我们第二版本的算法次数
--------------------- 第三版
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
总比较次数：10
----------------------第二版
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
总比较次数：22
----------------------第一版
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
总比较次数：28
小结
通过一次一次的优化，使得我们的冒泡排序从最初的比较次数28，通过加入有无调换顺序的判断后 优化为22 再到记录有序序列的下标。变为更优化的10次。是算法优化的结果，也是我们在慢慢进步的效果。
下节课我们将学习到一个更加优化的排序算法。鸡尾酒排序