快速排序

算法思路：

第一步确定分界点(q[l],q[(l+r)/2],q[r]随机)

第二步小于等于x(第一个区间)
大于等于x(第二个区间)

第三步递归处理左右两段

图解：

代码示例:

public class 快速排序 {
    public static void paixu(int[] p,int l,int r){
        if(l>=r){
            return;
        }
        int x = p[l];
        int m=l-1;
        int n=r+1;
        int temp;
        while(m<n){
            do m++; while (p[m]<x);
            do n--; while (p[n]>x);
            if(m<n){
                temp = p[m];
                p[m]=p[n];
                p[n]=temp;
            }
        }
        paixu(p,l,n);
        paixu(p,n+1,r);
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] str = new int[N];
        for(int i=0;i<N;i++){
            str[i]=sc.nextInt();
        }
        paixu(str,0,N-1);
        System.out.println(Arrays.toString(str));
    }
}

归并排序

算法思路:

第一步确定分界点:mid=(1+r)/2

第二步递归排序:left=right

第三步归并合二为一

图解:

代码示例:

public class 归并排序 {
    public static void panduan(int[] tmp,int[] q,int l,int r){
        if(l>=r){
            return;
        }
        int mid = (l+r)/2;
        panduan(tmp,q,l,mid);
        panduan(tmp,q,mid+1,r);
        int k=0,i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(q[i]<=q[j]) tmp[k++]=q[i++];
            else tmp[k++]=q[j++];
        }
        while (i<=mid) tmp[k++] =q[i++];
        while (j<=r) tmp[k++] = q[j++];

        for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] str = new int[N];
        int[] tmp = new int[N];
        for(int i=0;i<N;i++){
            str[i]=sc.nextInt();
        }
        panduan(tmp,str,0,N-1);
        System.out.println(Arrays.toString(str));
    }
}

二分查找

算法思路:

例题:给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。如果数组中不存在该元素，则返回“-1 -1”。

示例代码：

public class 数的范围 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] str = new int[N];
        for(int i=0;i<N;i++){
            str[i] = sc.nextInt();
        }

        for(int i=0;i<M;i++){
            int x = sc.nextInt();
            int l=0,r=N-1;
            while (l<r){
                int mid = (l+r)/2;
                if(str[mid]>=x) r=mid;
                else l=mid+1;
            }
            if(str[l]!=x) System.out.println("-1 -1");
            else{
                System.out.print(l+" ");
                l=0;
                r=N-1;
                while (l<r){
                 int mid = (l+r+1)/2;
                 if(str[mid]<=x) l=mid;
                 else  r=mid-1;
                }
                System.out.print(l);
                System.out.println();
            }
        }
    }
}