Java應用二分法停止查找和排序的示例。本站提示廣大學習愛好者：（Java應用二分法停止查找和排序的示例）文章只能為提供參考，不一定能成為您想要的結果。以下是Java應用二分法停止查找和排序的示例正文
完成二分法查找
二分法查找，須要數組內是一個有序的序列
二分查找比線性查找：數組的元素數越多，效力進步的越顯著
二分查找的效力表現：O(log2N) N在2的M次冪規模，那查找的次數最年夜就是M, log2N表現2的M次冪等於N, 省略常數，簡寫成O(logN)
若有一個200個元素的有序數組，那末二分查找的最年夜次數：
2^7=128, 2^8=256, 可以看出7次冪達不到200，8次冪包含， 所以最年夜查找次數就等於8
//輪回，二分查找
static int binarySearch(int[] array, int data) {
int start = 0;
int end = array.length - 1;
int mid = -1;
while (start <= end) {
System.out.println("查找次數");
mid = (start + end) >>> 1;
if (array[mid] < data) {
start = mid + 1;
} else if (array[mid] > data) {
end = mid - 1;
} else {
return mid;
}
System.out.println("start=" + start+",end="+end+",mid="+mid);
}
return -1;
}
//遞歸二分查找 初始start=0, end = array.length - 1
static int binarySearch4Recursion(int[] array, int data, int start, int end) {
int mid = -1;
System.out.println("查找次數");
if (start > end) {
return mid;
}
mid = (start + end) >>> 1;
if (array[mid] < data) {
return binarySearch4Recursion(array, data, mid + 1, end);
} else if (array[mid] > data) {
return binarySearch4Recursion(array, data, start, mid - 1);
} else {
return mid;
}
}
二分法拔出排序
設有一個序列a[0],a[1]...a[n];個中a[i-1]前是曾經有序的,當拔出時a[i]時,應用二分法搜刮a[i]拔出的地位
效力：O(N^2)，關於初始根本有序的序列，效力上不如直接拔出排序；關於隨機無序的序列，效力比直接拔出排序要高
/*
* 二分(折半)拔出排序
* 設有一個序列a[0],a[1]...a[n];個中a[i-1]前是曾經有序的,當拔出時a[i]時,應用二分法搜刮a[i]拔出的地位
*/
public class BinaryInsertSort {
public static void main(String[] args) {
int len = 10;
int[] ary = new int[len];
Random random = new Random();
for (int j = 0; j < len; j++) {
ary[j] = random.nextInt(1000);
}
binaryInsert(ary);
/*
* 龐雜度剖析： 最好情形，即都曾經排好序，則無需右移，此不時間龐雜度為：O(n lg n) 最差情形，全體逆序，此時龐雜度為O(n^2)
* 沒法將最差情形的龐雜度晉升到O(n|logn)。
*/
// 打印數組
printArray(ary);
}
/**
* 拔出排序
* @param ary
*/
private static void binaryInsert(int[] ary) {
int setValueCount = 0;
// 從數組第二個元素開端排序，由於第一個元素自己確定是曾經排好序的
for (int j = 1; j < ary.length; j++) {// 龐雜度 n
// 保留以後值
int key = ary[j];
// ∆ 應用二分查找定位拔出地位
// int index = binarySearchAsc(ary, ary[j], 0, j - 1);// 龐雜度：O(logn)
// int index = binarySearchDesc(ary, ary[j], 0, j - 1);// 龐雜度：O(logn)
int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// 龐雜度：O(logn)
printArray(ary);
System.out.println("第" + j +"個索引上的元素要拔出的地位是：" + index);
// 將目的拔出地位，同時右移目的地位左邊的元素
for (int i = j; i > index; i--) {// 龐雜度,最差情形：(n-1)+(n-2)+...+n/2=O(n^2)
ary[i] = ary[i - 1]; //i-1 <==> index
setValueCount++;
}
ary[index] = key;
setValueCount++;
}
System.out.println("\n 設值次數(setValueCount)=====> " + setValueCount);
}
/**
* 二分查找 升序 遞歸
*
* @param ary
* 給定已排序的待查數組
* @param target
* 查找目的
* @param from
* 以後查找的規模終點
* @param to
* 以後查找的前往起點
* @return 前往目的在數組中，按次序應在的地位
*/
private static int binarySearchAsc(int[] ary, int target, int from, int to) {
int range = to - from;
// 假如規模年夜於0，即存在兩個以上的元素，則持續拆分
if (range > 0) {
// 選定中央位
int mid = (to + from) / 2;
// 假如臨界位不知足，則持續二分查找
if (ary[mid] > target) {
/*
* mid > target, 升序規矩，target較小，應交流地位 前置， 即target定位在mid地位上，
* 依據 查找思惟， 從from到 mid-1以為有序， 所以to=mid-1
*/
return binarySearchAsc(ary, target, from, mid - 1);
} else {
/*
* mid < target, 升序規矩，target較年夜，不交流地位，查找比擬的肇端地位應為mid+1
*/
return binarySearchAsc(ary, target, mid + 1, to);
}
} else {
if (ary[from] > target) {//如 5,4, 要拔出的是4
return from;
} else {
return from + 1;
}
}
}
/**
* 二分查找 降序， 遞歸
*/
private static int binarySearchDesc(int[] ary, int target, int from, int to) {
int range = to - from;
if (range > 0) {
int mid = (from + to) >>> 1;
if (ary[mid] > target) {
return binarySearchDesc(ary, target, mid + 1, to);
} else {
return binarySearchDesc(ary, target, from, mid - 1);
}
} else {
if (ary[from] > target) {//如 5,4, 要拔出的是4
return from + 1;
} else {
return from;
}
}
}
/**
* 二分查找 降序， 非遞歸
*/
private static int binarySearchDesc2(int[] ary, int target, int from, int to) {
// while(from < to) {
for (; from < to; ) {
int mid = (from + to) >>> 1;
if (ary[mid] > target) {
from = mid + 1;
} else {
to = mid -1;
}
}
//from <==> to;
if (ary[from] > target) {//如 5,4, 要拔出的是4
return from + 1;
} else {
return from;
}
}
private static void printArray(int[] ary) {
for (int i : ary) {
System.out.print(i + " ");
}
}
}
打印
918 562 442 531 210 216 931 706 333 132 第1個索引上的元素要拔出的地位是：1 918 562 442 531 210 216 931 706 333 132 第2個索引上的元素要拔出的地位是：2 918 562 442 531 210 216 931 706 333 132 第3個索引上的元素要拔出的地位是：2 918 562 531 442 210 216 931 706 333 132 第4個索引上的元素要拔出的地位是：4 918 562 531 442 210 216 931 706 333 132 第5個索引上的元素要拔出的地位是：4 918 562 531 442 216 210 931 706 333 132 第6個索引上的元素要拔出的地位是：0 931 918 562 531 442 216 210 706 333 132 第7個索引上的元素要拔出的地位是：2 931 918 706 562 531 442 216 210 333 132 第8個索引上的元素要拔出的地位是：6 931 918 706 562 531 442 333 216 210 132 第9個索引上的元素要拔出的地位是：9
設值次數(setValueCount)=====> 24
931 918 706 562 531 442 333 216 210 132
