快速排序
算法思路：
第一步 确定分界点(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(); } } } }
