冒泡排序

1：比较相邻的元素。如果第一个比第二个大，就交换它们两个的位置；

2：对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数

3：针对所有的元素重复以上的步骤，除了最后一个；

4：重复步骤1~3，直到排序完成。

特点：

每轮把最大的往后面放

第一轮把最大的数放在最后

第二轮把第二大的数放在倒数第二个

以此类推

  1. public static void bubbleSort1(int[] array) {
  2.     int len = array.length;
  3.     if (len <= 1) {
  4.         return;
  5.     }
  6.     //开始冒泡
  7.     for (int i = 0; i < len; i++) {
  8.         for (int j = 0; j < len - i - 1; j++) {
  9.             //判断前后数据是否需要交换 如果前一个数据大于后一个数据则进行交换否则不交换
  10.             if (array[j] > array[j + 1]) {
  11.                 int temp = array[j];
  12.                 array[j] = array[j + 1];
  13.                 array[j + 1] = temp;
  14.             }
  15.         }
  16.     }
  17. }

改良版

效率改良版，如果数组已经排好序了，不需要数据交换了，直接可以提前结束了

  1. public static void bubbleSort2(int[] array) {
  2.         int len = array.length;
  3.         if (len <= 1) {
  4.             return;
  5.         }
  6.         //开始冒泡
  7.         for (int i = 0; i < len; i++) {
  8.             //是否需要提前结束冒泡的标识
  9.             boolean flag = true;
  10.             for (int j = 0; j < len - i - 1; j++) {
  11.                 //判断前后数据是否需要交换 如果前一个数据大于后一个数据则进行交换否则不交换
  12.                 if (array[j] > array[j + 1]) {
  13.                     int temp = array[j];
  14.                     array[j] = array[j + 1];
  15.                     array[j + 1] = temp;
  16.                     flag = false;
  17.                 }
  18.             }
  19.             if (flag) {
  20.                 return;
  21.             }
  22.         }
  23.     }

插入排序

1：从第一个元素开始，该元素可以认为已经被排序；

2：取出下一个元素，以当前元素的位置为基准从后向前扫描；

3：如果该元素（已排序）大于新元素，将该元素移到下一位置；

4：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5：将新元素插入到该位置后；

6：重复步骤2~5。

特点：第 i 轮会把前 i 个数排好序

  1. public static void insertion(int[] arr) {
  2.     if (arr.length <= 1) {
  3.         return;
  4.     }
  5.     for (int i = 0; i < arr.length; i++) {
  6.         for (int j = i; j > 0; j--) {
  7.             if (arr[j] < arr[j - 1]) {
  8.                 int temp = arr[j];
  9.                 arr[j] = arr[j - 1];
  10.                 arr[j - 1] = temp;
  11.             }
  12.         }
  13.     }
  14. }

选择排序

把最小的元素拿出来

特点：

每一轮把为排序的最小数放在前面

第一轮把最小的数放在第一个

第二轮把第二小的数放在第二个

以此类推

  1. public static void selection(int[] arr) {
  2.     if (arr.length <= 1) {
  3.         return;
  4.     }
  5.     for (int i = 0; i < arr.length; i++) {
  6.         //当前最小数的下标
  7.         int minPos = i;
  8.         for (int j = i + 1; j < arr.length; j++) {
  9.             //获得未排序的最小数下标
  10.             minPos = arr[minPos] < arr[j] ? minPos : j;
  11.         }
  12.         //最小数和当前下标的数交换位置
  13.         int temp = arr[i];
  14.         arr[i] = arr[minPos];
  15.         arr[minPos] = temp;
  16.     }
  17. }