读书笔记——冒泡排序
什么是冒泡排序？
最近开始重学算法。先从最简的冒泡排序开始。这里做个笔记方便后面复习。
对于冒泡排序算法的定义，相对于其他资料，百度百科里的介绍相对详细一点——冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
结论——冒泡排序它通过交换数据元素的位置进行排序，是一种典型的交换排序算法。
算法步骤
比较相邻两个元素的大小，如果第一个比第二个大，交换他们的位置。
向下顺移，对每一对元素做第1步的操作，直到末尾。至此最大的数会被挪动到末尾。
回到开始位置，重复步骤1、步骤2。（注意排除末尾的那个数，因为它的位置已经确定，是“有序”的）
持续对越来越少的元素重复步骤1、步骤2、步骤3，直到没有数字需要比较
尝试实现
假设我们现在有一个数组，这里以Java代码为例：
int[] array = {14, 12, 1, 15, 13};
//测试代码为
public static void main(String[] args) {
int[] array = {14, 12, 1, 15, 13};
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
实现步骤1
public static void bubbleSort(int[] array) {
if(array[0] > array[1]){
int temp = array[0];
array[0] = array[1];
array[1] = temp;
}
}
//运行结果为：
[12, 14, 1, 15, 13]
//这里发现比较后元素12和14发生交换实现步骤2
步骤2是因为要往后开始比较，所以考虑用for循环。初步实现如下
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}这里有个问题，开始下标i是从0开始，和它相邻的元素下标为i+1。当i遍历到末尾数组的最后一个元素时再用array[i+1]肯定会出现数据越界问题java.lang.ArrayIndexOutOfBoundsException。所以修改后步骤2的实现如下：
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
//运行结果为：
[12, 1, 14, 13, 15]
//这时最大元素15已经挪动到了末尾步骤3
重复一次，相当于遍历数组第二趟
public static void bubbleSort(int[] array) {
//第一趟
for (int i = 0; i < array.length - 1; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
//第一次重复，也就是第二趟遍历。应为第一趟末尾数字已经遍历ok变得有序
//所以这一次i的最大值要减1
for (int i = 0; i < array.length - 1 - 1; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
//第2次重复，也就是第3趟遍历。应为第2趟末尾2个数字已经遍历ok变得有序
//所以此次i的最大值要在上一次的基础上再减1
for (int i = 0; i < array.length - 1 - 2; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}步骤4
这里我们发现测试数组总共有5个item，也就是说遍历5趟就能完成数组的冒泡排序动作。
但是因为到最后一趟时只剩一个数，也就不需要进行遍历排序了。
所以最终4趟遍历就能完成此次冒泡排序
public static void bubbleSort(int[] array) {
//第一趟
for (int i = 0; i < array.length - 1; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
//第一次重复，也就是第二趟遍历。应为第一趟末尾数字已经遍历ok变得有序
//所以这一次i的最大值要减1
for (int i = 0; i < array.length - 1 - 1; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
//第2次重复，也就是第3趟遍历。应为第2趟末尾2个数字已经遍历ok变得有序
//所以此次i的最大值要在上一次的基础上再减1
for (int i = 0; i < array.length - 1 - 2; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
//第四趟
for (int i = 0; i < array.length - 1 - 3; i++) {
//步骤1，比较和交换位置
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
//运行结果如下：
[1, 12, 13, 14, 15]
//符合预期
因为每次需要排序的数组长度是不固定，我们不可能每次都先提前算好需要排序数据的长度N，然后在代码中重复写N-1趟遍历代码。所以上面的代码可以合并优化为如下代码：
public static void bubbleSort(int[] array) {
//本行for循环表示需要遍历的趟数
for (int i = 0; i < array.length -1 ; i++) {
//这里的第二个for循环表示的是每次需要遍历多个数，第i趟需要遍历length-i个
//或者说换种说法，表示的是每趟比较的次数，第i趟比较len-i次
for (int j = 0; j < array.length - 1 - i; j++) {
//步骤1，比较和交换位置；升序为左大于右，降序的话反着来即可
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
算法分析
时间复杂度
最好情况
最好情况就是数组已经是一个排好序的数组，一趟遍历即可完成。算法复杂度为O(n)
最坏情况
最坏情况就是队列逆序排列，需要N-1趟进行排序。并且呢每次要进行N-i次的比较才能完成。
i的取值为1<=i<=N-1。时间复杂度O(n^2)
平均情况
数组乱序排列时，数组的平均复杂度为O(n^2)
空间复杂度
因为交换的时候需要一个额外的空间来辅助完成元素交换动作。所以空间复杂度为O(1)
算法的稳定性
冒泡排序算法两个相邻元素比较时如果相等是不会发生交换动作的。如果两个相等的元素没有相邻，那么即使通过前面的交换，让两个元素相邻起来也不会交换。因此相同元素的前后顺序并没有改变。结论——冒泡排序是一种稳定排序算法
注：
算法稳定性指的是在一组待排序记录中，如果存在任意两个相等的记录R和S，且在待排序记录中R在S前，如果在排序后R依然在S前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的。