1、插入排序

插入排序的本质就是把一堆无序的元素，一次拿一个，每次拿的元素都按顺序排放，就像玩扑克摸排的时候。
理解的核心是想象两个集合，一个放有序元素，一个放原始的无序元素。开始之前，有序集合为空；排序完成之后，无序元素为空。排序的过程就是：从无序集合拿第一元素，放入有序集合中，再从无序集合中拿一个，放入有序集合的时候，看看已经有元素的大小，按顺序插入，以此类推，直到无序集合为空。
代码实现的时候就有技巧了，不需要真的开两个集合，就利用现有的集合，从第一个元素开始把集合分为两半，前一半有序，后一半无序，每次把无序中的第一个元素移动到有序那部分中。

  1. public static void main(String[] args) {
  2.     int[] arr = new int[]{23,15,8,66,79,18};
  4.     insertSort(arr);
  5.     //测试
  6.     for (int i : arr) {
  7.         System.out.print(i + "  ");
  8.     }
  10. }
  12. //插入排序，理解的核心是两个集合
  13. private static void insertSort(int[] arr) {
  14.     if(arr.length == 1){
  15.         return ;
  16.     }
  17.     //外层循环，未排序的元素
  18.     for (int i = 1; i < arr.length; i++) {
  19.         //内层循环，已排序的元素，第一个元素默认是已经排序的
  20.         //每次循环都是把无序元素的第一个移动到有序元素中
  21.         int j = i-1;
  22.         int n = arr[i];  //记录当前循环要排序的元素
  23.         for ( ; j >= 0 ; j--) {
  24.             if(arr[j] > n){
  25.                 arr[j+1] = arr[j];  
  26.             }else {
  27.                 break;
  28.             }
  29.         }
  30.         arr[j+1] = n;
  31.     }
  32. }

2、归并排序

使用递归的方法，先把集合拆开，然后合并的时候进行排序
核心思路是把集合的元素进行逐级拆分，每次对半，直到所有的元素被拆开，每个元素一组
开始合并的时候，两个一组进行合并，使用插入排序的思路，借助一个辅助数组，然后使用两个指针，分别开始遍历两个数组，将元素依次放入新数组。逐级向上合并，每次合并的时候，两个集合各自内都是有序的，所以只需要遍历一遍，至少会有一个集合的元素被排完，接着就把剩下一个集合的剩下的元素直接加到辅助数据中就好了。

  1.  public static void main(String[] args) {
  2.      int[] arr = new int[]{44,15,6,23,15,8,66,79,18};
  4.      mergeSort(arr,0,arr.length-1);
  5.      //测试
  6.      for (int i : arr) {
  7.          System.out.print(i + "  ");
  8.      }
  10.  }
  12. //拆分
  13. private static void mergeSort(int[] arr, int left, int right) {
  14.     if(left<right){
  15.         int mid = (right - left) / 2 + left;
  16.         //拆分
  17.         mergeSort(arr,left,mid);
  18.         mergeSort(arr,mid+1,right);
  19.         //合并（排序）
  20.         merge(arr,left,mid,right);
  21.     }
  22. }
  24. //合并（排序）
  25. private static void merge(int[] arr, int left, int mid, int right) {
  26.     //借助一个辅助数数组
  27.     int[] temp = new int[arr.length];
  28.     //两个指针，分别从两个数组开始遍历
  29.     int l = left;
  30.     int r = mid + 1;
  31.     int loc = left;
  32.     while (l <= mid && r <= right){
  33.         if(arr[l]<arr[r]){
  34.             temp[loc] = arr[l];
  35.             l++;
  36.             loc++;
  37.         }else {
  38.             temp[loc] = arr[r];
  39.             r++;
  40.             loc++;
  41.         }
  42.     }
  43.     //处理剩余元素
  44.     while (l <= mid){
  45.         temp[loc++] = arr[l++];
  46.     }
  47.     while (r <= right){
  48.         temp[loc++] = arr[r++];
  49.     }
  50.     //将辅助元素的数组赋给原数组
  51.     for (int i = left; i <= right; i++) {
  52.         arr[i] = temp[i];
  53.     }
  54. }

3、希尔排序

4、冒泡排序

  1. //冒泡
  2. private static void bubleSort(int[] arr) {
  3.     if(arr.length<=1){
  4.         return;
  5.     }
  6.     //从头开始，比较相邻的两个元素，前面比后面大的，交换位置，直到最大的元素移动到最后
  7.     //第一次循环把最大的元素移动到最后一位，第二次把第二大的元素移动到倒数第二位，依次类推，直到所有元素有序
  8.     for (int i = 0; i < arr.length - 1; i++) {  //最后一个元素不需要遍历，因为遍历到倒数第二个的时候arr[j]>arr[j+1]就会进行比较了
  9.         //j 的范围从o到 arr.length-1-i   前面已经排好序的元素，下一次就没必要再次比较了
  10.         for (int j = 0; j < arr.length - 1 - i; j++) {
  11.             if(arr[j] > arr[j+1]){
  12.                 int temp = arr[j];
  13.                 arr[j] = arr[j+1];
  14.                 arr[j+1] = temp;
  15.             }
  16.         }
  17.     }
  18. }

5、选择排序

  1. //选择排序
  2. private static void selectSort(int[] arr) {
  3.     //每一轮会找到最小的一个元素放在开头，下一轮从之后一个元素开始
  4.     //每一轮从这轮的第二个元素开始，遍历到头找到最小的一个，与这轮第一个元素进行比较，如果比第一个小，交换位置
  5.     if(arr.length<=1){
  6.         return;
  7.     }
  8.     for (int i = 0; i < arr.length - 1; i++) {
  9.         int min = i ;
  10.         //从i+1开始，找到之后元素中最小的那个，标记一下
  11.         for (int j = i + 1; j < arr.length; j++) {
  12.             if (arr[min] > arr[j]) {
  13.                 min = j;
  14.             }
  15.         }
  16.         //比较最小元素和起始元素，把更小的放前面
  17.         if(arr[i] > arr[min]){
  18.             int temp = arr[min];
  19.             arr[min]  = arr[i];
  20.             arr[i] = temp;
  21.         }
  22.     }
  23. }

比较冒泡排序与选择排序

6、快速排序

  1. //快速排序，核心找一个基准值（比如找数组的第一个元素），然后与其余元素比较，
  2. // 经过一轮比较之后，比这个基准值小的元素就会移动到基准值左边，比基准值大的元素就移动到基准值右边，
  3. // 然后在用同样的方法分别处理基准值左右两部分数组，直到所有的元素被分开
  4. private static void quickSort(int[] arr, int left, int right) {
  5.     if(left<right){
  6.         int base = arr[left]; //这个数组中的第一个元素为基准值，这里涉及到递归调用，第一个的意思是，每次要操作的那部分的数组的第一个
  7.         int ll = left;
  8.         int rr = right;
  9.         while (ll < rr){
  10.             //先从数组最后一个元素开始比较，直到找到一个比基准值小的元素，交换位置
  11.             while (ll < rr && arr[rr]>base){
  12.                 rr--;
  13.             }
  14.             if(ll < rr){
  15.                 arr[ll] = arr[rr];
  16.                 arr[rr] = base;
  17.                 ll++;
  18.             }
  19.             //这时候基准值已经移动到后面，然后再从前面开始比较，直到找到一个比基准值大的元素，交换位置
  20.             while (ll < rr && arr[ll]<base){
  21.                 ll++;
  22.             }
  23.             if(ll < rr){
  24.                 arr[rr] = arr[ll];
  25.                 arr[ll] = base;
  26.                 rr--;
  27.             }
  28.         }
  29.         //这样一轮下来，基准值就会移动到中间，左边是比它小的元素，右边是比它大的元素，(极端情况，基准值会出现在两端)
  30.         //然后用同样的逻辑处理左右两部分数据
  31.         if(left<ll-1){
  32.             quickSort(arr,left,ll-1);
  33.         }
  34.         if(ll+1 < right){
  35.             quickSort(arr,ll+1,right);
  36.         }
  37.     }
  38. }

快速的时间复杂度O(nlogn) 递归类似循环，进行的次数取决于基准值的选择，最好的是每次刚好取到中间，一共就会递归logn次，在每次中排序的时候相当于所有的元素排一遍，所以是nlogn
如果基准值选择不好，极端情况是每次都是一端，那么就会递归n次，最后的时间复杂度就会变成n^2。所以快速排序优化的点就在于如何选择基准值。
归并的时间复杂度是O(nlogn) 每次拆分一半，一共会拆分logn次，每次都要处理所有元素，所以是nlogn次

比较归并排序与快速排序

几种排序的总结：