Java实现直接插入排序和折半插入排序算法示例

将待排序的记录Ri插入到已经排好序的记录R1，R2，……对于一个随机序列而言，就是从第二个元素开始，依次将这个元素插入到它之前的元素中的相应位置。第1次排序：将第2个元素插入到前边的有序列表，之后，这个序列的前2个元素就是有序的了。，R（N-1）已经排好序，所以在查找插入位置时可采用“折半查找”。2 算法实现：3 性能分析：3.1 空间复杂度：如上代码，使用了一个辅助单元key，空间复杂度为O3.2 时间复杂度：虽然折半查找减少了记录比较次数，但没有减少移动次数，因此时间复杂度同直接查找算法。