2.1 直接插入排序假设待排序的 n 个记录 {R0 ，R1，⋯，Rn} 顺序存放在数组中，直接插入法在插入记录 Ri(i=1，2，⋯，n-1)时，记录被划分为两个区间[R0,Ri-1] 和[Ri+1,Rn-1], 其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki 与Ki-1Ki-2 ，⋯，K0 依次比较，找出应该插入的位置，将记录Ri 插，然后将剩下的 i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过 i-1 趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。2.1.2 排序过程初始数据：10 3 25 20 8 第一趟：[ 3 10 ] 25 20 8 （将前两个数据排序）第二趟：[ 3 10 25] 20 8 （将 25 放入前面数据中的适当位置）第三趟：[ 3 10 20 25 ] 8 （将 20 放入适当的位置）第四趟：[ 3 8 10 20 25 ] （将 8 放入适当的位置）2.1.3 时间复杂度分析直接插入排序算法必须进行n-1 趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1) ，移动元素次数是2(n-1) 。因此最好情况下的时间复杂度就是O(n) 。最坏情况 ( 非递增 ) 下，最多比较i 次，因此需要的比较次数是：所以，时间复杂度为O(n2) 。2.2 直接选择排序待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟第n 个记录中找出关键码最小的记录与第n 个记录交换； 第二趟， 从第二个记录开始的， 2 -1 个记录中再选出关键码最小的记录与第二个记录交换；如此，第i 趟，则从第 i 个记录开始的n - i + l 个记录中选出关键码最小的记录与第i 个记录交换，直到所有记录排好序。2.2.2 排序过程初始数据[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 1 / 10 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 第六趟排序后13 27 38 49 49 76 [76 97] 第七趟排序后13 27 38 49 49 76 76 [ 97] 最后...
