算法导论Java实现-二分插入排序（习题2.3-6）

1. package lhz.algorithm.chapter.two; 
2. /** 
3.  * “二分插入排序”，利用二分查找优化插入排序中的定位部分。 
4.  * 《算法导论》，习题2.3-6 
5.  *  Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in 
6.  * Section 2.1 uses a linear search to scan (backward) through the sorted 
7.  * subarray A[1  j - 1]. Can we use a binary search (see Exercise 2.3-5) 
8.  * instead to improve the overall worst-case running time of insertion sort to 
9.  * Θ(n lg n)? 
10.  * 本文地址:http://mushiqianmeng.blog.51cto.com/3970029/732333
11. *@author lihzh(苦逼coder) 
12.  */ 
13. public class InsertSortWithBinarySearch { 
14.      
15.     private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 }; 
16.  
17.     public static void main(String[] args) { 
18.         //从数组第二个元素开始排序，因为第一个元素本身肯定是已经排好序的 
19.         for (int j = 1; j < input.length; j++) {// 复杂度 n 
20.             //保存当前值 
21.             int key = input[j]; 
22.             //利用二分查找定位位置 
23.             int index = binarySearch(input, input[j], 0, j - 1);//复杂度：lgn 
24.             //将目标插入位置，同时右移目标位置右边的元素 
25.             for (int i = j; i > index ; i--) {//复杂度,最差情况：(n-1)+(n-2)+...+n/2=Θ(n^2) 
26.                 input[i] = input [i-1]; 
27.             } 
28.             input[index] = key; 
29.         } 
30.         /* 
31.          * 复杂度分析： 
32.          * 最佳情况，即都已经排好序，则无需右移，此时时间复杂度为：Θ(n lg n) 
33.          * 最差情况，全部逆序，此时复杂度为Θ(n^2) 
    
34.          * 所以针对2.3-6问题，无法将最差情况的复杂度提升到Θ(n lg n)。 
35.          */ 
36.         //打印数组 
37.         printArray(); 
38.     } 
39.      
40.     /** 
41.      * 二分查找 
42.      * @param input 给定已排序的待查数组 
43.      * @param target 查找目标 
44.      * @param from 当前查找的范围起点 
45.      * @param to 当前查找的返回终点 
46.      * @return 返回目标在数组中，按顺序应在的位置 
47.      */ 
48.     private static int binarySearch(int[] input, int target, int from, int to) { 
49.         int range = to - from; 
50.         //如果范围大于0，即存在两个以上的元素，则继续拆分 
51.         if (range > 0) { 
52.             //选定中间位 
53.             int mid = (to + from) / 2; 
54.             //如果临界位不满足，则继续二分查找 
55.             if (input[mid] > target) { 
56.                 return binarySearch(input,target,from,mid-1); 
57.             } else { 
58.                 return binarySearch(input,target,mid+1,to); 
59.             } 
60.         } else { 
61.             if (input[from] > target) { 
62.                 return from; 
63.             } else { 
64.                 return from + 1; 
65.                 } 
66.             } 
67.         } 
68.      
69.     private static void printArray() { 
70.         for (int i : input) { 
71.             System.out.print(i + " "); 
72.         } 
73.     } 
74.  
75. } 

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/732333，如需转载请自行联系原作者