【算法基础】冒泡排序

时间:2021-05-29 11:05:54

从数列第一个数字开始,与相邻的后一位数字比较,如果前一位数字比后一位大,则置换它们的位置,一轮下来排到最后的是最大的数字,直到数列完全有序。

要点:
1. 每轮排序最大的数字会被置换到最后,下一轮就不需要再对比这个数字了。因此第一轮需要对比N-1次,第二轮需要N-2次,第X轮只需要对比N-X次。
2. 如果数列在对比到中途某一轮时已经有序,那么即可终止排序了(提高效率)

实现:

static void bubbleSort(int[] array) {
//标志位,如果该轮没有元素交换,那么代表数组已经有序,可以停止对比。
boolean isSwap = false;

for (int i = array.length - 1; i >= 0; i--) {
int a = array[0];
System.out.println("round:" + i);
for (int k = 1; k <= i; k++) {
if (a > array[k]) {//相邻两位对比
int tmp = array[k];
array[k] = array[k - 1];
array[k - 1] = tmp;
isSwap = true;
}
a = array[k];
}
if (!isSwap) //本轮没有交换位置,说明数列已经有序
break;
}
}