一、直接插入排序
整个区间被分为
有序区间
无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入。
public static void insertSort（int[] arr）{
for （int i = 1; i < arr.length; i++） {
int tmp = arr[i];
int j = i - 1;
for （ ; j >= 0 ; j--） {
if （arr[j] > tmp）{
arr[j + 1] = arr[j];
}else{
//arr[j + 1] = tmp;//只要j回退的时候，遇到了比tmp小的元素，就结束了这次的比较
break;
}
}
//j回退到了小于0的地方
arr[j + 1] = tmp;
}
}
public static void main（String[] args） {
int[] array = {6,10,9,3,5};
insertSort（array）;
System.out.println（Arrays.toString（array））;
}
}
输出结果：
时间复杂度：最好O（N）–>数据本身是有序的；
* 最坏O（N^2）；–>数据逆序；
* 当一组数据，数据量不大且趋近于有序，此时用插入排序时间更快，越有序越快。
空间复杂度：O（1）；
稳定性：稳定的排序；
一个稳定的排序可以实现为不稳定的排序，但是一个本身就不稳定的排序不可以变成稳定的排序。
二、希尔排序
希尔排序法又称缩小增量法。
希尔排序法的本质是插入排序，只不过是将待排序的序列按某种规则分成几个子序列，分别对几个子序列进行直接插入排序。这个规则就是增量，增量选取很重要，增量一般选序列长度一半，然后逐半递减，直到最后一个增量为1，为1相当于直接插入排序。
public static void shell（int[] arr,int gap）{
for （int i = 1; i < arr.length; i++） {
int tmp = arr[i];
int j = i - gap;
for （; j >= 0 ; j-=gap） {
if（tmp < arr[j]）{
arr[j + gap] = arr[j];
}else{
break;
}
}
arr[j+gap] = tmp;
}
}
public static void shellSort（int[] arr） {
int gap = arr.length;
//增量在缩小，最后一组的增量为1
while （gap > 1）{
gap /= 2;
shell（arr,gap）;
}
shell（arr,1）;
}
public static void main（String[] args） {
int[] array = {9,1,2,5,7,4,8,6,3,5};
shellSort（array）;
System.out.println（Arrays.toString（array））;
|
