快速排序
思路：首先随机定义数组的一个数，把他当成边界值进行排序，一般是取数组中间的一个数，在这个数的左边区间寻找一个比他大的数，在这个数的右边区间寻找一个比他小的数，将这两个数进行交换，最后左边区间的数都小于他，右边的数都大于他，然后在左右区间分别递归。
参数1，待排序数组 参数二，起始索引 参数三，终止索引
private static void quick_sort(int[] q, int l, int r) { if(l>=r) return; int t=q[(l+r)/2],i=l-1,j=r+1; while (i<j){ do i++; while (q[i]<t); do j--; while (q[j]>t); if(i<j) { int temp=q[i]; q[i]=q[j]; q[j]=temp; } } quick_sort(q,l,j); quick_sort(q,j+1,r); }
归并排序
思路：该算法采用经典的分治策略（把一个大问题分解为若干个小的问题进而求解的过程），将数组不断一分为二，分成n份后，再按照有序数组的拼接方法，两两比较取每一份中的最小值进行拼接，对每个子数组进行拼接，这样就能保证每次的拼接结果都还是有序的最终拼接成一个之后，整个数组便都是有序的
private static void merge_sort(int[] q, int l, int r) { if(l>=r) return; int mid = l+r>>1; merge_sort(q,l,mid); merge_sort(q,mid+1,r); int k=0,i=l,j=mid+1; int []tmp=new int [r-l+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(int m=l,n=0;m<=r;m++,n++ ) q[m]=tmp[n]; }
整数二分算法
二分的本质不是单调性, 单调性的题目一定可以二分, 可以二分的题目不一定有单调性
二分的本质是边界
二分法用于查找, 每次都选择答案所在的区间再次进行查找, 当区间长度为 1时, 就是答案
模板1
// 区间[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; }
模板2
// 区间[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; }
如何选择模板
根据 check(mid)来判断 r和 l的取值范围
根据取值范围选择 mid是否有 + 1操作
如果mid满足条件在左边, r = mid, mid选择 不 +1
如果mid满足条件在右边, l = mid, mid选择 +1
浮点数二分算法
public static void main(String[] args) { Scanner sc=new Scanner(System.in); double n= sc.nextDouble(); double eps=1e-8; double l=0,r = 10000;//浮点数范围在10000以内，有负数 while(r-l>eps){ double mid=(l+r)/2; if(mid*mid*mid>=Math.abs(n)){ r=mid; }else{ l=mid; } } if (n >= 0) System.out.println(String.format("%.6f", l)); // 保留 6位小数 else System.out.println("-" + String.format("%.6f", l)); }
