插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序，时间复杂度O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
第一种直接插入排序法：
简单粗暴，输出结果：
从结果来看 直接插入排序明显是从第二位开始一位一位排序数组直到将整个数组排序完成
二分查入法：
折半插入算法是对直接插入排序算法的改进，排序原理同直接插入算法。
区别：在插入到已排序的数据时采用来折半查找（二分查找），取已经排好序的数组的中间元素，与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于前半部分，否则属于后半部分，依次不断缩小范围，确定要插入的位置。
代码：
输出结果：
希尔排序法：
public class ShellSort
{
public static void main(String[] args)
{
int[] array = { 5, 7, 1, 3, 9, 11 };
System.out.println("排序之前：");
for (int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
// 希尔排序
int gap = array.length;
while (true)
{
gap /= 2; // 增量每次减半
System.out.println("gap = " + gap);
for (int i = 0; i < gap; i++)
{
for (int j = i + gap; j < array.length; j += gap)
{
// 这个循环里其实就是一个插入排序
int temp = array[j];
int k = j - gap;
while (k >= 0 && array[k] > temp)
{
array[k + gap] = array[k];
k -= gap;
}
array[k + gap] = temp;
for (int x = 0; x < array.length; x++)
{
System.out.print(array[x] + " ");
}
System.out.println("============");
}
}
for (int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
if (gap == 1)
break;
}
}
}
输出结果:
排序之前：
5 7 1 3 9 11
gap = 3
3 7 1 5 9 11 ============
3 7 1 5 9 11 ============
3 7 1 5 9 11 ============
3 7 1 5 9 11
gap = 1
3 7 1 5 9 11 ============
1 3 7 5 9 11 ============
1 3 5 7 9 11 ============
1 3 5 7 9 11 ============
1 3 5 7 9 11 ============
1 3 5 7 9 11
代码2：
public class ShellSort2
{
public static void main(String[] args)
{
int[] data ={ 5, 7, 1, 3, 9, 11};
int[] temp = new int[data.length];
System.out.println();
for (int gap = data.length/2; gap > 0; gap--) {
System.out.println("gap=" + gap);
int index = 0;
for (int i = 0; i < gap; i++){
int begin = index;
for (int j = i; j < data.length; j+=gap) {
int x = index;
while (x > begin && data[j] < temp[x-1]) {
temp[x] = temp[x-1];
x--;
}
temp[x] = data[j];
index++;
}
}
for (int i = 0; i < temp.length; i++)
{
System.out.print(temp[i] + " ");
}
System.out.println();
data =temp;
temp = new int[data.length];
}
}
}
输出结果：
gap=3
3 5 7 9 1 11
gap=2
1 3 7 5 9 11
gap=1
1 3 5 7 9 11
两种方法的主要差异其实只有一点
1、增量缩减 一个通过不停的除以2的方式快速缩减至1，另外一种逐次递减减少至1
至于优劣 能准确的通过代码将此算法敲出来了 在了解一下其中的数学理论就清楚了
原文：https://www.cnblogs.com/tiantanglw/p/12439406.html