冒泡排序和简单选择排序比较（冒泡排序和简单选择排序本质一样）

冒泡排序

概述

冒泡排序应该是我们第一个学习的排序算法。其简单也不难理解它的排序过程就像是冒泡一样，每一次都将最大的数冒上来，然后冒第二大，以此类推冒 n-1 次就可以得到序列的排序了。

冒泡排序的时间复杂度是 O(n2)的，但是可以优化并不一定是 O(n2)的在等会会详细介绍。

接下来我们来学习一下所谓的冒泡排序吧。

排序过程

宏观认知

可以将所需要排列的序列 q 分为两个序列，一个是未排序好的序列，一个是已经排序好的序列。如何理解呢？

一开始序列 q 中所有的数都是为排序的因此这个时候所有的数都是存在为排序的序列中，而已排序的序列中是 0 个元素。这个不难理解。

那么会进行 n-1 次迭代（为什么是 n-1 次？后面慢慢看）。每一次迭代都可以确定一个元素的排序，将其加到已经排序好的序列中。这个时候已经排序好的序列中有一个元素，而另一个序列是 n-1 个元素：

第一次迭代

同样的第二次迭代：会从未确定的排序序列中再次选取一个最大值，将其加到已经排好的序列中

第二次迭代

以此类推知道迭代 n-1次之后：

n-1 次迭代

可以发现只剩下最后一个元素了，因此不用在迭代选择最大元素了，这个元素就是未确定排序中最大的元素，整个序列中最小的元素。所以这就是为什么只迭代 n-1 次的原因。

那么这个排序过程应该就很清楚了总结一下：

将整个序列分为两个序列，还未确定排序的序列，和已经排序好的序列 前半部分为未排序的序列，后半部分为已排序的序列。 进行 n-1 次迭代 每次迭代都从未确定的序列中选取最大的值放到排序好的序列当中

当然这个是从宏观上的认识，还要来讨论每次是如何从未确定排序的序列中选取最大值呢？

遍历未确定排序的序列

从小到大遍历未确定排序的序列 如果后一个数比当前数小就进行交换

最后当这样遍历一遍之后就会将这个序列中的最大值放到这个序列的最后一个位置。最后将这个位置的数划分为已经确定好的序列中就可以了。

那如何去维护有序序列和无序序列呢？

其实这两个序列都是存放在原本的序列中，只是序列的右边是有序的，左边是无序的，有序序列的个数跟迭代的次数是一致的，原因是因为每次迭代可以确定一个数的顺序。因此通过遍历的变量就可以维护这两个序列的分界线了。只要遍历的时候不超过这个分界线就可以了。

每次迭代完都会将选出的最大值放在最后一个位置，而只要将这个分界线往前移动一个位置就可以将这个值划分到右边的有序序列中了。

结合下面的动图进行理解

冒泡排序

ps：图片来源于网络

排序过程总结

因此现在整个排序过程就很清楚了，进行 n-1 次迭代，每次迭代中要进行遍历，从未排序的序列中选取最大值放到最后一个位置。进行玩 n-1 次迭代后，就按从大到小的顺序选出了 n-1 个最大的数，最后一个数就是最小的数，因此就得到了一个有序的序列。

代码实现：

void bubble(int[] arr){ int n = arr.length; // 进行 n-1 次迭代 for(int i = 0; i < n-1; i++){ // 将未确定排序的序列中的最大值移动到最后一位 for(int j = 0; j < n-i-1; j++){ // 如果后一个数比当前数小，就交换往后移动一位 if(arr[j] > arr[j+1]){ int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t; } } } }

优化代码：

void bubble(int[] arr){ int n = arr.length; for(int i = 0; i < n-1; i++){ // 标记 boolean flag = false; for(int j = 0; j < n-i-1; j++){ if(arr[j] > arr[j+1]){ int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t; // 如果有交换说明还存在逆序对 flag = true; } } // 如果标记没有被改变，说明没有进行交换 if(!flag)break; } }

优化思路：每一次迭代的时候都使用一个标记变量。如果当前迭代一次交换都没有发生的话，是可以说明这个序列都是有序的因此就不需要后面的迭代了。可以提前退出。

这个是有一个特点的：一个有序的序列是不存在逆序对的。所谓的逆序对就是一个序列中有两个数前面一个数比后面一个数大，就称这两个数为逆序对。

而冒泡排序中的每一次相邻两个元素的之间的交换是会严格减少一个逆序对的。当序列中一个逆序对都没有的时候就说明这个序列已经是有序的了。因此可以提前退出

复杂度分析

时间复杂度

在上面的过程中可以发现，要进行 n-1 次迭代，而每次迭代中又要进行遍历，第一次迭代遍历需要进行 n-1 次，第二次需要进行 n-2 次依次类推

n-1 + n-2 + n-3 .... n-(n-1) + n-n = n2-（1 + n）*n/2 = n2/2 - 1/2

因此时间复杂度为O(n2)最坏的情况,最好的情况是 O(n)的，也就是刚才我们优化的那种情况，如果一开始序列本来就是有序的，那么我们只要迭代第一次也就是扫描 n-1次，即判断是一个有序序列，从而 break 出来。

因此冒泡排序的时间复杂度最坏是 O(n2)而最好的情况是 O(n)

空间复杂度

空间复杂度是针对使用的辅助空间而言的，因此存储序列的空间不能计算进去，因此使用的辅助空间只有几个变量，因此空间复杂度是O(1)的。

稳定性分析

首先说明的是稳定性并不是值算法时间复杂度是否稳定，而是值如果序列中存在相同的两个数，排序前跟排序后他们的相对位置是否会发生改变。

通过上面的过程中可以发现冒泡排序是通过交换相邻两数进行排序的。如果两数相等就没必要进行交换了，因此冒泡排序是可以称为稳定排序的。

但是稳定与否跟具体的实现有关，因为两数相等因此即使两个数进行交换也不会应该结果，如果算法实现的时候判断条件改为相等的时候也交换的话，那么这个时候冒泡排序就不是稳定的了。

例如if(arr[j] > arr[j+1]) 这样判断就是稳定的，如果是if(arr[j] >= arr[j+1]) 这样判断就是不稳定的。