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;
}
}
