数据结构实现

（一）二分法查找
二分法查找其实就是折半查找，一种效率较高的查找方法。针对有序数组来查找的。
主要思想是：（设查找的数组期间为array[low, high]）
（1）确定该期间的中间位置K
（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：
a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]
b.array[k]<T 类似上面查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半。递归找，即可。

时间复杂度:O(log2n);

public class BubbleTest
{
public static int binary(int[] array, int value)
{
int low = 0;
int high = array.length - 1;
while(low <= high)
{
int middle = (low + high) / 2;
if(value == array[middle])
{
return middle;
}
if(value > array[middle])
{
low = middle + 1;
}
if(value < array[middle])
{
high = middle - 1;
}
}
return -1;
}
public static void main(String[] args)
{
int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int value = binary(a, 9);
System.out.println(value);
}
}

（二）快速排序

（二）快速排序算法
快速排序是尽量避免额外计算的极好例子.其工作方式是在数组中划分出小的和大的元素
基本思想是：
从数组中取出一个元素作为基准值
把其他元素分为两组：
“小的”是那些小于基准值的元素。
“大的”是那些大于基准值的元素，
递归对这两个组做排序。
快速排序快速的原因在于：一旦知道了某个元素比基准值小，它就不需要在与那些大的元素比较。而大的元素也不需要在与小的元素比较，这个性质使快速排序比简单排序、冒泡排序快的多。

时间复杂度：O（nlogn）

public static void quickSort(int a[], int start, int end){
        int i,j;
        i = start;
        j = end;
        if((a==null)||(a.length==0))
            return;
        while(i<j){
            while(i<j&&a[i]<=a[j])     //以数组start下标的数据为key，右侧扫描
                j--;
            if(i<j){                   //右侧扫描，找出第一个比key小的，交换位置 
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            while(i<j&&a[i]<a[j])    //左侧扫描（此时a[j]中存储着key值）
                i++;
            if(i<j){                 //找出第一个比key大的，交换位置
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        if(i-start>1){                //递归调用，把key前面的完成排序
            quickSort(a,0,i-1);
        }
        if(end-j>1){
            quickSort(a,j+1,end);    //递归调用，把key后面的完成排序
 
        }
    }