【正确答案】(1)算法
各种算法的思想具体请参见教材，其中有详细地说明，这里不再赘述。
(2)程序实现
此处将6种算法的实现写成6个函数，放在一个程序中。
每个函数中添加Pmove和Pcompare的指针参数记录移动和比较次数。由于有时要递归调用，所以函数内部比较和移动的次数加上调用的初始值才是实际的值。主函数中调用时，每次要将这两个参数的初值设为0。
考虑到随机性，每次排序都重新生成新的数组。各种排序算法均按递增序排列。
完整程序：(略)
(3)实习结果比较分析
排序结果：
n=20
the origion record：
46 30 82 90 56 17 95 15 48 26
4 58 71 79 92 60 12 21 63 47
直接插入排序：
4 12 15 17 21 26 30 46 47 48
56 58 60 63 71 79 82 90 92 95
move：132 compare：112
the origion record：
19 41 90 85 14 9 52 71 79 16
81 51 95 93 34 10 79 95 61 92
直接选择排序：
9 10 14 16 19 34 41 51 52 61
71 79 79 81 85 90 92 93 95 95
move：54 compare：190
the origion record：
89 88 66 64 92 63 66 64 39 51
27 0 95 12 8 66 47 42 74 69
冒泡排序：
0 8 12 27 39 42 47 51 63 64
64 66 66 66 69 74 88 89 92 95
move：351 compare：175
the origion record：
89 83 66 41 90 78 65 79 90 33
53 29 85 22 33 37 36 68 60 58
Shell排序：
22 29 33 33 36 37 41 53 58 60
65 66 68 78 79 83 85 89 90 90
move；161 compare：87
the origion record：
36 60 42 42 67 15 16 18 56 79
8 59 61 97 55 81 75 40 90 1
快速排序：
1 8 15 16 18 36 40 42 42 55
56 59 60 61 67 75 79 81 90 97
move：24 compare：64
the origion record：
37 35 43 67 12 11 33 93 54 53
26 18 86 70 84 14 31 99 86 30
堆排序：
11 12 14 18 26 30 31 33 35 37
43 53 54 67 70 84 86 86 93 99
move：173 compare：122
n=100，n=500的排序结果省略。
(4)比较和移动次数的对比分析
1)比较次数
| 排序算法 | n=20 | n=100 | n=500 | 理论分析次数 |
| 直接插入排序 | 112 | 2588 | 62859 | O(n2) |
| 直接选择排序 | 190 | 4950 | 124750 | O(n2) |
| 冒泡排序 | 175 | 4830 | 124729 | O(n2) |
| Shell排序 | 87 | 848 | 6256 | O(n1.3) |
| 快速排序 | 64 | 617 | 4957 | O(nlog2n) |
| 堆排序 | 122 | 1023 | 7417 | O(nlog2n) |
2)移动次数
| 排序算法 | n=20 | n=100 | n=500 | 理论分析次数 |
| 直接插入排序 | 132 | 2685 | 63352 | O(n2) |
| 直接选择排序 | 54 | 285 | 1479 | O(n2) |
| 冒泡排序 | 351 | 7752 | 187080 | O(n2) |
| Shell排序 | 161 | 1391 | 10016 | O(n1.3) |
| 快速排序 | 24 | 207 | 1616 | O(nlog2n) |
| 堆排序 | 173 | 1065 | 6528 | O(nlog2n) |
结论：从n=500的测试结果可以看出，对随机输入的排序码花费的时间代价有以下的结论。
比较次数：快速排序＜Shell排序＜堆排序＜直接插入排序＜冒泡排序＜直接选择排序。
移动次数：直接选择排序＜快速排序＜堆排序＜shell排序＜直接插入排序＜冒泡排序。
如果以一次移动相当于两次比较的时间计算，折合成移动次数的时间代价如下表所示：