|
排序算法有很多种，冒泡算是其中最简单的一种，之所以叫冒泡，是因为每一次循环结束，都有一个数（最大或最小）被选择出来，就跟冒泡冒出来一样，所以叫冒泡排序。
冒泡排序需要两个for循环嵌套执行，外层的for循环代表一轮，内层的for循环代表每一轮比较的次数
冒泡排序的原理就是对相邻的每个数进行一个对比，按照升序的话，如果第一个数比第二个数大，那么这两个数交换位置，然后再进行第二个数与第三个数的比对，注意，这里的第二个数其实就是应该交换过的，原来的第一个数，如果前面的数比后面的数大，则两者交换位置，如果不比前面的大，就继续对比下一组相邻的两个数。直到所有的数对比完，此有一轮对比结束，每一轮对比结束都会把最大的数排序出来，在最右边，如果是按照降序排序的话，最右边就是最小的数。一轮结束，再进行第二轮，第二轮将会冒泡出第二大的数出来，以此类推，知道循环完所有的轮数，则排序完成
举个例子，假如现在有5个数，目前的顺序是 5、7、3、4、1，我们按照升序来排序。
第一轮开始：5跟7对比，5<7，位置不变，对比7跟3，7>3，则7与3互换位置，此时顺序为5、3、7、4、1，7跟3已经交换了位置，后面还有4跟1还没对比，继续对比，7>4，交换位置，再对比7跟1，7>1，交换位置，1已经是最后一个数，已经对比完了，说明一轮结束，一轮结束后，此时这几个数的顺序将变成 5、3、4、1、7，此时可以看到7已经冒泡出来了，它是最大的数，目前排在最右边。
第二轮：注意第二轮是在第一轮排序后的基础上再进行排序的，也就是此时的数列是 5、3、4、1、7。 再次按照第一轮的方法对比相邻的两个数，第二轮5将会冒泡出来，第二轮之后数列变成为3、4、1、5、7.
第三轮：4将被冒泡出来，数列变为3、1、4、5、7
第四轮：3将被冒泡出来，数列变为1、3、4、5、7。
可以看到，5个数，经过4轮对比，已经实现从大到小的顺序排列好了。5个数，经过4轮，那N个数，就是N-1轮。
再看每一轮要对比多少次，第一轮5个数对比了4次，第二轮4个数对比了3次（因为最大已经冒泡出来了，无需再对比），第三轮3个数对比了2次，第四轮2个数对比了1次，以此类推，N个数对比，需要N-1轮，每一轮需要对比N-1次。
下面是代码实现：
int[] array = {18,13,50,15,4,17,18};
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j]; //temp为临时变量，用于临时存储
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
|