数据结构与算法(四,分治法和快排)

分治法

• 思想:
  分治法的前提条件是数列已经是有序的,当在有序数列中查找一个数的位置时,首先取数列中间位置的值,与要查找的值比较,若arr[mid]>key,则low = mid+1,否则height = mid-1,然后继续取新的mid,直到height-low<=0(说明数列中没有key值,此时返回-(low+1)或者-1),或者arr[mid]=key(说明已找到key值,位置为mid)
• 注意:
  在取mid值时,要注意闭包思想,也就是在数学中的左闭又开,这样才能形成一个完整的数列
  即:mid=(low+(height-1))/2
• 代码

public int binarySearch(int[] array,int key,int fromIndex,int toIndex){
        if (fromIndex<0||toIndex>array.length-1){
            return -1;
        }else {
            int low = fromIndex;
            int height = toIndex-1;
            while(low<=height){
                int mid = (low+height)/2;
                if (array[mid]>key){
                    height = mid-1;
                }else if (array[mid]<key){
                    low = mid+1;
                }else {
                    return mid;
                }
            }
            return -(low+1);
        }
    }

快排

• 思想:
  在数列中选取一个数,将数列中的数与之比较大小,大的放右边,小的放左边,这样一轮比较下来,该数的左边全部比他小,右边全部比他大.然后再取该数为新的low和height的位置,即(起点0)low--height(该数的位置) (该数的位置)low---height(终点arr[lenght-1])继续上述步骤,直到low>=height,此时,这个数列就是有序的
• 步骤:
  1.取数列第0位作为目标值x
  2.取数列第0位和数列最后一位为low和height,
  3.从height开始依次往前比较,若arr[height]>x,height--,若arr[height]<x.
  arr[low] = arr[height],low++,然后开始4
  4.从low开始依次往后比较,若arr[low]<x,low++,若arr[low]>x,arr[height] = arr[low],height--,然后开始3
  5.当low=height时.x的位置已确定,x左边小于x,右边大于x,此时,第一轮比较完毕,将x值赋值给arr[low],arr[low] = x
  6.分别与x的位置为height和low,继续执行该算法,直到low>=height
• 时间复杂度
  n为数组长度
  则每次最多比较n次
  比较log2n轮
  即O[n] = n*log2n
• 代码

 public void quickSort(int[] array,int begain,int end){

        if (end-begain<=0){
            return;
        }

        int low = begain;
        int height = end;
        int x = array[begain];
        boolean direction = true;
        L1:
        while (low<height){
            if (direction){
                for (int i = height; i > low; i--) {
                    if (array[i]<x){
                        array[low++] = array[i];
                        height = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                height = low;
            }else {
                for (int i = low; i <height; i++) {
                    if (array[i]>x){
                        array[height--] = array[i];
                        low = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                low = height;
            }
        }

        array[low] = x;
        quickSort(array,begain,low-1);
        quickSort(array,low+1,end);
    }