一、插入排序(Insertion Sort)
1. 基本思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2. 排序过程：
【示例】：
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
| 01 |
Procedure InsertSort(Var R : FileType); |
| 02 |
|
| 03 |
//对R[1..N]按递增序进行插入排序, R[0]是监视哨// |
| 04 |
|
| 05 |
Begin |
| 06 |
|
| 07 |
for I := 2 To N Do //依次插入R[2],...,R[n]// |
| 08 |
|
| 09 |
begin |
| 10 |
|
| 11 |
R[0] := R[I]; J := I - 1; |
| 12 |
|
| 13 |
While R[0] < R[J] Do //查找R[I]的插入位置// |
| 14 |
|
| 15 |
begin |
| 16 |
|
| 17 |
R[J+1] := R[J]; //将大于R[I]的元素后移// |
| 18 |
|
| 19 |
J := J - 1 |
| 20 |
|
| 21 |
end |
| 22 |
|
| 23 |
R[J + 1] := R[0] ; //插入R[I] // |
| 24 |
|
| 25 |
end |
| 26 |
|
| 27 |
End; //InsertSort // |
| 28 |
二、选择排序
1. 基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2. 排序过程：
【示例】：
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后