快速排序->分治

图形：image.png

步骤：

1.确定分界点：q[l] , q[(l+r)/2] , q[r] , 或随机点
2.调整区间image.png
3.调用递归处理两段

模板：

当 int x = q[(l+r+1 >> 1)];或int x = q[r];时
quickSort(q , l , i - 1);
quickSort(q , i , r);
当 int x = q[ l ];
quickSort(q , l , j );
quickSort(q , j+1 , r );

代码：

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  4. public class Main {
  5.     public static void main(String[] args) throws Exception {
  6.         //从键盘上获取数字
  7.         InputStreamReader is = new InputStreamReader(System.in);
  8.         BufferedReader br = new BufferedReader(is);
  9.         //获取长度
  10.         int num = Integer.parseInt(br.readLine());
  11.         //新建数组
  12.         int[] arr = new int[num];
  13.         //获取数组值
  14.         String[] res = br.readLine().split(" ");
  15.         //赋值数组
  16.         for(int i = 0;i<res.length;i++) {
  17.             arr[i] = Integer.parseInt(res[i]);
  18.         }
  20.         quickSort(arr, 0, num - 1);
  22.         for (int i = 0; i < num; i++) {
  23.             System.out.print(arr[i] + " ");
  24.         }
  25.         br.close();
  26.     }
  27.     public static void  quickSort(int[] q,int l,int r) {
  28.         //只剩一个或为空 方法结束
  29.         if(l>=r) return;
  31.         int x = q[l];
  32.         int i = l - 1;
  33.         int j = r + 1;
  35.         while(i < j) {
  36.             do i++;while (q[i] < x);
  37.             do j--;while (q[j] > x);
  38.             if(i < j) {
  39.                 int tem = q[i];
  40.                 q[i] = q[j];
  41.                 q[j] = tem;
  42.             }
  43.         }
  44.         quickSort(q,l,j);
  45.         quickSort(q,j + 1,r);
  46.     }
  47. }

题目：

https://www.acwing.com/problem/content/788/
给定一个长度为 nn 的整数数列，以及一个整数 kk，
请用快速选择算法求出数列从小到大排序后的第k个数
输入格式
第一行包含两个整数 nn 和 kk。
第二行包含 nn 个整数（所有整数均在 1∼1091∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 kk 小数。
数据范围
1≤n≤1000001≤n≤100000,
1≤k≤n1≤k≤n
输入样例：
5 3 2 4 1 5 3
输出样例：
3
代码实现：

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  4. public class Main {
  5.     public static void main(String[] args) throws Exception {
  6.         InputStreamReader is = new InputStreamReader(System.in);
  7.         BufferedReader rd = new BufferedReader(is);
  8.         String str[] = rd.readLine().split(" ");
  10.         String num[] = rd.readLine().split(" ");
  12.         int n = Integer.parseInt(str[0]);
  13.         int k = Integer.parseInt(str[1]);
  14.         int[] arr = new int[n];
  16.         for(int i = 0;i < n;i++) {
  17.             arr[i] = Integer.parseInt(num[i]);
  18.         }
  20.         quickSort(arr,0,n-1);
  22.         System.out.println(arr[k-1]);
  24.         rd.close();
  25.         is.close();
  26.     }
  27.     static void quickSort(int[] q,int l,int r) {
  28.         if (l >= r) return;
  29.         int i = l-1 , j = r + 1 ,x = q[r + l + 1 >> 1];
  30.         while(i < j) {
  31.             do i++ ; while (q[i] < x);
  32.             do j-- ; while (q[j] > x);
  33.             if (i < j) {
  34.                 int tem = q[i];
  35.                 q[i] = q[j];
  36.                 q[j] = tem;
  37.             }
  38.         }
  39.         quickSort(q,l,i - 1);
  40.         quickSort(q,i,r);
  41.     }
  42. }

合并排序->分治

步骤：

1.确定分界点：q[( l + r ) / 2]
2.调用递归排序
3.归并—合二为一

模板：

  1.           int mid = r + l >>1;<br />mergeSort(q ,** l** , **mid** );<br />              mergeSort(q , **mid + 1** ,** r**);<br />        //合并，取 k 值 <br />              int **k = 0 ,i = l , j = mid + 1**;<br />              while (i <= mid && j <= r) {<br />                  if (q[i] <= q[j]) tem[k++] = q[i++];<br />                  else tem[k++] = q[j++];<br />              }<br />              while(j <= r) tem[k++] = q[j++];<br />              while(i <= mid) tem[k++] = q[i++];<br />        //从左边界 到右边界 进行数组赋值<br />              for (**i = l , j = 0 ; i <= r ; i++ , j++**) q[i] = tem[j];

代码：


import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * @author JDsen99
 * @description
 * @createDate 2021/7/6-10:52
 */
public class Main {
        public final static int N = (int) (1e6 + 10);
        public static int[] tem = new int[N];

        public static void main(String[] args) throws Exception {
            InputStreamReader is = new InputStreamReader(System.in);
            BufferedReader rd = new BufferedReader(is);

            String str = rd.readLine();
            String num[] = rd.readLine().split(" ");

            int n = Integer.parseInt(str);

            int[] arr = new int[n];


            for(int i = 0;i < n;i++) {
                arr[i] = Integer.parseInt(num[i]);
            }

            mergeSort(arr,0,n-1);
            for(int i = 0;i < n;i++) System.out.printf("%d ",arr[i]);
            rd.close();
            is.close();
        }
        static void mergeSort(int[] q, int l,int r) {
            //边界判断
            if (l >= r) return;
            //取中值
            int mid = r + l >>1;
            //递归
            mergeSort(q,l,mid);
            mergeSort(q,mid+1,r);
            //合并
            int k = 0 ,i = l , j = mid + 1;
            while (i <= mid && j <= r) {
                if (q[i] <= q[j]) tem[k++] = q[i++];
                else tem[k++] = q[j++];
            }
            while(j <= r) tem[k++] = q[j++];
            while(i <= mid) tem[k++] = q[i++];
            for (i= l,j= 0;i<=r;i++,j++) q[i] = tem[j];
        }
    }

题目：

给定一个长度为 nn 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 nn，表示数列的长度。
第二行包含 nn 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
6
2 3 4 5 6 1
输出样例：
5
代码实现：

import java.io.*;
public class Main {
    final static int N = (int) 1e6+100;
    static int[] tem = new int[N];
    public static void main(String[] args) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        String str = rd.readLine();

        int n = Integer.parseInt(str);
        int[] arr = new int[n];

        String[] num = rd.readLine().split(" ");
        for (int i = 0 ;i < n ;i++) {
            arr[i] = Integer.parseInt(num[i]);
        } 
        System.out.println(mergeSort(arr,0,n-1));
    }
    private static long mergeSort(int[] q,int l,int r) {

        long res = 0;

        if(l >= r) return res;

        int mid = l + r >> 1;

        res += mergeSort(q,l,mid)+mergeSort(q,mid + 1,r);

        int k = 0 , i = l,j = mid + 1;
        while(i <= mid && j <= r) {
            if (q[i] <= q[j] ) tem[k++] = q[i++];
            else {
                tem[k++] = q[j++];
                res += mid - i + 1;
            }
        }
        while(i <= mid) tem[k++] = q[i++];
        while(j <= r) tem[k++] = q[j++];
        for (i = l,j = 0;i <= r;i++,j++) q[i] = tem[j];
        return res;
    }
}

整数二分->二段性

图形：

image.png

![image.png](https://cdn.nlark.com/yuque/0/2021/png/21621722/1625487366666-7ad38e3b-804e-475f-9d46-6c9ffd47ceec.png#clientId=ud0cfbeb1-fb0c-4&from=paste&height=336&id=ub7d767ad&margin=%5Bobject%20Object%5D&name=image.png&originHeight=627&originWidth=1125&originalType=binary&ratio=1&size=238934&status=done&style=shadow&taskId=u1ce11e4e-4ad2-4b11-9c92-80639a8105b&width=603)

模板：

模板一： 左区间

// 区间[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)  // check() 判断 mid是否满足性质
            r = mid; 
        else
            l = mid + 1;
    }
    return l;
}

模板二：右区间

// 区间[l, r]被划分成 [l, mid-1] 和 [mid, r]时使用
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 2;   // 注意
        if (check[mid)  // check() 判断 mid是否满足性质
            l = mid;
        else
            r = mid - 1;

    }
    return l;
}

题目

给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 nn 和 qq，表示数组长度和询问个数。
第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。
输出格式
共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author JDsen99
 * @description
 * @createDate 2021/7/6-16:38
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        String strings[] = rd.readLine().split(" ");
        int n = Integer.parseInt(strings[0]);
        int count = Integer.parseInt(strings[1]);

        int[] arr = new int[n];

        String strs[] = rd.readLine().split(" ");

        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(strs[i]);

        while (count-- != 0) {
            int target = Integer.parseInt(rd.readLine());

            //查找左边界
            int l = 0,r = n - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if(arr[mid] < target) l = mid + 1;
                else r = mid;
            }

            if (arr[l] != target) {
                System.out.println("-1 -1");
            } else {
                System.out.print(l+" ");
                l = 0;
                r = n -1;

                while(l < r) {
                    int mid = l + r + 1 >> 1;
                    if (arr[mid] <= target) {
                        l = mid;
                    } else {
                        r = mid -1;
                    }
                }
                System.out.println(l);
            }
        }
    }
}

浮点二分->二段性

模板：

double bsearch(double l, double r) {
    while (r - l >=1e-7) {
        double mid =( l + r ) / 2;
        if (check[mid)  // check() 判断 mid是否满足性质
            r = mid; 
        else
            l = mid;
    }
}

题目

给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
代码实现：

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * @author JDsen99
 * @description
 * @createDate 2021/7/6-17:30
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        String str = rd.readLine();
        double n = Double.parseDouble(str);
        double l = n > 0?0:n-1,r = Math.abs(n);
        while(r - l >=1e-7) {
            double mid = (r + l ) / 2;
            if(Math.pow(mid,3.0) >= n ) r = mid ;
                else l = mid;
        }
        System.out.printf("%.6f",r);
    }
}