首页 > 代码库 > 数据结构之排序算法Java实现（6）—— 插入类排序之折半插入排序算法
数据结构之排序算法Java实现（6）—— 插入类排序之折半插入排序算法
折半插入排序是对直接插入排序进行了改进，在寻找插入点时使用二分查找算法，提高了查询效率。
升序排序：
/**
* 折半插入排序
* 升序排序
*/
@Override
public <T extends Comparable<? super T>> void sortByAsc(T[] data) {
for(int i = 1;i < data.length;i++ ){
if(data[i].compareTo(data[i - 1]) < 0){
/**记录i的值*/
T temp = data[i];
/**记录搜索范围的左边界*/
int low = 0;
/**记录搜索范围的右边界*/
int high = i - 1;
while(low <= high){
/**记录中间位置*/
int mid = (high + low)/2;
/**比较中间位置数据和i处数据大小，以缩小搜索范围*/
if(data[mid].compareTo(temp) < 0){
low = mid + 1;
}else{
high = mid - 1;
}
}
/**移动low~i处数据整体向后移动*/
for(int j = i; j > low; j--){
data[j] = data[j - 1];
}
data[low] = temp;
}
}
}
降序排序：
/**
* 折半插入排序
* 降序排序
*/
@Override
public <T extends Comparable<? super T>> void sortByDesc(T[] data) {
for(int i = 1;i < data.length;i++ ){
if(data[i].compareTo(data[i - 1]) > 0){
/**记录i的值*/
T temp = data[i];
/**记录搜索范围的左边界*/
int low = 0;
/**记录搜索范围的右边界*/
int high = i - 1;
while(low <= high){
/**记录中间位置*/
int mid = (high + low)/2;
/**比较中间位置数据和i处数据大小，以缩小搜索范围*/
if(data[mid].compareTo(temp) > 0){
low = mid + 1;
}else{
high = mid - 1;
}
}
/**移动low~i处数据整体向后移动*/
for(int j = i; j > low; j--){
data[j] = data[j - 1];
}
data[low] = temp;
}
}
}
数据结构之排序算法Java实现（6）—— 插入类排序之折半插入排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。