学习JAVA的第十二天（基础）

目录

算法

查找算法

基本查找（顺序查找）

二分查找（折半查找）

分块查找

 排序算法

冒泡排序

选择排序

插入排序

快速排序

递归算法 

---

 

算法

                        算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

---

查找算法

基本查找（顺序查找）

关键：

                        从0索引开始依次向后查找

方法：

 public static boolean basicSearch(int[] arr,int number) {
        //基本查找  遍历数组查找所需结果
        for (int i = 0; i < arr.length; i++) {
            if(number == arr[i]){
                return true;
            }
        }
        return false;
    }
 
}

二分查找（折半查找）

关键：

                        数组中的数据是有序的

                        每次排除一半的查找范围，节省查找次数

方法：

    public static int BinarySearch(int[] arr,int number)  {
        //定义变量确定查找范围 最小肯定是0索引的
        int min = 0;
        //最大的索引是数组长度-1
        int max = arr.length-1;
        //开始循环查找数据，利用while循环，查找出索引直接返回结果
        while(true){
            if(min > max){
                //返回-1，调用时可以将-1与0作比较，得出数据索引是否存在
                return -1;
            }
            //中间位置
            int mid = (min + max) / 2;
            //arr[mid]>number
            if(arr[mid]>number){
                max = mid - 1;
            }//arr[mid]<number
            else if(arr[mid]<number){
                min = mid + 1;
 
            }else{
                return mid;
            }
        }
 
    }

分块查找

关键：

                                块内无序，块间有序。

                                一般分块是按照数组长度的开根号

                                具体问题，具体分析 

方法：

//判断number在哪个块中
    private static int findIndexBlock(Block[] bArr,int number){
        //循环判断number在哪个块中
        for (int i = 0; i < bArr.length; i++) {
            if(number <= bArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }

    //利用分块查找获取索引
    private static int getIndex(Block[] bArr,int[] arr,int number){
        int indexBlock = findIndexBlock(bArr,number);
 
        //数据不在数组中
        if(indexBlock == -1){
            return -1;
        }
        //数据在数组中  刚才获取了数据所属块的索引
        int startIndex = bArr[indexBlock].getStartIndex();
        int endIndex = bArr[indexBlock].getEndIndex();
 
        //遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        return -1;
 
 
    }

 排序算法

冒泡排序

关键：

                                将相邻的数据进行比较，小的放前面，大的放后面。

方法：

      for(int i = 0; i < arr.length - 1; i++){
            for (int j = 0; j < arr.length - 1-i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }

选择排序

关键 ：

                           从0索引开始，用每个索引的元素与后面依次比较，小的放前面，大的放后面。

方法：

        //循环次数
        for(int i = 0; i < arr.length-1;i++){
            //从哪个索引开始比较
            for (int j = 1+i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j ];
                    arr[j ] = tmp;
                }
            }
        }

插入排序

关键：

                         将0索引到n索引看成有序的，n+1到最大索引是无序的。遍历无序数据，将其插入有序数据的合适位置

方法：

//确定无序数据的开始索引，依次插入有序数据中
        for (int i = startIndex; i < arr.length; i++) {
            int j = i;
            //相当于依次向左比较，直至到0索引为止
            while(j > 0 && arr[j] < arr[j-1]){
                int tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
                j--;
            }
 
 
        }

快速排序

关键：

                        将0索引的数据作为基准数，左边都是比基准数小的，右边都是比基准数大的

方法：

 public static void QuickSort(int[] arr, int startIndex, int endIndex) {
        //定义两个查找的范围 start~end
        int start = startIndex;
        int end = endIndex;
        //递归的出口
        if(end < start){
            return;
        }
        //0索引为基准数
        int baseNumber = arr[startIndex];
 
 
        while(end != start){
            while (true) {
                if (start >= end || arr[end] < baseNumber) {
                    break;
                }
                end--;
            }
            while (true) {
                if (start >= end || arr[start] > baseNumber) {
                    break;
                }
                start++;
            }
 
 
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
        }
        int tmp = arr[start];
        arr[start] = arr[startIndex];
        arr[startIndex] = tmp;
        //递归条件
        QuickSort(arr,startIndex,start-1);
        QuickSort(arr,start+1,endIndex);
 
 
    }

递归算法 

                方法中调用方法本身的现象

关键：

                递归算法一定要有出口，否则内存会溢出

                以大化小解决问题

方法：

   //简单的累加递归
 public static int Recursion(int number) {
       if(number == 1){
           return 1;
       }
       return number+Recursion(number-1);
    }

         

    //简单的求阶乘的递归
    public static int getNumber(int number) {
        if(number == 1){
            return 1;
        }
        return number * getNumber(number-1);
 
    }