基础算法(一)

目录

一.排序

快速排序:

归并排序:

二.二分法

整数二分模板:

浮点二分:

---

 

一.排序

快速排序:

• 从数列中挑出一个元素，称为 "基准"
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作。
• 递归把小于基准值元素的子数列和大于基准值元素的子数列排序。

    static void quick_sort(int[] arr,int l,int r){if (l>=r) return;//特判小于等于1个的数组int x=arr[(l+r)>>1],i=l-1,j=r+1;//取分隔基准while (i<j){//把小于x的数放左边,大于x的数放右边//跳过已符合条件do i++; while (arr[i]<x);do j--; while (arr[j]>x);//交换使符合条件if (i<j){int t=arr[i];arr[i]=arr[j];arr[j]=t;}}//递归左右边排序quick_sort(arr,l,j);quick_sort(arr,j+1,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 (l<r){int mid=l+r>>1;if (check(mid)){r=mid;}else {l=mid+1;}}return l;}static int binary_search2(int[] arr,int l,int r){while (l<r){int mid=l+r+1>>1;if(check(mid)){l=mid;}else {r=mid-1;}}return l;}

根据具体情况选择判断后边界的取值,特别注意不同边界下mid的初始化.

浮点二分:

    static double binary_search3(double[] arr,double l,double r){final double eps=1e-6;while (r-l>eps){double mid=(l+r)/2;if (check(mid)) r=mid;else l=mid;}return l;}

浮点二分的核心在使用eps的精度进行判断