排序算法之冒泡排序！

核心思路：

依次比较相邻的两个数，将小数放在前面，大数放在后面。

第一趟：

首先比较第1个和第2个数，将小数放前，大数放后。

然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。

至此第一趟结束，将最大的数放到了最后。

第二趟：

仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数）。

将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的）。

第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。

如此下去，重复以上过程，直至最终完成排序。

举例说明：4 5 6 3 2 1，从小到大排序

第一次冒泡的结果:4 5 6 3 2 1->4 5 3 6 2 1 -> 4 5 3 2 6 1 -> 4 5 3 2 1 6，6这个元素的位置确定了

第二次冒泡的结果:4 5 3 2 1 6->4 3 5 2 1 6 -> 4 3 2 5 1 6 -> 4 3 2 1 5 6，5这个元素的位置确定了

第三次冒泡的结果:4 3 2 1 5 6->3 4 2 1 5 6 -> 3 2 4 1 5 6 -> 3 2 1 4 5 6，4这个元素的位置确定了

第四次冒泡的结果:3 2 1 4 5 6->2 3 1 4 5 6 -> 2 1 3 4 5 6，3这个元素的位置确定了

第五次冒泡的结果:2 1 3 4 5 6->1 2 3 4 5 6，2这个元素的位置确定了

实现：设数组长度为N：

1、比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

2、这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就沉到数组第N-1个位置。

3、循环N=N-1，如果N不为0就重复前面二步，否则排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class BubbleSort {
    public static void BubbleSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j + 1] < arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int arr[] = new int[]{1, 6, 2, 3, 22};
        BubbleSort.BubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

冒泡排序法存在的不足及改进方法

在排序过程中，执行完最后的排序后，虽然数据已全部排序完毕，但程序无法判断是否完成排序。

为了解决这一不足，可设置一个标志位flag，将其初始值设置为非0，表示被排序的表是一个无序的表。

  • 每一次排序开始前设置flag值为0，在进行数据交换时，修改flag为非0。

在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据（有序状态），则结束排序，否则进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Arrays;
public class BubbleSort {
  public static void main(String[] args) {
    int data[] = { 4, 5, 6, 3, 2, 1 };
    int n = data.length;
    for (int i = 0; i < n - 1; i++) { //排序的次数
      boolean flag = false;
      for (int j = 0; j < n - 1 - i; j++) { //具体冒泡 n - 1 - i
        if (data[j] > data[j + 1]) {
          int temp = data[j]; 
          data[j] = data[j + 1];
          data[j + 1] = temp;
          flag = true;
        }
      }
      if(!flag) break;
    }
    System.out.println(Arrays.toString(data));
  }
}