【算法设计与分析基础】26、在写快排

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法设计与分析基础】26、在写快排，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4645字，纯文字阅读大概需要7分钟。

内容图文

我真是服了。。。。一段时间没用，快排都不会了，实打实写了半天，细细回想一下为什么会写那么久写不出来？？？

1.没有吧概念理解清楚就开始动代码，致命错误

2.无法准确明白前后遍历索引终止位置

3.习惯重低位向高位进行索引，导致中间索引位置和真正的中间位置相差一位，因为我们比较的时候，是按照从小到大的顺序排序的，并且我们比较都是>=或者<= 问题就在这个等于上，因为我们等于的时候还是会进行索引的++

那么就导致是从上往下合并还是从下往上合并，如果是从下往上合并的话，那么先遍历小的，在等于我们中间数据的时候，我们还会再走一趟，那么就会导致索引所在位置会比之前的位置大一位

哎。。。。

还差的远啊，加油啊

 

这里其实是在做另外一道笔试题的时候，用到了排序，于是想用一下快排，好久没写了，结果悲剧了。。。。

算了发出来，笔试其实不麻烦，麻烦的是这个快排。。。

 

package y2019.m03.d13;

import y2019.m03.d13.vo.RoomVo;

/**
 * @ProjectName: cutter-point
 * @Package: y2019.m03.d13
 * @ClassName: BuildRoom
 * @Author: xiaof
 * @Description:
 * 题目：
 * 为解决城中村改造问题并解决市民的住房困难，政府决定在城郊区域建造一批安居房。工程进行的比较顺利，已经有n套方形的房屋建好了。所有的房子都在街道的一侧，中心位于x轴上，
 * 墙壁与坐标轴平行。任何两个房子之间没有重叠，但可以公用邻接的墙壁以节省开支。由于负责建设这批安居房的公司出现了问题，小B所在的公司负责接手后续房子的建设工作。
 * 客户希望房子能够和其他房子一样位于x轴上，并且也是方形的，边长为t，墙壁与坐标轴平行，且至少与一个已经建好的房子毗邻。由于还不熟悉情况，
 * 她希望你能帮她找出还有多少位置可以开展新房建设工作。
 *
 * 输入中有多组测试数据。每组测试数据的第一行为空格分隔的两个整数nn和t（1=<n,t<=1000）t（1=<n,t<=1000），随后的n行中每行包含两个整数xi和 ai，xi为第i个房子的中心坐标，
 * ai为其边长（?1000=<xi<=1000,1=<ai<=1000）（?1000=<xi<=1000,1=<ai<=1000）。
 *
 * @Date: 2019/3/13 9:14
 * @Version: 1.0
 */
public class BuildRoom {

    /**
     *
     * @program: y2019.m03.d13.BuildRoom
     * @description: 快排
     * 1. 取开始位置的一个数据
     * 2. 2变index向中间比较，如果碰头，那么开始递归下一个区间
     * 3. 没有碰头，那么就前后和key依次比较，交换位置
     * @auther: xiaof
     * @date: 2019/3/13 9:23
     */
    public static void quikSortForRoom(RoomVo data[], int start, int end) {
        if(start >= end)
            return;

        int low = start;
        int high = end;
        int key = data[low].getX();

        //这个循环的主要目的是，寻找中间位置，然后和key进行交换，用key进行区分两边位置
        //切记，这里是重高位优先开始往地位遍历，那么会导致高位会先与低位与低位汇聚成一个索引位置
        //那么我们获取到的中央位置，肯定就是我们的中间点，也就是我们用来分裂的位置
        //然后我们用和这个位置进行分裂递归遍历，那么正好就可以获取到正确的顺序
        while(low < high) {

            while(high > low && data[high].getX() >= key) {
                --high;
            }

            //交换位置
            if(low < high) {

                BuildRoom.swap(data, low, high);
            }

            //如果没有碰头，那么就依次比较交换位置
            while(low < high && data[low].getX() <= key) {
                ++low;
            }

            //交换位置
            if(low < high) {

                BuildRoom.swap(data, low, high);
            }

        }

        quikSortForRoom(data, start, high - 1);
        quikSortForRoom(data, high + 1, end);

    }

    public static void printData(RoomVo data[]) {
        for(int i = 0; i < data.length; ++i) {
            System.out.print(data[i].getX() + " => ");
        }
        System.out.println();
    }

    public static void swap(RoomVo data[], int i, int j) {
        RoomVo temp = data[i];
        data[i] = data[j];
        data[j] = temp;
        printData(data);
    }

    /**
     *
     * @program: y2019.m03.d13.BuildRoom
     * @description: 这个题我的理解是，再一个x坐标上建房子，不同的房子的中心点坐标不同，边长不同，现在要建新房子，每个房子的边长都是t，现在需要排除间隔在t以上的位置，
     *      并判断间隔能建几个位置
     * @auther: xiaof
     * @date: 2019/3/13 9:18
     */
    public static int selectRoomSite(int roomSites[][]) {
        //1、受限按照x坐标轴对这些数据进行重新排序
        //2、根据排序结果，依次获取数据，然后计算中间间隔
        //间隔除以t，如果正好除净，余下多少就是有几个位置，如果除不尽那么取除数+1
        return -1;
    }

}

 

package y2019.m03.d13.vo;

/**
 * @ProjectName: cutter-point
 * @Package: y2019.m03.d13.vo
 * @ClassName: RoomVo
 * @Author: xiaof
 * @Description: ${description}
 * @Date: 2019/3/13 9:21
 * @Version: 1.0
 */
public class RoomVo {

    private int x; //x坐标位置
    private int a;  //房子边长

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getA() {
        return a;
    }

    public void setA(int a) {
        this.a = a;
    }
}

 

 

测试代码：

    @Test
    public void test4() {
        RoomVo roomVo[] = new RoomVo[11];
        roomVo[0] = new RoomVo();
        roomVo[0].setX(6);
        roomVo[1] = new RoomVo();
        roomVo[1].setX(2);
        roomVo[2] = new RoomVo();
        roomVo[2].setX(7);
        roomVo[3] = new RoomVo();
        roomVo[3].setX(3);
        roomVo[4] = new RoomVo();
        roomVo[4].setX(8);
        roomVo[5] = new RoomVo();
        roomVo[5].setX(9);
        roomVo[6] = new RoomVo();
        roomVo[6].setX(1);
        roomVo[7] = new RoomVo();
        roomVo[7].setX(10);
        roomVo[8] = new RoomVo();
        roomVo[8].setX(2);
        roomVo[9] = new RoomVo();
        roomVo[9].setX(6);
        roomVo[10] = new RoomVo();
        roomVo[10].setX(-1);

        BuildRoom.quikSortForRoom(roomVo, 0, roomVo.length - 1);

//        BuildRoom.printData(roomVo);

    }

 

结果：

 

 

 这里会输出每一次交换的时候变动

 

内容总结

以上是互联网集市为您收集整理的【算法设计与分析基础】26、在写快排全部内容，希望文章能够帮你解决【算法设计与分析基础】26、在写快排所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---