分别对1k,1w,10w,20w大小的随机数组排序
得到综合结果是:
速度: 快速排序>>归并排序>>>>>插入排序>>选择排序>>冒泡排序

1，插入排序

先找待插入数字，然后提出来，与前面有序的数列对比，看比谁小就放在谁前面
image.png

  1. public class InsertSort {
  3.     public static void sort(int[] arr) {
  4.         if (arr.length >= 2) {
  5.             for (int i = 1; i < arr.length; i++) {
  6.                 //挖出一个要用来插入的值,同时位置上留下一个可以存新的值的坑
  7.                 int x = arr[i];
  8.                 int j = i - 1;
  9.                 //在前面有一个或连续多个值比x大的时候,一直循环往前面找,将x插入到这串值前面
  10.                 while (j >= 0 && arr[j] > x) {
  11.                     //当arr[j]比x大的时候,将j向后移一位,正好填到坑中
  12.                     arr[j + 1] = arr[j];
  13.                     j--;
  14.                 }
  15.                 //将x插入到最前面
  16.                 arr[j + 1] = x;
  17.             }
  18.         }
  19.     }
  20. }

2，快速排序法

  1. public class QuickSort {
  3.     public static void sort(int[] arr,int begin,int end) {
  4.         //先定义两个参数接收排序起始值和结束值
  5.         int a = begin;
  6.         int b = end;
  7.         //先判断a是否大于b
  9.         if (a >= b) {
  10.             //没必要排序
  11.             return;
  12.         }
  13.         //基准数,默认设置为第一个值
  14.         int x = arr[a];
  16.         //循环
  17.         while (a < b) {
  18.             //从后往前找,找到一个比基准数x小的值,赋给arr[a]
  19.             //如果a和b的逻辑正确--a<b ,并且最后一个值arr[b]>x,就一直往下找,直到找到后面的值大于x
  20.             while (a < b && arr[b] >= x) {
  21.                 b--;
  22.             }
  23.             //跳出循环,两种情况,一是a和b的逻辑不对了,a>=b,这时候排序结束.二是在后面找到了比x小的值
  24.             if (a < b) {
  25.                 //将这时候找到的arr[b]放到最前面arr[a]
  26.                 arr[a] = arr[b];
  27.                 //排序的起始位置后移一位
  28.                 a++;
  29.             }
  31.             //从前往后找,找到一个比基准数x大的值,放在最后面arr[b]
  32.             while (a < b && arr[a] <= x) {
  33.                 a++;
  34.             }
  35.             if (a < b) {
  36.                 arr[b] = arr[a];
  37.                 //排序的终止位置前移一位
  38.                 b--;
  39.             }
  40.         }
  41.         //跳出循环 a < b的逻辑不成立了,a==b重合了,此时将x赋值回去arr[a]
  42.         arr[a] = x;
  43.         //调用递归函数,再细分再排序
  44.         sort(arr,begin,a-1);
  45.         sort(arr,a+1,end);
  46.     }
  47. }

3，冒泡排序

跟前面的比较，小的往前

  1. public class MaoPao {
  3.     public static void  sort(int[] arr){
  4.         for (int i = 1; i < arr.length; i++) {  //第一层for循环,用来控制冒泡的次数
  5.             for (int j = 0; j < arr.length-1; j++) { //第二层for循环,用来控制冒泡一层层到最后
  6.                 //如果前一个数比后一个数大,两者调换 ,意味着泡泡向上走了一层
  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.     }
  15. }

在这个版本中,改动了两点
第一点是加入了一个布尔值,判断第二层循环中的调换有没有执行,如果没有进行两两调换,说明后面都已经排好序了,已经不需要再循环了,直接跳出循环,排序结束.
第二点是第二层循环不再循环到arr.length - 1,因为外面的i循环递增一次,说明数组最后就多了一个排好序的大泡泡.第二层循环也就不需要到最末尾一位了,可以提前结束循环

  1.  /**
  2.  * 终极版冒泡排序
  3.  * 加入一个布尔变量,如果内循环没有交换值,说明已经排序完成,提前终止
  4.  * @param arr
  5.  */
  6. public static void sortPlus(int[] arr){
  7.     if(arr != null && arr.length > 1){
  8.         for(int i = 0; i < arr.length - 1; i++){
  9.             // 初始化一个布尔值
  10.             boolean flag = true;
  11.             for(int j = 0; j < arr.length - i - 1 ; j++){
  12.                 if(arr[j] > arr[j+1]){
  13.                     // 调换
  14.                     int temp;
  15.                     temp = arr[j];
  16.                     arr[j] = arr[j+1];
  17.                     arr[j+1] = temp;
  18.                     // 改变flag
  19.                     flag = false;
  20.                 }
  21.             }
  22.             if(flag){
  23.                 break;
  24.             }
  25.         }
  26.     }
  27. }

4，选择排序

首先在未排序数列中找到最小元素，然后将其与数列的首部元素进行交换，然后循环找 ，放在最前面
image.png

  1. public static void sort(int[] arr){
  2.     for(int i = 0; i < arr.length - 1 ; i++){
  3.         int min = i; // 遍历的区间最小的值
  4.         for (int j = i + 1; j < arr.length ;j++){
  5.              if(arr[j] < arr[min]){
  6.                  // 找到当前遍历区间最小的值的索引
  7.                  min = j;
  8.              }
  9.         }
  10.         if(min != i){
  11.             // 发生了调换
  12.             int temp =  arr[min];
  13.             arr[min] = arr[i];
  14.             arr[i] = temp;
  15.         }
  16.     }
  17. }

5，归并排序

归并排序,分成两个数一组，排序，然后合起来 ，合并的规则是将其按从小到大的顺序放到一个临时数组中,再把这个临时数组替换原数组相应位置,
image.png

  1. public static void mergeSort(int[] a,int s,int e){
  2.     int m = (s + e) / 2;
  3.     if (s < e){
  4.       mergeSort(a,s,m);
  5.       mergeSort(a,m+1,e);
  6.       //归并
  7.       merge(a,s,m,e);
  8.     }
  9.   }
  11.   private static void merge(int[] a, int s, int m, int e) {
  12.     //初始化一个从起始s到终止e的一个数组
  13.     int[] temp = new int[(e - s) + 1];
  14.     //左起始指针
  15.     int l = s;
  16.     //右起始指针
  17.     int r = m+1;
  18.     int i = 0;
  19.     //将s-e这段数据在逻辑上一分为二,l-m为一个左边的数组,r-e为一个右边的数组,两边都是有序的
  20.     //从两边的第一个指针开始遍历,将其中小的那个值放在temp数组中
  21.     while (l <= m && r <= e){
  22.       if (a[l] < a[r]){
  23.         temp[i++] = a[l++];
  24.       }else{
  25.         temp[i++] = a[r++];
  26.       }
  27.     }
  29.     //将两个数组剩余的数放到temp中
  30.     while (l <= m){
  31.       temp[i++] = a[l++];
  32.     }
  33.     while (r <= e){
  34.       temp[i++] = a[r++];
  35.     }
  37.     //将temp数组覆盖原数组
  38.     for (int n = 0; n < temp.length; n++) {
  39.       a[s+n] = temp[n];
  40.     }
  42.   }

6，Arrays.sort（）

Arrays工具类提供的排序方法。它内部实现也是快速排序

  1. private static void arraysSort(int[] a){
  2.     Arrays.sort(a);
  3.   }

7，Collections.sort（）

将数组转为list,使用集合的排序方法,但是这无异于兜圈子,因为集合底层也是数组

  1. private static void listSort(int[] a){
  2.     List<Integer> integers = Ints.asList(a);
  3.     Collections.sort(integers);
  4.     integers.toArray(new Integer[a.length]);
  5.   }