冒泡排序算法
2021-05-10 本文已影响0人
想象之中丶意料之外
冒泡排序算法原理
比较两个相邻的元素，将值大的元素交换到右边。然后再剩下的数中，再找最大数，再交换到剩余数的最右边。此时形成了一种冒泡，每次把剩余数中最大的数，冒泡到剩余数中最右边。
思路：
步骤1：比较数组0和1位的数，将小数放在前面，将大数放在后面【大小交换位置】。
步骤2：比较数组1和2位的数，将小数 放在前面，大数放在后面。
......
重复此步骤，就会将最大的数，放到最右边【数组最后1位】。
- 再将数组剩下数字，按照上述步骤，再找到剩下数中最大的数，放在数组剩余数中的最右边。【即：数组倒数第二位位置，数组倒数第一位，已经有第一次的最大数了】
- 以此类推
举例：数组：[3, 7, 2, 4] 冒泡排序
- 第一次找最大的数：
3,7,2,4【比较数组0与1位数，3小于7，不换位。结果：3,7,2,4】
3,7,2,4【比较数组1和2位数，7大于2，换位。结果：3,2,7,4）】
3,2,7,4【比较数组2和3位数，7大于4，换位。结果：3,2,4,7）】
第一次找完，找出了最大数7
- 第二次
第一次最终结果：3,2,4,7
接着比较除最大数7之外的数字【3,2,4】即可：
3,2,4【比较数组0与1位数，3大于2，换位。结果：2,3,4】
2,3,4【比较数组1与2位数，3小于4，不换位。结果：2,3,4】
第二次找到剩余数【3,2,4】中最大的数4
- 第三次比较
第二次比较结果：2,3,4
接着比较除7&4之外的数字【2,3】即可：
2,3【比较数组0与1位数，2小于3，不换位。结果：2,3】
- 对比结束，最终排序出来。
注：每次比较都找到了剩余数中最大的数。所以再下一次的比较中，不需要将上次的最大数再进行比较。故每次比较时，内部数字比较次数，都会减1.
规律
从上述例子中，发现一个规律：
- 说明一下：数组外部循环，我们是为了找到剩余数字的最大数，内部循环是为了将每次最大数与下一个数进行换位。
- 1、数组外部找剩余最大数字循环次数是：数组长度-1【例子中，数组长度4，只比较了3次】
- 2、数组内部换位次数是：数组外部剩余最大数字循环次数-1【第一次剩余4个，循环3次。第二次剩余3个，循环2次，...】
java代码
int[] a = {3,7,2,4};
for(int i = a.length - 1; i > 0; i--) {
// 这里通过 i 从数组长度往下减的方式，来实现所说的规律2
/*
* 比如：i = 3，那么 j循环就是 0、1、2（完成3次循环）
* i = 2，那么 j循环就是 0、2（完成2次循环）
* ....
*/
for(int j = 0; j < i; j++) {
// 换位逻辑
// 这里不用考虑 数组越界异常，因为j从0开始，且小于i，导致不可能出现越界异常。
if(a[j] > a[j + 1]) {
int tmp = a[j]; // 大的数，先找个地方存一下。
a[j] = a[j + 1]; // 将小的数字，转到当前位置。
a[j + 1] = tmp; // 将大的数字，转到下个位置。
}
}
}
