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