这里有新鲜出炉的 Java 并发编程示例,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要为大家详细介绍了 Java 经典排序算法之二分插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
一、折半插入排序(二分插入排序)
将直接插入排序中寻找 A[i] 的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。在处理 A[i] 时,A[0]……A[i-1] 已经按关键码值排好序。所谓折半比较,就是在插入 A[i] 时,取 A[i-1/2] 的关键码值与 A[i] 的关键码值进行比较,如果 A[i] 的关键码值小于 A[i-1/2] 的关键码值,则说明 A[i] 只能插入 A[0] 到 A[i-1/2] 之间,故可以在 A[0] 到 A[i-1/2-1] 之间继续使用折半比较;否则只能插入 A[i-1/2] 到 A[i-1] 之间,故可以在 A[i-1/2+1] 到 A[i-1] 之间继续使用折半比较。如此担负,直到最后能够确定插入的位置为止。一般在 A[k] 和 A[r] 之间采用折半,其中间结点为 A[k+r/2],经过一次比较即可排除一半纪录,把可能插入的区间减小了一半,故称为折半。执行折半插入排序的前提是文件纪录必须按顺序存储。
二、算法原理
折半插入排序的算法思想:
算法的基本过程:
(1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入 i 索引之间,反之,就是在刚开始的位置 到中间值的位置,这样很简单的完成了折半;
(2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2 1/4 1/8 ....... 快速的确定出第 i 个元素要插在什么地方;
(3)确定位置之后,将整个序列后移,并将元素插入到相应位置。
三、代码实现
- public class BinarySort {
- public static void binarySort(int[] source) {
- int i, j;
- int high, low, mid;
- int temp;
- for (i = 1; i < source.length; i++) {
- // 查找区上界
- low = 0;
- // 查找区下界
- high = i - 1;
- //将当前待插入记录保存在临时变量中
- temp = source[i];
- while (low <= high) {
- // 找出中间值
- // mid = (low + high) / 2;
- mid = (low + high) >> 1;
- //如果待插入记录比中间记录小
- if (temp<source[mid] ) {
- // 插入点在低半区
- high = mid - 1;
- } else {
- // 插入点在高半区
- low = mid + 1;
- }
- }
- //将前面所有大于当前待插入记录的记录后移
- for (j = i - 1; j >=low; j--) {
- source[j + 1] = source[j];
- }
- //将待插入记录回填到正确位置.
- source[low] = temp;
- System.out.print("第" + i + "趟排序:");
- printArray(source);
- }
- }
- private static void printArray(int[] source) {
- for (int i = 0; i < source.length; i++) {
- System.out.print("\t" + source[i]);
- }
- System.out.println();
- }
- public static void main(String[] args) {
- int source[] = new int[] { 12, 15, 9, 14, 4, 18, 23, 6 };
- System.out.print("初始关键字:");
- printArray(source);
- System.out.println("");
- binarySort(source);
- System.out.print("\n\n排序后结果:");
- printArray(source);
- }
- }
四、运行结果
- 初始关键字: 12 15 9 14 4 18 23 6
- 第1趟排序: 12 15 9 14 4 18 23 6
- 第2趟排序: 9 12 15 14 4 18 23 6
- 第3趟排序: 9 12 14 15 4 18 23 6
- 第4趟排序: 4 9 12 14 15 18 23 6
- 第5趟排序: 4 9 12 14 15 18 23 6
- 第6趟排序: 4 9 12 14 15 18 23 6
- 第7趟排序: 4 6 9 12 14 15 18 23
- 排序后结果: 4 6 9 12 14 15 18 23
来源: http://www.phperz.com/article/17/1224/357733.html