基础算法(一)

目录

一.排序

快速排序:

归并排序:

二.二分法

整数二分模板:

浮点二分:

---

 

一.排序

快速排序:

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

    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//把小于x的数放左边,大于x的数放右边
 
            //跳过已符合条件
            do i++; while (arr[i]
            do j--; while (arr[j]>x);
            //交换使符合条件
            if (i
                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++];
            else
                tmp[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
            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
            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的精度进行判断