折半插入排序是直接插入排序的一种优化，他利用了直接插入排序中前面的元素已经完成排序的特点进行折中对比。他的效果与直接插入排序一样，但是速度更快。
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;
}
}
当前位置：
论坛首页 »
自由讨论区 »
Android, Python及开发编程讨论区
»
发起投票
技术讨论
加好友
发消息
2013-2-16 11:12:36 |
赞(
操作
