一、直接插入排序算法

1.1 基本思想：

把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。
实例：

1. 初始状态 3，1，5，7，2，4，9，6（共8个数）
   有序表：3；
   无序表：1，5，7，2，4，9，6

2. 第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序
   有序表：1，3；
   无序表：5，7，2，4，9，6

3. 第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序
   　有序表：1，3，5；
   　无序表：7，2，4，9，6

4. 第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序
   　有序表：1，3，5，7；
   　无序表：2，4，9，6

5. 第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序
   　有序表：1，2，3，5，7；
   　无序表：4，9，6

6. 第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序
   　有序表：1，2，3，4，5，7；
   　无序表：9，6

7. 第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序
   　有序表：1，2，3，4，5，7，9；
   　无序表：6

8. 第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序
   　有序表：1，2，3，4，5，6，7，9；
   　无序表：（空）

1.2 代码实现

package com.test.www;

public class Hello {
	
	public static void insertSort(int[] a) {
		int length = a.length;// 数组长度，将这个提取出来是为了提高速度。
		int insertNum;// 要插入的数
		for (int i = 1; i < length; i++) {// 插入的次数
			insertNum = a[i];// 要插入的数
			for (int j = i - 1; j >= 0 && a[j] > insertNum; j--) {
				a[j + 1] = a[j];
				a[j] = insertNum;
			}
		}
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	public static void main(String[] args) {
		int[] a = { 3, 1, 5, 7, 2, 4, 9, 6 };
		insertSort(a);
	}

}

二、直接插入排序算法

2.1 基本思想

希尔排序(Shell Sort)是插入排序的一种，是针对直接插入排序算法的改进，是将整个无序列分割成若干小的子序列分别进行插入排序，希尔排序并不稳定。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<d_t-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。