Java 折半插入排序算法实例
折半插入排序是直接插入排序与折半查找二者的结合，仍然是将待排序元素插入到前面的有序序列，插入方式也是由后往前插，只不过直接插入排序是边比较边移位。而折半插入排序则是先通过折半查找找到位置后再一并移位，最终将待排序元素赋值到空出位置。
实例源码：
源代码：
执行
执行中...
x
1
/**2
* 折半插入排序 的实现 稳定算法3
* nowjava.com4
*/5
public class InsertSort {6
public static void main(String[] args) {7
// TODO Auto-generated method stub8
int a[] = { 3, 1, 5, 7, 2, 4, 9, 6 };9
new InsertSort().doInsertSort(a);10
}11
12
/**13
* 折半插入排序算法的实现14
*/15
private void doInsertSort(int[] a) {16
// TODO Auto-generated method stub17
System.out.println("—————折半插入排序算法—————");18
int n = a.length;19
int i, j;20
for (i = 1; i < n; i++) {21
/**22
* temp为本次循环待插入有序列表中的数 - nowjava.com23
*/24
int temp = a[i];25
int low = 0;26
int high = i - 1;27
/**28
* 寻找temp插入有序列表的正确位置，使用二分查找法29
*/30
while (low <= high) {31
/**32
* 有序数组的中间坐标，此时用于二分查找，减少查找次数33
*/34
int mid = (low + high) / 2;35
/**36
* 若有序数组的中间元素大于待排序元素，则有序序列向中间元素之前搜索，否则向后搜索37
*/38
if (a[mid] > temp) {39
high = mid - 1;40
} else {41
low = mid + 1;42
}43
}44
45
for (j = i - 1; j >= low; j--) {46
/**47
* 元素后移，为插入temp做准备48
*/49
a[j + 1] = a[j];50
}51
/**52
* 插入temp53
*/54
a[low] = temp;55
/**56
* 打印每次循环的结果57
*/58
print(a, n, i);59
}60
/**61
* 打印排序结果62
*/63
printResult(a, n);64
}65
66
/**67
* 打印排序的最终结果68
* 69
* @param a70
* @param n71
*/72
private void printResult(int[] a, int n) {73
System.out.print("最终排序结果：");74
for (int j = 0; j < n; j++) {75
System.out.print(" " + a[j]);76
}77
System.out.println();78
}79
80
/**81
* 打印排序的每次循环的结果82
* 83
* @param a84
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
- —————折半插入排序算法—————
- 第1次： 1 3 5 7 2 4 9 6
- 第2次： 1 3 5 7 2 4 9 6
- 第3次： 1 3 5 7 2 4 9 6
- 第4次： 1 2 3 5 7 4 9 6
- 第5次： 1 2 3 4 5 7 9 6
- 第6次： 1 2 3 4 5 7 9 6
- 第7次： 1 2 3 4 5 6 7 9
- 最终排序结果： 1 2 3 4 5 6 7 9
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java