Java

算法

递归

定义

递归是一种编程和算法设计的技术，在这种技术中，一个函数直接或间接地调用自身一次或多次。递归算法就是将一个大问题分解为一个或多个较小的相同类型的子问题，然后对这些子问题进行求解。递归算法的核心是把问题的解决方案定义为相同问题但规模更小的解决方案的函数。

递归通常有两个主要的部分组成:

  1. 基本情况：这是递归的终止条件，通常是一个或多个非常简单的情况可以直接求解不需要进一步的递归调用
  2. 递归情况：函数会把问题分解成一个或多个较小的问题，然后调用自身来就解决这些子问题

优缺点

  1. 优点：
    • 代码简洁易懂
    • 问题分解
    • 不需要循环结构
    • 适用于不确定深度问题
  2. 缺点
    • 效率低
    • 栈溢出风险
    • 调试困难
    • 空间复杂度
    • 可读性问题

二分查找

定义

二分查找是一种有效的查找算法，用于在已排序的数组中找到特定的元素，算法的基本思想是将数组分为两半，然后根据需要查找的值与中间元素的大小关系来确定下一步应查找哪一半

排序

冒泡排序

定义：是一种简单但效率较低的排序算法，它通过反复交换相邻的不按顺序的项。

插入排序

定义：插入排序的工作方式，就像排序一手扑克牌，从第一个元素开始，该算法逐渐构建一个有序的数组

工作原理：通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入

package com.leetcode;

public class Demo7 {
    public static void main(String[] args) {
        int[] arr ={1,5,6,8,7,9,2};
        sort(arr);
        for (int n:arr
             ) {
            System.out.print(n+" ");
        }
    }

    public static void sort(int[] arr){
        //i:待排序元素开始的位置
        for (int i = 1 ; i < arr.length;i++){
            int key = arr[i];//保持排序元素
            int j = i - 1;//从后向前指向已排序的元素
            while (j >=0 && arr[j] >key){
                arr[j+1] = arr[j];
                j = j-1;
            }
            //找到待排序的元素位置，插入元素
            arr[j+1] = key;
        }
    }
}

快速排序

快速排序是一种分组的排序算法，工作方式是将一个数组分为两个子数组，然后递归排序它们

partition分区方法：

负责把数组分为两个部分，一个所有元素都小于基准的部分，一个所有元素都大于基准的部分

  1. 他首先选择一个基准元素，在我们的案例中，基准元素是数组的最后一个元素
  2. 然后它遍历子数组将所有小于基准的元素移动到基准的左边
  3. 最后它将基准元素移动到其最终的位置，这样基准左边的所有元素都小于基准，右边的所有元素都大于基准
package com.leetcode;

public class Demo9 {

    public static void quickSort(int[] arr,int low,int high){
        if (low < high){
            int pi = partition(arr,low,high);

            quickSort(arr,low,pi-1);
            quickSort(arr,pi+1,high);
        }
    }
    public static int partition(int[] arr,int low,int high){
        //选择最后一个元素作为基准元素
        int pivot = arr[high];
        //初始化指针，用于追踪小于基准元素的最后一个位置
        int i = low-1;
        for (int j = low;j < high;j++){
            //如果当前元素小于基准
            if (arr[j] < pivot){
                //移动i指针，并交换arr[i]和arr[j]
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //把基准元素移动到其最终的位置(i+1)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        //返回基准元素的最终索引号
        return i+1;
    }
    public static void main(String[] args) {
        int[] arr = {5,9,7,8,6,3,1,4,2};
        quickSort(arr,0,arr.length-1);
        for (int n: arr
             ) {
            System.out.print(n+" ");
        }
    }
}