1.算法介绍

1.1 选择排序

选择排序的工作原理在于每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
代码实现如下：

public static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){
        int min = i;
        for(int j = i + 1; j < arr.length; j++)
            if(arr[j] < arr[min])
                min = j;
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

1.2 冒泡排序

比较相邻的元素，如果第一个元素比第二个元素大的话就交换位置，对每一对相邻元素都进行这样的操作，那么最后的元素就是最大的元素。然后对前n - 1个元素进行同样的操作，直到没有相邻元素可以比较，那么排序就完成了。
代码实现如下：

public static void bubbleSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){
        for(int j = 0; j < arr.length - i - 1; j++){
            if(arr[j] > arr[j + 1]){
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

1.3 插入排序

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。与选择排序一样，当前索引的左边的所有元素是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，可能需要被移动。和选择排序不同的是，插入排序所需的时间取决于输入元素的初始顺序。
代码实现如下：

public static void insertionSort(int[] arr){
    for(int i = 1; i < arr.length; i++){
        for(int j = i; j > 0 && arr[j - 1] > arr[j]; j--){
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        } 
    }
}

1.4 希尔排序

希尔排序是基于插入排序的排序算法，它的基本思想是先将整个待排记录序列分割成若干个子序列，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。而子序列的构成不是简单地“逐段分割”，而是将相隔某个增量的记录来组成一个子序列。如何选取增量序列是决定希尔排序性能的重要因素，但至今尚未有人求得最佳的增量序列。
代码实现如下，增量序列为 1/2(3^k - 1)：

public static void shellSort(int[] arr){
    int N = arr.length;
    int h = 1;
    while(h < N/3)
        h = 3*h + 1;
    while(h >= 1){
        for(int i = h; i < N; i++){
            for(int j = i; j >= h && arr[j - h] > arr[j]; j -= h){
                int temp = arr[j];
                arr[j] = arr[j - h];
                arr[j - h] = temp;
            } 
        }
        h = h / 3;
    }
}