[推荐]插入排序——折半插入排序_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3166 | 回复: 0   主题: [推荐]插入排序——折半插入排序        下一篇 
yi.liao
注册用户
等级:少校
经验:917
发帖:52
精华:4
注册:2013-1-31
状态:离线
发送短消息息给yi.liao 加好友    发送短消息息给yi.liao 发消息
发表于: IP:您无权察看 2013-2-16 11:12:36 | [全部帖] [楼主帖] 楼主

折半插入排序是直接插入排序的一种优化,他利用了直接插入排序中前面的元素已经完成排序的特点进行折中对比。他的效果与直接插入排序一样,但是速度更快。

publicclass 折半排序Demo {

publicstaticvoid main(String[] args) {
      // 1. 初始化一个无序数组
      int[] myArr = { 23, 35, 73, 27, 4, 77, 54, 84, 47, 56, 34, 32, 75, 32,
      31, 0, 99, 7, 54, 57 };


myArr = 折半排序(myArr);

for (int i : myArr) {
      System.out.print(i + " ");
}
System.out.println("");
}


privatestaticint[] 折半排序(int[] myArr) {

for (int n = 1; n < myArr.length; n++) {


int index = 找位置(myArr, 0, n, myArr[n]);

if (index != n) {// 如果需要挪位
      int tmpNum = myArr[n];
      for (int k = n; k > index; k--) {
            myArr[k] = myArr[k - 1];
      }
      myArr[index] = tmpNum;
}
}
return myArr;
}


privatestaticint 找位置(int[] tmpArr, int startIndex, int endIndex, int num) {

int index = 0;
// 获取折半元素的索引
int helfIndex = (endIndex - startIndex) / 2 + startIndex;
if (tmpArr[helfIndex] > num) {
      // 如果startIndex == endIndex,获得的折半元素就是最终对比元素,如果大于num,则返回折半的索引
      if (helfIndex == startIndex) {
            return startIndex;
      }


index = 找位置(tmpArr, startIndex, helfIndex, num);

} else {
      // 如果startIndex == endIndex,获得的折半元素就是最终对比元素,如果大于num,则返回折半后一位的索引
      if (helfIndex == startIndex) {
            return startIndex + 1;
      }


index = 找位置(tmpArr, helfIndex, endIndex, num);

}
return index;
}
}




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论