我也每日一题

Question

java写个快速排序1。 可以中断，
2。 可以在中断的Context继续
比如说：1 3 2 9 5 6 7 8 4
==》
1 3 2 4 5 // 后面的先不管了。
你可以先排 前几个，作为一个Partial。然后排序暂停，处理其他逻辑去需要的时候继续排。 然后还可以继续当然了，你把这种事情放到一个线程里面也行，随时Suspend，随时Resume，但是我今天要一个算法。

Answer 1

QUICKSORT(A[]，int p，int r，boolean isWait) 　　
1　if p<r
2  if isWait {wait();} 　　
2　then q ← PARTITION(A，p，r) 　　
3　QUICKSORT(A，p，q-1) 　　
4　QUICKSORT(A，q+1，r) 放线程里，抽象出一个原子操作，执行原子操作前判断isWait

Answer 2

//用线程不复杂
public class Test implements Runnable {    public static void main(String[] args) {
        int[] d = new int[]{
            1, 3, 2, 9, 5, 6, 7, 8, 4
        };
        Test t = new Test(d);
        t.start();
    }
    private boolean init;
    private boolean push;
    private boolean end;
    private Thread thr = new Thread(this);
    private int[] date;    public Test(int date[]) {
        this.date = date;
    }    /**开始排序*/
    public void start() {
        if (init) {
            return;
        }
        init = true;
        thr.start();
    }    /**返回当前排序的状态*/
    public String Context() {
        String str = "[";
        synchronized (date) {
            if (date != null) {
                for (int i = 0; i < date.length; i++) {
                    str += date[i];
                    if (i + 1 < date.length) {
                        str += ",";
                    }
                }
            }
        }
        return str + "]";
    }    /**暂停，恢复*/
    public void push() {
        push = !push;
    }    /**是不是排序结束*/
    public boolean isEnd() {
        return end;
    }
    private java.util.Stack<Operator> s = new java.util.Stack<Operator>();    public void run() {
        s.add(new Operator(0, date.length - 1));
        while (!s.isEmpty()) {
            while (push) {
                try {
                    Thread.sleep(0);
                } catch (InterruptedException ex) {
                }
            }
            Operator wp = s.pop();
            int i = wp.l;
            int j = wp.r;            if (i < j) {
                //默认左边第一个数为比较的 key
                int key = date[wp.l];
                //排序
                do {
                    //找到左边边界
                    while (date[i] < key && i < wp.r) {
                        i++;
                    }
                    //找到右边边界
                    while (date[j] > key && j > wp.l) {
                        j--;
                    }
                    // 左边大的 和 右边小的 交换
                    if (i < j) {
                        synchronized (date) {
                            int temp = date[i];
                            date[i] = date[j];
                            date[j] = temp;
                        }                    }
                } while (i < j);                //比较结束
                if (i > j) {
                    synchronized (date) {
                        int temp = date[wp.l];
                        date[wp.l] = date[j];
                        date[j] = temp;
                    }
                }                //加入要比较的新区间
                s.push(new Operator(wp.l, j - 1));
                s.push(new Operator(j + 1, wp.r));                //System.out.println("过程:" + Context());
            }
        }
        end = true;
    }    class Operator {        int r;
        int l;        Operator(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
}

Answer 3

不太懂java，悄悄地，不要犯了众怒