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

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);

    }