插入排序，好比是洗扑克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置，例如：
排序前： [92], 77, 67, 8, 6, 84, 55, 85, 43, 67 -- 将数组分为两部分，第一个元素为一组
第 1 次排序：[77 92] 67 8 6 84 55 85 43 67 -- 将后一组的第一个元素 77 插入前一组的适当位置
第 2 次排序：[67 77 92] 8 6 84 55 85 43 67 -- 将后一组的第一个元素 67 插入前一组的适当位置
第 3 次排序：[8 67 77 92] 6 84 55 85 43 67 -- 将后一组的第一个元素 8 插入前一组的适当位置
第 4 次排序：[6 8 67 77 92 84] 55 85 43 67 -- 将后一组的第一个元素 6 插入前一组的适当位置
第 5 次排序：[6 8 67 77 84 92 55] 85 43 67 -- 将后一组的第一个元素 84 插入前一组的适当位置
第 6 次排序：[6 8 55 67 77 84 92 85] 43 67 -- 将后一组的第一个元素 55 插入前一组的适当位置
第 7 次排序：[6 8 55 67 77 84 85 92 43] 67 -- 将后一组的第一个元素 85 插入前一组的适当位置
第 8 次排序：[6 8 43 55 67 77 84 85 92] 67 -- 将后一组的第一个元素 43 插入前一组的适当位置
第 9 次排序：[6 8 43 55 67 67 77 84 85 92] -- 将后一组的第一个元素 67 插入前一组的适当位置
Java代码实现，如下：
/** */
/**
* 插入排序
*
@param
data：等代排序整型数组
* data = { 92, 77, 67, 8, 6, 84, 55, 85, 43, 67 }
* 排序结果：
* 第 1 次排序：77 92 67 8 6 84 55 85 43 67
* 第 2 次排序：67 77 92 8 6 84 55 85 43 67
* 第 3 次排序：8 67 77 92 6 84 55 85 43 67
* 第 4 次排序：6 8 67 77 92 84 55 85 43 67
* 第 5 次排序：6 8 67 77 84 92 55 85 43 67
* 第 6 次排序：6 8 55 67 77 84 92 85 43 67
* 第 7 次排序：6 8 55 67 77 84 85 92 43 67
* 第 8 次排序：6 8 43 55 67 77 84 85 92 67
* 第 9 次排序：6 8 43 55 67 67 77 84 85 92
*/
public
void
insertSort(
int
data[])
{
int
k, temp, max
=
data.length;
for
(
int
i
=
1
; i
<
max; i
++
)
{
temp
=
data[i];
//
后一组的第一个元素
k
=
i
-
1
;
//
从前一组的最后一个元素开始比较
while
(temp
<
data[k])
{
data[k
+
1
]
=
data[k];
//
如果前一组元素大于后一组第一个元素，则后移
k
--
;
if
(k
==
-
1
)
break
;
//
如果前一组元素比较完，则跳出
}
data[k
+
1
]
=
temp;
//
插入适当的位置
System.out.print(
"
第
"
+
i
+
"
次排序：
"
);
for
(
int
j
=
0
; j
<=
max
-
1
; j
++
)
{
System.out.print(data[j]
+
"
"
);
}
System.out.println();
}
}