데이터 구조의 정렬 찾기

주로 2 분 검색, 삽입 값 찾기, 피 보 나치 찾기, 거품 정렬, 병합 정렬 알고리즘 설명 을 소개 합 니 다. 주석 병합 정렬 알고리즘 설명 을 참고 하 십시오.http://www.cnblogs.com/jillzhang/archive/2007/09/16/894936.html

/** *      *    ，    * @author asdc * */
public class Array {

     public final static int MAXSIZE = 20;

    /** *     ,  key   ，     <0       O(logN) * @param a * @param key * @return */
    public static int binarySearch(long[] a, long key){

        int lo = 0;//    
        int hi = a.length - 1;//    

        while(lo < hi){

            int mid = (lo + hi)/2;//    

            if(key == a[mid]){

                return mid;

            }else if(key > a[mid]){

                lo = mid + 1;

            }else if(key < a[mid]){

                hi = mid - 1;

            }

        }

        return -1;

    }

    /** *      * @param a * @param key * @return */
    public static int interpolationSearch(long[] a, long key){

        //              ，         ，                      ，            
        //       mid = (lo + hi)/2
        //     mid = lo/2 + hi/2 ----> mid = lo + hi/2 - lo/2 ----> mid = lo + (hi - lo)/2
        //mid = lo + (1/2)(hi - lo)  1/2       (key - a[lo])/(a[hi] - a[lo])
        //     mid = lo + (hi - lo) * (key - a[lo])/(a[hi] - a[lo])                      

        int lo = 0;//    
        int hi = a.length - 1;//    

        while(lo < hi){

            int mid = (int) (lo + (hi - lo) * (key - a[lo])/(a[hi] - a[lo]));//    

            if(key == a[mid]){

                return mid;

            }else if(key > a[mid]){

                lo = mid + 1;

            }else if(key < a[mid]){

                hi = mid - 1;

            }

        }

        return -1;

    }

    /** *        * @param a * @param key * @return */
    public static int fibonacciSearch(long[] a,long key){

        int lo = 0;
        int hi = a.length - 1;

        int[] f = fibonacci();

        int k = 0;//      

        while(a.length > f[k] - 1){

            k++;

        }

        long[] temp = new long[f[k] - 1];
        for(int i = 0; i < a.length; i++){

            temp[i] = a[i];

        }

        //      f[k]    
        //                 
        for (int i = a.length; i < f[k] - 1; i++) {  
            temp[i] = temp[hi];  
        }  

        while (lo <= hi) {  
            // low：     
            //      f[k-1]   ，     0   
            //  -1                
            int mid = lo + f[k - 1] - 1;  

            if (temp[mid] > key) {  
                //       ，       
                hi = mid - 1;  
                // （    ） = （    ）+（    ） 
                // f[k] = f[k-1] + f[k-2] 
                //        f[k-1]   ，   k = k-1 
                k = k - 1;  
            } else if (temp[mid] < key) {  
                //       ，       
                lo = mid + 1;  
                // （    ） = （    ）+（    ） 
                // f[k] = f[k-1] + f[k-2] 
                //        f[k-1]   ，   k = k-2 
                k = k - 2;  
            } else {  
                //              
                if (mid <= hi) {  
                    return mid;  
                } else {  
                    //                 
                    //        high        
                    return hi;  
                }  
            }  
        }  
        return -1;  


    } 


    /** *          * @return */
    public static int[] fibonacci(){

        int[] f = new int[MAXSIZE];
        f[0] = 1;
        f[1] = 1;
        for(int i = 2; i < MAXSIZE; i++){

            f[i] = f[i - 1] + f[i - 2];

        }

        return f;

    }

    //    
    //    ：          mid = (lo + hi)/2
    //    :         mid = lo + (hi - lo)*(key-a[lo])/(a[hi]-a[lo])
    //      :           mid = low + f[k-1] - 1          
    //          ，                 
    //                  ，    ，                


    /** *          * @param a * @return */
    public static void bubbleSort(long[] a){

        boolean isSort = true;//           

        for(int j = a.length - 1; j > 0; j--){

            for(int i = 0; i < j; i++){

                if(a[i] > a[i + 1]){

                    isSort = false;

                    //  
                    long temp = a[i + 1];
                    a[i + 1] = a[i];
                    a[i] = temp;

                }

            }

            if(isSort == true){

                break;

            }

        }

    }

    /** *         * @param a * @param lo * @param hi */
    public static void Merger(long[] a, int lo, int hi, int mid){

        long[] temp = new long[hi - lo];//              

        int indexA = lo;
        int indexB = mid;//      

        //                temp   
        int i = 0;
        while(indexA < mid && indexB < hi){

            if(a[indexA] > a[indexB]){

                temp[i++] = a[indexB++];

            }else{

                temp[i++] = a[indexA++];

            }

        }

        //       temp 
        while(indexA < mid){

            temp[i++] = a[indexA++];

        }
        while(indexB < hi){

            temp[i++] = a[indexB++];

        }

        //  a  
        for (int k2 = 0; k2 < temp.length; k2++) {  
            a[k2 + lo] = temp[k2];  
        }  


    }

    public static void MergerSort(long[] a, int lo, int hi){
        if (hi > lo) //hi - lo > 1
        {
            int mid = (lo + hi) / 2;
            System.out.println(" " + lo + "," + mid);
            MergerSort(a, lo, mid);
            System.out.println(" " + (mid+1) + "," + hi);
            MergerSort(a, mid + 1, hi);
            Merger(a, lo, hi, mid);
        }
    } 

}