冒泡排序
1、思想 （以 从小到大排序 为例）
1.从数组下标0开始，两相邻元素依次比较，如果数组下标小者元素大于数组下标小者元素，两者进行交换。
2.每一轮确定一个最大值
3.需要进行（数组长度-1）轮排序
2、代码 （第一版）
import java.util.Arrays;
public class BubbleSort{
public static void main(String[] args) {
int [] a={3,9,-1,10,-2}; //例子
int k=0; //交换数据所需要的中间变量
for(int j=0;j<a.length-1-0;j++){
if(a[j]>a[j+1]){
k=a[j+1];
a[j+1]=a[j];
a[j]=k;
}
}
System.out.println("第一轮"+Arrays.toString(a));
for(int j=0;j<a.length-1-1;j++){
if(a[j]>a[j+1]){
k=a[j+1];
a[j+1]=a[j];
a[j]=k;
}
}
System.out.println("第二轮"+Arrays.toString(a));
for(int j=0;j<a.length-1-2;j++){
if(a[j]>a[j+1]){
k=a[j+1];
a[j+1]=a[j];
a[j]=k;
}
}
System.out.println("第三轮"+Arrays.toString(a));
for(int j=0;j<a.length-1-3;j++){
if(a[j]>a[j+1]){
k=a[j+1];
a[j+1]=a[j];
a[j]=k;
}
}
System.out.println("第四轮"+Arrays.toString(a));
}
}
结果：
第一轮[3, -1, 9, -2, 10]
第二轮[-1, 3, -2, 9, 10]
第三轮[-1, -2, 3, 9, 10]
第四轮[-2, -1, 3, 9, 10]
2、代码 （第二版）
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] a = {3, 9, -1, 10, -2}; //例子
int k = 0; //交换数据所需要的中间变量
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]) {
k = a[j + 1];
a[j + 1] = a[j];
a[j] = k;
}
}
System.out.println("第" + (i + 1) + "轮" + Arrays.toString(a));
}
}
}
结果:
第1轮[3, -1, 9, -2, 10]
第2轮[-1, 3, -2, 9, 10]
第3轮[-1, -2, 3, 9, 10]
第4轮[-2, -1, 3, 9, 10]
3、代码 （最终优化版）
在有些情况下：例如有数组 [1,2,3,4,5,6]，数组已经排好序，采用上面两种代码，都会执行 （数组长度-1）轮排序。这时，我们需要做出一些优化，对于已经排好序的数组，直接返回数组，不再进行（数组长度-1）轮排序，不在浪费不必要的时间。
思路：用一个标记(默认为false)。如果本轮循环，进行了数组元素的交换，就修改标记为true，进行下一轮循环。如果本轮循环，没有进行数组元素的交换，就不修改标记，说明此时，该数组已经排好序，直接结束返回数组。
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] a = {3, 9, -1, 10, -2};
sort(a);
}
public static void sort(int[] a) {
boolean flag = false;//是否进行了交换，默认为false
int k = 0;
for (int i = 0; i < a.length - 1; i++) {
flag = false; //每一轮排序后重置标记
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
k = a[j + 1];
a[j + 1] = a[j];
a[j] = k;
flag = true;
}
}
if (flag == false) { //如果本轮排序没有进行数据的交换，说明此数组已经有序，直接返回。
return;
}
System.out.println("第" + (i + 1) + "轮" + Arrays.toString(a));
}
return;
}
}
结果：
第1轮[3, -1, 9, -2, 10]
第2轮[-1, 3, -2, 9, 10]
第3轮[-1, -2, 3, 9, 10]
第4轮[-2, -1, 3, 9, 10]
