插入排序，好比是洗撲克一樣，我們將牌分作兩堆，每次從后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的適當位置，例如：
排序前： [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();
????????}
????}