快速排序

核心思想：分治
稳定性：不稳定。

确定分界点： left、right、mid、随机
调整区间左边的都是小于等于x右边都是大约等于x
- 开连个区间，分别保存小于x，和大约x的，循环遍历完，再把他们放到原数组里来。
递归处理左右两边

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = sc.nextInt();
        }

        quick_sort(nums, 0, count - 1);
        StringBuilder builder = new StringBuilder();
        for (int i : nums) {
            builder.append(i + " ");
        }
        builder.delete(builder.length() - 1, builder.length());
        System.out.print(builder.toString());
    }
//模板记忆
    private static void quick_sort(int[] nums, int left, int right) {

        if (left >= right) return;
        int x = nums[left], i = left - 1, j = right + 1;
        while(i < j) {
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j) {
                int temp = nums[i];
                nums[i]  = nums[j];
                nums[j] = temp;
            }
        }
        //为什么用j 不用i 因为选取的数是左边的，在有序的情况下会产生无限递归。
        //如果这里非得写i 上边的left 就要改成right；要不然会出现边界问题。
        quick_sort(nums, left, j);
        quick_sort(nums, j + 1, right);
    }


}

归并排序

核心思想分治

确定分界点 mid = (l + r) / 2
递归左边和右边
归并合二为一

import java.util.Scanner;

public class Main {

    private static   int[] temp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        temp = new int[n];
        merge_sort(nums, 0, n - 1);
        StringBuilder builder = new StringBuilder();
        for (int i : nums) {
            builder.append(i + " ");
        }
        builder.delete(builder.length() - 1, builder.length());
        System.out.println(builder.toString());
    }
//重点模板要记忆的
    private static void merge_sort(int[] nums, int left, int right) {

        if (left >=  right) {
            return;
        }
        // >>1 相当于除以二， 而且 + 优先级大于>> 相当于 (left + right) / 2;
        //分界点
        int mid = left + right >> 1;
        //向下递归
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        //归并处理 ,两个指针代表两个有序的开始
        int k = 0, i = left, j = mid + 1;
        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else  {
                temp[k++] = nums[j++];
            }
        }
        //两边的数组有可能有的没有遍历完
        while(i <= mid) {
            temp[k++] = nums[i++];
        }
        while(j <= right) {
            temp[k++] = nums[j++];
        }
        //最后将临时数组的有序数据copy到原来数组上
        for (i = left, j = 0;  i <= right; i++, j++)
            nums[i] = temp[j];
    }


}

二分

整数二分

有单调性的一定能二分，不单调也有可能二分
二分的本质是存在一个边界，左半边不满足这个性质，右半边满足这个性质，我们要找这个性质，将区间一分为二，一般满足一半不满足，当然这个边界有可能不是一个值，就是一个区间
图片说明

大致过程
图片说明
为什么当区间 l = mid 的时候需要将mid + 1
因为除数向下取整如果 l = r - 1 如果不加一 mid 将一直等于left 会造成死循环。
上边两种方式一种是求红点，一个是求绿点。左边界，右边界。
自己写check函数就好。
【二分的时候答案已经在区间里面，二分最后肯定会求出来一个解一定会找到边界的，只不过答案可能不是答案要求的】

//模板
boolean check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
//终止条件 l 和 r 相等的。
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

789. 数的范围(acwing中的题目)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        while (m-- != 0) {
            int x = sc.nextInt();
            int left = 0, right = n - 1; //都是闭区间
            //左边界
            while (left < right) { //最终相等两个数
                int mid =  left + right >> 1;
                if (arr[mid] >= x)
                    right = mid;
                else
                    left = mid + 1;
            }
            // 寻求左边界，如果这个数不存在，找到的这个数是第一个大于x的数
            // 寻求右边界，如果这个数不存在，找到的这个数是第一个小于的数
            if (arr[left] != x)
                System.out.println("-1 -1");
            else {
                System.out.print(left + " ");
                left = 0;
                right = n - 1;
                while (left < right) {
                    int mid = left + right + 1 >> 1;
                    if (arr[mid] <= x)
                        left = mid; //遇到left = mid 你就要将mid转换成+1的形式
                    else
                        right = mid - 1;
                }
                System.out.println(left);

            }
        }
    }


}

leetcode 69 x的平方根，利用的就是查找右边界。<= 的那个数。
class Solution {
    public int mySqrt(int x) {
        long l = 0;
        long r = x;
        while(l < r) {
            long mid = (r + l + 1) / 2;
            if (mid * mid <= x) {
                l = mid;
            }else {
                r = mid - 1;
            }
        }
        return (int)l;
    }
}

浮点数二分

和整数二分差不多，甚至于简单一些，不用考虑边界问题，不用再left的时候进行加一
答案要在搜索的区间内
最后根据区间的范围大小确定自己找到了这个数，只要这个区间足够的小，我们就找到了这个数。

高精度运算

数字特别大的运算【这里只讲大整数】

存储。我们将数字保存到数组中，个位在第一位，从0开始往后位数越大，为什么这样存，保证了再遇到进位的时候在数组后面加一位就好，如果高位放在前面，进位就需要整体平移。
模拟运算。

ACwing基础班-第一章基础算法

快速排序

归并排序

二分

整数二分

浮点数二分

高精度运算