冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。关键点：
1）N个元素，有N轮冒泡
2）每一轮，都从第一个元素开始，依次与其下一个比较，是否需要交换
image.png

  1.     public void bubbleSort() {
  2.         int[] data = {4, 5, 6, 3, 2, 1};
  3.         System.out.println("未排序=" + Arrays.toString(data));
  4.         // 从小到大排序
  5.         for (int i = 0; i < data.length; i++) {
  6.             // 是否有交互数据
  7.             boolean swap = false;
  8.             for (int j = 0; j < data.length - i - 1; j++) {
  9.                 if (data[j] > data[j + 1]) {
  10.                     int t = data[j];
  11.                     data[j] = data[j + 1];
  12.                     data[j + 1] = t;
  13.                     swap = true;
  14.                 }
  15.             }
  16.             System.out.println(String.format("第%d轮", i + 1) + "=" + Arrays.toString(data) + ",swap=" + swap);
  17.             if (!swap) {
  18.                 break;
  19.             }
  20.         }
  21.     }

选择排序

选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾
image.png

  1. public class SelectionSort implements IArraySort {
  3.     @Override
  4.     public int[] sort(int[] sourceArray) throws Exception {
  5.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  7.         // 总共要经过 N-1 轮比较
  8.         for (int i = 0; i < arr.length - 1; i++) {
  9.             int min = i;
  11.             // 每轮需要比较的次数 N-i
  12.             for (int j = i + 1; j < arr.length; j++) {
  13.                 if (arr[j] < arr[min]) {
  14.                     // 记录目前能找到的最小值元素的下标
  15.                     min = j;
  16.                 }
  17.             }
  19.             // 将找到的最小值和i位置所在的值进行交换
  20.             if (i != min) {
  21.                 int tmp = arr[i];
  22.                 arr[i] = arr[min];
  23.                 arr[min] = tmp;
  24.             }
  26.         }
  27.         return arr;
  28.     }
  29. }