image.png
    冒泡排序：
    从第一个数开始，和后一位对比，大的数后移。

    1. public static void bubbleSort(int[] arr) {
    2.         if (arr == null || arr.length < 2) {
    3.             return;
    4.         }
    5.         for (int end = arr.length - 1; end > 0; end--) {    //大的数冒泡到末尾之后，固定这个最大数，把end前移
    6.             for (int i = 0; i < end; i++) {                    //不会越界，i只到end-1,但会与end下标的值对比
    7.                 if (arr[i] > arr[i + 1]) {
    8.                     swap(arr, i, i + 1);
    9.                 }
    10.             }
    11.         }
    12.     }

    选择排序：
    i到n遍历选最小值放下标i位置。
    例：
    0到所有选一最小值，放0位置，
    1到所有，选最小值，放1位置
    ……

    1. public static void selectionSort(int[] arr) {
    2.         if (arr == null || arr.length < 2) {
    3.             return;
    4.         }
    5.         for (int i = 0; i < arr.length - 1; i++) {
    6.             int minIndex = i;                                        //每轮的最小值都不同，因此在此定义
    7.             for (int j = i + 1; j < arr.length; j++) {
    8.                 minIndex = arr[j] < arr[minIndex] ? j : minIndex;    
    9.             }
    10.             swap(arr, i, minIndex);                                    //最小值放入下标为i的位置
    11.         }
    12.     }

    插入排序：
    类似扑克牌等牌插入，假设插入的是第i个牌，有arr.length-1个待插入

    1. public static void insertionSort(int[] arr) {
    2.         if (arr == null || arr.length < 2) {
    3.             return;
    4.         }
    5.         for (int i = 1; i < arr.length; i++) {
    6.             for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {    //j是i前一个数，j与j+1比较，下标往前挪，逐个向前比较，直到j<0
    7.                 swap(arr, j, j + 1);
    8.             }
    9.         }
    10.     }

    希尔排序：
    初始增量为length/2,缩小增量继续以gap=gap/2的方式，进行分组，每组使用直接插入排序，随着增量减少，每组元素越多，增量为1时，这个数组为一组，算法结束。
    image.png
    image.png

    1. void shell_sort(int *data, int length) {
    2.     int gap = 0;
    3.     int i = 0, j = 0;
    4.     int temp;
    5.     for (gap = length / 2;gap >= 1; gap /= 2) {
    6.         for (i = gap;i < length;i ++) {
    7.             temp = data[i];
    8.             for (j = i-gap;j >= 0 && temp < data[j];j = j - gap) {
    9.                 data[j+gap] = data[j];            
    10.             }
    11.             data[j+gap] = temp;
    12.         }
    13.     }
    14. }

    归并排序：
    base case：划分至最小规模，就不用再划分

    1. public static void mergeSort(int[] arr) {
    2.         if (arr == null || arr.length < 2) {
    3.             return;
    4.         }
    5.         mergeSort(arr, 0, arr.length - 1);
    6.     }
    8. public static void mergeSort(int[] arr, int l, int r) {
    9.         if (l == r) {
    10.             return;
    11.         }
    12.         int mid = l + ((r - l) >> 1);
    13.         mergeSort(arr, l, mid);
    14.         mergeSort(arr, mid + 1, r);
    15.         merge(arr, l, mid, r);
    16.     }
    18. public static void merge(int[] arr, int l, int m, int r) {            //外排：归并排序；
    19.         int[] help = new int[r - l + 1];
    20.         int i = 0;
    21.         int p1 = l;
    22.         int p2 = m + 1;
    23.         while (p1 <= m && p2 <= r) {
    24.             help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];    //都不越界时，最小数存help里，指针再加1；
    25.         }
    26.         while (p1 <= m) {
    27.             help[i++] = arr[p1++];                                    //p2越界，p1存入help;
    28.         }
    29.         while (p2 <= r) {
    30.             help[i++] = arr[p2++];
    31.         }
    32.         for (i = 0; i < help.length; i++) {
    33.             arr[l + i] = help[i];                                    //按顺序存回数组中；
    34.         }
    35. }