插入排序，希尔排序
插入排序
插入排序是一种比较排序算法
核心思想
在每次遍历序列过程中，从序列中取出一个元素插入到有序序列中，形成新的有序序列，重复该过程，直到遍历完成，形成新的有序序列。
特点：
- 时间复杂度分析：O(N^2)，如果序列在排序前已经是有序序列，则为O(N)
- 空间复杂度分析：O(1)
- 数据量较少时效率高。插入排序适合数据量少的情况
- 算法的实际运行效率优于选择排序和冒泡排序。
- 稳定排序 — 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
/**
* 插入排序 O(N^2)
* @param a
*/
public static void insertSort(int[] a) {
int j;
//外层循环控制需要排序的趟数 -- a.length - 1
for(int p = 1;p<a.length;p++) {
//当前数据
int tmp = a[p];
//比较---当前数据小于前一位数据，则交换位置
for(j = p;j>0 && tmp<a[j-1];j--) {
a[j] = a[j-1];
}
//退出循环--找到合适位置，将当前数据放入该位置
a[j] = tmp;
}
}
希尔排序
希尔排序是插入排序的修改版，根据步长由长到短分组，分组进行插入排序，直到步长为1为止，属于插入排序的一种。
核心思想
希尔排序为了加快速度，改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
特点：
- 希尔排序的时间复杂度较直接插入排序低，它的时间是所取“增量”（步长gap）序列的函数。
最好时间复杂度： O(n) – 有序情况下
平均时间复杂度： O(1.2^n ~ 1.5^n) – Hibbard
最坏时间复杂度： O(n^2) — 希尔增量 - 空间复杂度：O(1)
- 非稳定排序 — 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
/**
* 优化 -- 插入排序
* 希尔排序 -- 希尔增量 O(N^2)
* -- Hibbard增量O(N^3/2)
* @param a
*/
public static void shellSort(int[] a) {
int j;
//最外层循环控制步长 -- 减少插入排序的数据量
for(int gap = a.length/2;gap>0;gap/=2 ) {
//内层嵌套for循环是插入排序
for(int p = gap;p<a.length;p++) {
int tmp = a[p];
for(j = p;j>=gap && tmp<a[j-gap];j-=gap) {
a[j] = a[j-gap];
}
a[j] = tmp;
}
}
}
测试
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,3,2,8,9,2,4,5,10,20,12};
insertSort(a);
int[] b = {1,3,4,2,1,9,8,10,5,4,3,2,1,20};
shellSort(b);
for(int i = 0;i<a.length;i++) {
System.out.print(a[i]+"\t");
}
System.out.println("\n");
for(int i = 0;i<b.length;i++) {
System.out.print(b[i]+"\t");
}
}
结果：