谈一谈冒泡排序

看到很多人谈算法题，上来就是一段代码，你去看去吧，自己悟去吧。

心塞有的题目老长时间就是不理解。。。

本文分析一下啥是冒泡排序？排序就是一组数字，按照顺序排列（从小到大） ，冒泡排序是排序的一个方法：

1. 从给定的一组数头部开始，前一个数和后一个数进行两两比较，数字大的移动到后面去，一直比较到数组尾部，最大的数会移动到尾部。

2. 循环上述操作，直到这一组数按照从小到大的顺序排列。

聊一聊赋值操作

数据的赋值操作是一件很有意思的事情？下面来看这样的代码：

int a = 2

很简单的一个赋值操作 ，代码的意思就是把 2 这个数赋值给 a , 现在我们来看等于号（=）的两边，左边是 a , 右边是数值，左边是这个数的引用，右边是引用（也叫指针）指向的一个确切的数字：

赋值操作可以这样理解就是引用（指针）指向一个确切的数字或者这个数字被等于号左边的指针所拥有。

int a,b;
a = 1;
b = 2
a = b;
b = a;

请问以上的五行代码中 a 等于？ b 等于？第二行代码a = 1 表示 1 的指针是 a 即 a → 1; 第三行代码表示 2 的指针是 b 即 b → 2 ;

第四行是很有意思的代码 a = b，很多人刷算法的时候经常容易在这里搞得晕头转向，尤其是引用很多的时候（ a ,b ,c ,d …..),它等于它，它又等于它。。。。，其实我们不用想太多，我们只要这要考虑就好：

赋值操作等于号左边是引用，右边是数值；

尽管 a 和 b 都是引用，但 a = b 的操作是把 b 的值 2 赋值给 a 仅此而已，结果是 a → 2，b 的引用没有发生改变依然是 b → 2。

第五行代码依然如此, a 代表的数值是 2 ，赋值给 b 即 b → 2, a 依然是 a → 2;

聊一聊两个变量的数值交换

有了前面的讲解，下面我们再来看看两个变量之间的交换：

int a, b;
a = 1;
b = 1;
a = b;
b = a;

请问以上的代码可以完成两个数字的交换吗？答案是否定的，原因可以参考上面的分析；

如果要实现两个变量的数值交换需要借助第三方变量去存储一方的数值。

看似很简单的道理，但是这一点却有人总也想不通？

int a, b, temp;
a = 1;
b = 2;
temp = a;
a = b;
b = temp;

把最大的值放在后面

下面我们来解决这样的一个问题：给你一组数（即数组 a)，怎么把最大的一个数移动到最后面呢？

从头开始两两比较，直到比较到最后一位，如上图所示，上面如何用代码展示呢？

解决两数据交换的问题,参考上面谈到的数据交换循环操作，直到比较到最后一位数循环终止

该问题的难点就是如何控制循环的次数，思路转换成代码：

for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}

这里有一个难点可能就是这个 for 循环应该怎么去控制，何时应该终止 for 循环？这里面存在当前数同它后一个数的比较，即 if(a[i]>a[i+1]) 当 a[i] 是最后一个数的时候存在着 a[i+1]数组越界的问题。

因此循环的次数应该是数组的长度减少 1 即 a.length - 1 ，使用 for (int i = 0; i < a.length - 1; i++) 循环可以把最大的数移动到数组的最后面。

不断循环把最大的值放在后面

上面的一个问题是：给你一组数（即数组 a)，怎么把最大的一个数移动到最后面呢？那么把问题进行拓展，怎么使用该方法进行数组的一个排序呢？

把最大的一个数移动到后面循环操作第一步，这样也就完成了排序操作

以上两点也就是冒泡排序算法，这里的难点就是怎么控制循环次数,循环次数整明白了，冒泡排序也就搞定了：

for (int i = 0; i < a.length-1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if(a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j+1] = temp;
}
}
}

下面重点分析一下循环次数的问题：

分析一下外层 for 循环

经过前面的讨论，我们可以把最大的数移动到最后面，需要移动多少次可以把数组完成排序呢？第一轮：最大的数排在最后面，搞定 1 个第二轮：次大的数排在倒数第二的位置，搞定 2 个。。。。依次进行，每进行一轮，筛选出一个大的数出来，也就是大的数往后移动的过程。这个过程从数组的后面往头部看，也就是一个从大到小的过程。由此可知： 循环 a.length-1 即数组的总长度减 1 就可以完成排序了，这样也就确定了外层循环： for (int i = 0; i < a.length-1; i++)

分析一下内层 for 循环

先看看前面讨论把最大的数移动到最后面的代码：

for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
int temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}

这段代码循环了 a.length -1 即数组的长度减 1 次，问题来了，外循环每循环一次是可以搞定一次大数后移的过程的，内存的 for 循环还有必要每次循环到 i< a.length-1 吗？答案是否定的。

外循环每处理一次，内循环范围缩小一次，这样也就有了前面提供的内存 for 循环for (int j = 0; j < a.length - 1 - i; j++) 这里的 a.length - 1 - i就是在缩小循环的范围，每次外循环一次，就相应减小内循环的次数。

循环一般用 for 和 while

上面基本把冒泡排序给讨论完了，现在我们来讨论一下循环次数的问题，在计算机的循环语句当中，循环通常使用 for 循环和 while 循环，循环的问题都可以通过这两种循环去解决的，解题的难点就是边界的控制，从什么时候开始，什么时候跳出循环体。

给你一组数（即数组 a)，怎么把最大的一个数移动到最后面呢？请使用 while 循环实现。

int i = 0;
while(i < a.length - 1){
if (a[i] > a[i + 1]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
i++;
}

这里的循环判断条件是 i < a.length - 1 每次循环一次执行 i++;

for 循环和 while 循环是解决循环问题常用的手段，你更倾向用哪种方式解决循环问题呢？

while 循环实现冒泡排序

你可以使用 while 循环解决冒泡排序的问题吗？

int i=0,temp=0;
while (i < a.length -1) {
int j = 0;
while(j <a.length-1-i){
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
j++;
}
i ++;
}

具体分析可以参考 for 循环的冒泡排序。