作者：海鹰
本人才疏学浅，若有纰漏，虚心请教
本文讲述插入排序算法
版权所有，未经允许，请勿随意转载。
经典的插入排序算法：直接插入排序和希尔排序。
各种插入排序算法都是在直接插入排序的基础上，从减少“比较”和“移动”这两种操作的次数着眼。
直接插入排序（Straight Insertion Sort）
一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1..i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1..i]。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入。
示例代码 [Java] ：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
* 直接插入排序
* @param nums
* @return
*/
public int[] straightInsertionSort(int[] nums){
int temple;
for( int i=1, j; i<nums.length; i++ ){
temple = nums[i];
for( j=i-1; j>=0&&nums[j]>temple; j-- ){
nums[j+1] = nums[j];
}
nums[j+1] = temple;
}
return nums;
}
希尔排序（Shell’s Sort），又称“缩小增量排序”（Diminishing Increment Sort）
它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
思考过程如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16[初始] 49 38 65 97 76 13 27 49
49 76
|_______________|
38 13
|_______________|
65 27
|_______________|
97 49
|_______________|
[第一趟] 49 13 27 49 76 38 65 97
49 27 76 65
|_______|________|______|
13 49 38 97
|_______|________|______|
[第二趟] 27 13 49 38 65 49 76 97
[第三趟] 间隔为 1 ，相当于来一次直接插入排序
示例代码 [Java] ：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 希尔插入
* @param nums
* @param distance
*/
public void shellInsertion(int[] nums, int distance){
int temple;
for( int i=distance, j; i<nums.length; i+=distance ){
temple = nums[i];
for( j=i-distance; j>=0&&nums[j]>temple; j-=distance ){
nums[j+distance] = nums[j];
}
nums[j+distance] = temple;
}
}
/**
* 希尔排序
* @param nums
* @param distances
* @return
*/
public int[] shellSort(int[] nums, int[] distances){
for(int i=0; i<distances.length; i++){
shellInsertion(nums, distances[i]);
}
return nums;
}
需注意的是，最后的间隔必须是1，即distances数组的最后一个元素必须是1。
折半插入排序（Binary Insertion Sort）
由于插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序。
折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。
示例代码 [Java] ：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* 折半插入排序
* @param nums
* @return
*/
public int[] binaryInsertionSort(int[] nums){
int temple;
for(int i=1, j, low, high, mid; i<nums.length; i++){
temple = nums[i];
low = 0; high = i-1;
while (low<=high){
mid = (low+high)/2;
if( nums[i] < nums[mid] )
high = mid - 1;
else
low = mid + 1;
}
for( j=i-1; j>=high+1; --j )
nums[j+1] = nums[j];
nums[j+1] = temple;
}
return nums;
}
在折半插入排序的基础上，还衍生出了“2-路插入排序”、“表插入排序”等算法。