冒泡排序

• 图解

  

• 原理

  • 假设有数组 arr[3, 9, -1, 10, -2]
  • 第一轮循环数组时，下标指向的值和它后面的值作比较，如果大于它后面的值，二者就交换，所以此轮循环下标最大就是arr.length - 1，第一轮数组元素循环结束后，最大的元素就放在了倒数第一个位置
  • 第二轮循环数组时，下标指向的值和它后面的值作比较，如果大于它后面的值，二者就交换，由于第一次循环之后，最大元素已经在最后一个元素的位置了，所以此次下标就没必要到达arr.length - 1了，而是前一个位置arr.length - 1，第二轮数组元素循环结束后，第二大的元素就放在了倒数第二的位置
  • 以此类推
  • 那么要循环多少轮呢？逆向思维：大的数据每一轮都找到了自己的位置，那最小的元素肯定就慢慢地被交换到了前面，所以一共会循环arr.length - 1轮

• 优化的地方

  • 在经过一轮循环以后，如果数组的顺序没有变化，那么说明其实此次循环后数据已经排好顺序了，剩余轮数就没必要执行了

• 完整代码

  public class BubbleSorting {
  
      public static void main(String[] args) {
          int arr[] = {3, 9, -1, 10, -2};
          int temp;
          boolean loop = false;
  
          // 共循环 arr.length - 1 轮
          for(int i = 0; i < arr.length - 1; i++) {
  
              // 第一轮 指针最大到 arr.length - 1 的位置
              // 第二轮 指针最大到 arr.length - 2 的位置
              // 以此类推...
              for (int j = 0; j < arr.length - 1 - i; j++) {
                  if (arr[j] > arr[j + 1]) {
                      temp = arr[j];
                      arr[j] = arr[j + 1];
                      arr[j + 1] = temp;
  
                      loop = true;
                  }
              }
              System.out.println("第 " + (i + 1) + " 轮排序的结果：" + java.util.Arrays.toString(arr));
  
              // 没有交换,说明已经排好序了
              if (!loop) {
                  break;
              }else {
                  // 重置标识,为下一轮做准备
                  loop = false;
              }
          }
      }
  }

选择排序

• 图解

  

• 原理

  • 假设有数组 arr[3, 9, -1, 10, -2]
  • 第一轮排序，找出下标从 [0, arr.length - 1] 中的数据的最小值，与arr[0]交换位置
  • 第二轮排序，找出下标从 [1, arr.length - 1] 中的数据的最小值，与arr[1]交换位置
  • 以此类推
  • 那么要循环多少轮呢？当下标从arr.length - 1开始(循环次数为arr.length)的时候，此次就没必要找最小值并替换了，所以循环的轮数为 arr.length - 1

• 完整代码

  public class SelectSorting {
  
      public static void main(String[] args) {
          int arr[] = {3, 9, -1, 10, -2};
          int temp;
  
          // 循环的轮数为 arr.length - 1
          for (int i = 0; i < arr.length - 1; i++) {
              int minIndex = i;
              
              // 从没设置过最小值的下标开始遍历
              for (int j = i; j < arr.length; j++) {
                  if (arr[j] < arr[minIndex]) {
                      minIndex = j;
                  }
              }
              
              // 将最小元素交换到前面
              temp = arr[i];
              arr[i] = arr[minIndex];
              arr[minIndex] = temp;
          }
  
          System.out.println("排序后的数组为：" + java.util.Arrays.toString(arr));
      }
  
  }