快速排序、归并排序、二分算法

用户10604450

发布于 2024-03-15 13:48:29

650

发布于 2024-03-15 13:48:29

文章被收录于专栏：练习两年半

快速排序

思路：首先随机定义数组的一个数，把他当成边界值进行排序，一般是取数组中间的一个数，在这个数的左边区间寻找一个比他大的数，在这个数的右边区间寻找一个比他小的数，将这两个数进行交换，最后左边区间的数都小于他，右边的数都大于他，然后在左右区间分别递归。

参数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));
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-01-03，如有侵权请联系 cloudcommunity@tencent.com 删除

索引