分治法(数据结构及算法09)

基本思想:

将一个规模为N的问题，分解成K个规模较小的子问题，这些子问题相互独立且月原问题性质相同。求解出子问题的解，合并得到原问题的解。

一、查找技术

1、顺序查找

如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。

2、二分查找

image.png

前题条件：数据已经排序
注意：设计成左闭右开--是一种区间无重复的思想random(０，１)等大量的数学函数for(int i=0;i<array.length;i++）

    /**
     * 二分查找
     */
    public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){
        int low=fromIndex;
        int high=toIndex-1;
        while(low<=high){
            int mid=(low+high)/2;//取中间
            int midVal=array[mid];
            if(key>midVal){//去右边找
                low=mid+1;
            }else if(key<midVal){//去左边找
                high=mid-1;
            }else{
                return mid;
            }
        }
        return -(low+1);//low+1表示找不到时停在了第low+1个元素的位置
    }

测试代码

        int array[] = {1,2,3,4,5,6,7,8};
        int index0 = binarySearch(array, 0, array.length, 0);
        int index1 = binarySearch(array, 0, array.length, 1);
        int index4 = binarySearch(array, 0, array.length, 4);
        int index8 = binarySearch(array, 0, array.length, 8);
        System.out.println("0的下标:"+index0);
        System.out.println("1的下标:"+index1);
        System.out.println("4的下标:"+index4);
        System.out.println("8的下标:"+index8);

打印结果

0的下标:-1
1的下标:0
4的下标:3
8的下标:7

二、快速排序（前序）

image.png

应用场景:数据量大并且是线性结构
短处:有大量重复数据的时候，性能不好,单向链式结构处理性能不好（一般来说，链式都不使用）

    //快速排序     31  21  59  68  12  40
    //    x=31
    public static void quickSort(int[] array,int begin,int end){
        if(end-begin<=0) return;
        int x=array[begin];
        int low=begin;//0
        int high=end;//5
        //由于会从两头取数据，需要一个方向
        boolean direction=true;
        L1:
        while(low<high){
            if(direction){//从右往左找
                for(int i=high;i>low;i--){
                    if(array[i]<=x){
                        array[low++]=array[I];
                        high=I;
                        direction=!direction;
                        continue L1;
                    }
                }
                high=low;//如果上面的if从未进入，让两个指针重合
            }else{
                for(int i=low;i<high;i++){
                    if(array[i]>=x){
                        array[high--]=array[I];
                        low=I;
                        direction=!direction;
                        continue L1;
                    }
                }
                low=high;
            }
        }
        //把最后找到的值 放入中间位置
        array[low]=x;
        //开始完成左右两边的操作
        quickSort(array,begin,low-1);
        quickSort(array,low+1,end);
    }

测试代码

        int arrays[] = {0,2,3,4,5,6,9,7,1};
        quickSort(arrays,0,arrays.length-1);
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i]+" ");
        }

打印结果

0 1 2 3 4 5 6 7 9 

三、归并排序(后序)

image.png

应用场景:数据量大并且有很多重复数据，链式结构
短处:需要空间大

public static void merge(int[] array,int left,int mid,int right){
        int leftSize=mid-left;
        int rightSize=right-mid+1;
        //生成数组
        int[] leftArray=new int[leftSize];
        int[] rightArray=new int[rightSize];
        //填充数据
        for(int i=left;i<mid;i++){
            leftArray[i-left]=array[i];
        }
        for(int i=mid;i<=right;i++){
            rightArray[i-mid]=array[i];
        }
        //合并
        int i=0;
        int j=0;
        int k=left;
        while(i<leftSize && j<rightSize){
            if(leftArray[i]<rightArray[j]){
                array[k]=leftArray[i];
                k++;i++;
            }else{
                array[k]=rightArray[j];
                k++;j++;
            }
        }
        while(i<leftSize){
            array[k]=leftArray[i];
            k++;i++;
        }
        while(j<rightSize){
            array[k]=rightArray[j];
            k++;j++;
        }
    }

public static void mergeSort(int array[],int left,int right){
        if(left==right){
            return;
        }else{
            int mid=(left+right)/2;
            mergeSort(array,left,mid);
            mergeSort(array,mid+1,right);
            merge(array,left,mid+1,right);
        }
    }

        int[] array=new int[]{2,1,6,4,3,9,8,10,7,5};
        mergeSort(array,0,array.length-1);
        for (int i : array) {
            System.out.print(i+" ");
        }

打印结果

1 2 3 4 5 6 7 8 9 10