长春高端品牌网站建设,软件公司logo图标大全,wordpress宠物插件,广东网站建设公司哪家便宜目录
一.排序
快速排序:
归并排序:
二.二分法
整数二分模板:
浮点二分: 一.排序
快速排序:
从数列中挑出一个元素#xff0c;称为 基准重新排序数列#xff0c;所有元素比基准值小的摆放在基准前面#xff0c;所有元素比基准值大的摆在基准的后面#…目录
一.排序
快速排序:
归并排序:
二.二分法
整数二分模板:
浮点二分: 一.排序
快速排序:
从数列中挑出一个元素称为 基准重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区操作。递归把小于基准值元素的子数列和大于基准值元素的子数列排序。 static void quick_sort(int[] arr,int l,int r){if (lr) return;//特判小于等于1个的数组int xarr[(lr)1],il-1,jr1;//取分隔基准while (ij){//把小于x的数放左边,大于x的数放右边//跳过已符合条件do i; while (arr[i]x);do j--; while (arr[j]x);//交换使符合条件if (ij){int tarr[i];arr[i]arr[j];arr[j]t;}}//递归左右边排序quick_sort(arr,l,j);quick_sort(arr,j1,r);}
归并排序:
利用归并(先递归排序子元素,再合并)的思想实现的排序方法该算法采用经典的分治divide-and-conquer策略分治法将问题分(divide)成一些小的问题然后递归求解而治(conquer)的阶段则将分的阶段得到的各答案修补在一起即分而治之)。 static void merge_sort(int[] arr, int l, int r) {if (l r) return;int mid l r 1;merge_sort(arr, l, mid);//递归排序左merge_sort(arr, mid 1, r);//右//合并int[] tmp new int[arr.length];int k 0, i l, j mid 1;while (i mid j r) {//从排序好的左右数组取最小依次放入tmp数组,知道某一个数组取完if (arr[i] arr[j])tmp[k] arr[i];elsetmp[k] arr[j];}//剩余部分直接放入tmp数组末尾while (i mid) tmp[k] arr[i];while (j r) tmp[k] arr[j];//tmp数组赋给原数组for (i l, j 0; i r; i, j) arr[i] tmp[j];}
二.二分法
二分法的思想很简单因为整个数组是单调的,每次判断后可将另外一半直接排除,大大提高查找效率,但是二分查找的边界问题很容易成为问题
整数二分模板: static int binary_search1(int[] arr,int l, int r){while (lr){int midlr1;if (check(mid)){rmid;}else {lmid1;}}return l;}static int binary_search2(int[] arr,int l,int r){while (lr){int midlr11;if(check(mid)){lmid;}else {rmid-1;}}return l;}
根据具体情况选择判断后边界的取值,特别注意不同边界下mid的初始化.
浮点二分: static double binary_search3(double[] arr,double l,double r){final double eps1e-6;while (r-leps){double mid(lr)/2;if (check(mid)) rmid;else lmid;}return l;}
浮点二分的核心在使用eps的精度进行判断
