public class A01_BasicSearchDemo1 {
    public static void main(String[] args) {
        //基本查找/順序查找
        //核心：
        //從0索引開(kāi)始挨個(gè)往后查找

        //需求：定義一個(gè)方法利用基本查找，查詢某個(gè)元素是否存在
        //數(shù)據(jù)如下：{131, 127, 147, 81, 103, 23, 7, 79}


        int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};
        int number = 82;
        System.out.println(basicSearch(arr, number));

    }

    //參數(shù)：
    //一：數(shù)組
    //二：要查找的元素

    //返回值：
    //元素是否存在
    public static boolean basicSearch(int[] arr, int number){
        //利用基本查找來(lái)查找number在數(shù)組中是否存在
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number){
                return true;
            }
        }
        return false;
    }
}

package com.itheima.search;

public class A02_BinarySearchDemo1 {
    public static void main(String[] args) {
        //二分查找/折半查找
        //核心：
        //每次排除一半的查找范圍

        //需求：定義一個(gè)方法利用二分查找，查詢某個(gè)元素在數(shù)組中的索引
        //數(shù)據(jù)如下：{7, 23, 79, 81, 103, 127, 131, 147}

        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(binarySearch(arr, 150));
    }

    public static int binarySearch(int[] arr, int number){
        //1.定義兩個(gè)變量記錄要查找的范圍
        int min = 0;
        int max = arr.length - 1;

        //2.利用循環(huán)不斷的去找要查找的數(shù)據(jù)
        while(true){
            if(min > max){
                return -1;
            }
            //3.找到min和max的中間位置
            int mid = (min + max) / 2;
            //4.拿著mid指向的元素跟要查找的元素進(jìn)行比較
            if(arr[mid] > number){
                //4.1 number在mid的左邊
                //min不變，max = mid - 1；
                max = mid - 1;
            }else if(arr[mid] < number){
                //4.2 number在mid的右邊
                //max不變，min = mid + 1;
                min = mid + 1;
            }else{
                //4.3 number跟mid指向的元素一樣
                //找到了
                return mid;
            }

        }
    }
}

public class FeiBoSearchDemo {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(search(arr, 1234));
    }

    public static int[] getFeiBo() {
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }

    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        //表示斐波那契數(shù)分割數(shù)的下標(biāo)值
        int index = 0;
        int mid = 0;
        //調(diào)用斐波那契數(shù)列
        int[] f = getFeiBo();
        //獲取斐波那契分割數(shù)值的下標(biāo)
        while (high > (f[index] - 1)) {
            index++;
        }
        //因?yàn)閒[k]值可能大于a的長(zhǎng)度，因此需要使用Arrays工具類(lèi)，構(gòu)造一個(gè)新法數(shù)組，并指向temp[],不足的部分會(huì)使用0補(bǔ)齊
        int[] temp = Arrays.copyOf(arr, f[index]);
        //實(shí)際需要使用arr數(shù)組的最后一個(gè)數(shù)來(lái)填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while循環(huán)處理，找到key值
        while (low <= high) {
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {//向數(shù)組的前面部分進(jìn)行查找
                high = mid - 1;
                /*
                  對(duì)k--進(jìn)行理解
                  1.全部元素=前面的元素+后面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因?yàn)榍懊嬗衚-1個(gè)元素沒(méi)所以可以繼續(xù)分為f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面繼續(xù)查找k--
                  即下次循環(huán),mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {//向數(shù)組的后面的部分進(jìn)行查找
                low = mid + 1;
                index -= 2;
            } else {//找到了
                //需要確定返回的是哪個(gè)下標(biāo)
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

package com.itheima.search;

public class A03_BlockSearchDemo {
    public static void main(String[] args) {
        /*
            分塊查找
            核心思想：
                塊內(nèi)無(wú)序，塊間有序
            實(shí)現(xiàn)步驟：
                1.創(chuàng)建數(shù)組blockArr存放每一個(gè)塊對(duì)象的信息
                2.先查找blockArr確定要查找的數(shù)據(jù)屬于哪一塊
                3.再單獨(dú)遍歷這一塊數(shù)據(jù)即可
        */
        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //創(chuàng)建三個(gè)塊的對(duì)象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定義數(shù)組用來(lái)管理三個(gè)塊的對(duì)象（索引表）
        Block[] blockArr = {b1,b2,b3};

        //定義一個(gè)變量用來(lái)記錄要查找的元素
        int number = 37;

        //調(diào)用方法，傳遞索引表，數(shù)組，要查找的元素
        int index = getIndex(blockArr,arr,number);

        //打印一下
        System.out.println(index);



    }

    //利用分塊查找的原理，查詢number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.確定number是在那一塊當(dāng)中
        int indexBlock = findIndexBlock(blockArr, number);

        if(indexBlock == -1){
            //表示number不在數(shù)組當(dāng)中
            return -1;
        }

        //2.獲取這一塊的起始索引和結(jié)束索引   --- 30
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        //3.遍歷
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        return -1;
    }


    //定義一個(gè)方法，用來(lái)確定number在哪一塊當(dāng)中
    public static int findIndexBlock(Block[] blockArr,int number){ //100


        //從0索引開(kāi)始遍歷blockArr，如果number小于max，那么就表示number是在這一塊當(dāng)中的
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }



}

class Block{
    private int max;//最大值
    private int startIndex;//起始索引
    private int endIndex;//結(jié)束索引


    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 獲取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 設(shè)置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 獲取
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 設(shè)置
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 獲取
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 設(shè)置
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

public class A01_BubbleDemo {
    public static void main(String[] args) {
        /*
            冒泡排序：
            核心思想：
            1，相鄰的元素兩兩比較，大的放右邊，小的放左邊。
            2，第一輪比較完畢之后，最大值就已經(jīng)確定，第二輪可以少循環(huán)一次，后面以此類(lèi)推。
            3，如果數(shù)組中有n個(gè)數(shù)據(jù)，總共我們只要執(zhí)行n-1輪的代碼就可以。
        */


        //1.定義數(shù)組
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用冒泡排序?qū)?shù)組中的數(shù)據(jù)變成 1 2 3 4 5

        //外循環(huán)：表示我要執(zhí)行多少輪。 如果有n個(gè)數(shù)據(jù)，那么執(zhí)行n - 1 輪
        for (int i = 0; i < arr.length - 1; i++) {
            //內(nèi)循環(huán)：每一輪中我如何比較數(shù)據(jù)并找到當(dāng)前的最大值
            //-1：為了防止索引越界
            //-i：提高效率，每一輪執(zhí)行的次數(shù)應(yīng)該比上一輪少一次。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //i 依次表示數(shù)組中的每一個(gè)索引：0 1 2 3 4
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        printArr(arr);




    }

    private static void printArr(int[] arr) {
        //3.遍歷數(shù)組
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

public class A02_SelectionDemo {
    public static void main(String[] args) {

        /*
            選擇排序：
                1，從0索引開(kāi)始，跟后面的元素一一比較。
                2，小的放前面，大的放后面。
                3，第一次循環(huán)結(jié)束后，最小的數(shù)據(jù)已經(jīng)確定。
                4，第二次循環(huán)從1索引開(kāi)始以此類(lèi)推。

         */


        //1.定義數(shù)組
        int[] arr = {2, 4, 5, 3, 1};


        //2.利用選擇排序讓數(shù)組變成 1 2 3 4 5
       /* //第一輪：
        //從0索引開(kāi)始，跟后面的元素一一比較。
        for (int i = 0 + 1; i < arr.length; i++) {
            //拿著0索引跟后面的數(shù)據(jù)進(jìn)行比較
            if(arr[0] > arr[i]){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
            }
        }*/

        //最終代碼：
        //外循環(huán)：幾輪
        //i:表示這一輪中，我拿著哪個(gè)索引上的數(shù)據(jù)跟后面的數(shù)據(jù)進(jìn)行比較并交換
        for (int i = 0; i < arr.length -1; i++) {
            //內(nèi)循環(huán)：每一輪我要干什么事情？
            //拿著i跟i后面的數(shù)據(jù)進(jìn)行比較交換
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }


        printArr(arr);


    }
    private static void printArr(int[] arr) {
        //3.遍歷數(shù)組
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

package com.itheima.mysort;


public class A03_InsertDemo {
    public static void main(String[] args) {
        /*
            插入排序：
                將0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一個(gè)當(dāng)成是無(wú)序的。
                遍歷無(wú)序的數(shù)據(jù)，將遍歷到的元素插入有序序列中適當(dāng)?shù)奈恢茫缬龅较嗤瑪?shù)據(jù)，插在后面。
                N的范圍：0~最大索引

        */
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到無(wú)序的哪一組數(shù)組是從哪個(gè)索引開(kāi)始的。  2
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i + 1]){
                startIndex = i + 1;
                break;
            }
        }

        //2.遍歷從startIndex開(kāi)始到最后一個(gè)元素，依次得到無(wú)序的哪一組數(shù)據(jù)中的每一個(gè)元素
        for (int i = startIndex; i < arr.length; i++) {
            //問(wèn)題：如何把遍歷到的數(shù)據(jù)，插入到前面有序的這一組當(dāng)中

            //記錄當(dāng)前要插入數(shù)據(jù)的索引
            int j = i;

            while(j > 0 && arr[j] < arr[j - 1]){
                //交換位置
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }

        }
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        //3.遍歷數(shù)組
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

package com.itheima.mysort;

import java.util.Arrays;

public class A05_QuickSortDemo {
   public static void main(String[] args) {
       System.out.println(Integer.MAX_VALUE);
       System.out.println(Integer.MIN_VALUE);
     /*
       快速排序：
           第一輪：以0索引的數(shù)字為基準(zhǔn)數(shù)，確定基準(zhǔn)數(shù)在數(shù)組中正確的位置。
           比基準(zhǔn)數(shù)小的全部在左邊，比基準(zhǔn)數(shù)大的全部在右邊。
           后面以此類(lèi)推。
     */

       int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};


       //int[] arr = new int[1000000];

      /* Random r = new Random();
       for (int i = 0; i < arr.length; i++) {
           arr[i] = r.nextInt();
       }*/