数据结构之折半插入排序图文详解及代码(C++实现)
问题:
对待排序的数组r[1..n]中的元素进行直接插入排序,得到一个有序的(从小到大)的数组r[1..n]。
算法思想:
1、设待排序的记录存放在数组r[1..n]中,r[1]是一个有序序列。
2、循环n-1次,每次使用折半查找法,查找r[i](i=2,..,n)在已排好的序列r[1..i-1]中的插入位置,然后将r[i]插入表长为i-1的序列r[1..i-1],直到将r[n]插入表长为n-1的有序序列r[1..n-1],最后得到一个表长为n的有序序列。
图解:
代码:
运行结果: