假如我们要在一个数组中找一个关键字key,可能浮现在大家脑海中的第一个方法就是一个for()循环进行线性查找,但是这种查找方式在数组元素个数很大的时候会很低效。原因如下:
前提:
数组必须被提前排好序了
假设有n个元素长度的数组,进行第一次比较后还需要比较n/2个元素;第二次比较后,还需要比较n/2/2个元素;经过第k次比较后,还需要比较n/2^k个元素。当k=log2n时,还需要比较一个元素。所以总共的比较次数最坏情况下是:log2n+1。故时间复杂度为O(log2n+1)。
public class BinarySearch{ public static binarySearch(int[] a,int key){ int low = 0; int high = a.length; while(low >= high){ int mid = (low+high)/2; if(key > a[mid]){ low = mid + 1; } else if(key == a[mid]) return mid; else high = mid - 1; } return -low-1; //返回该查找应该插入的下标位置 } }
选择排序:
每次把第i个元素,与后面length-i个元素进行比较,把最小的元素位置和i号元素位置进行对调。
public static void selectSort(int[] a){ //将每个元素和后面的所有元素进行比较,最小的放在第一个 for(int i = 0;i < a.length-1;i++){ int currentMin = a[i]; int currentIndex = i; for(int j = i+1;j < a.length;j++){ if(currentMin > a[j]){ currentMin = a[j]; currentIndex = j; } } //最小元素不是本身则对调 if(j!=i){ a[j] = a[i]; a[i] = currentMin; } } }
如对本文有疑问, 点击进行留言回复!!
Java Class.forName()用法和newInstance()方法原理解析
网友评论