奇偶排序及其并行化设计

题目

奇偶排序及其并行化设计

定义

奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒，就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=0,2, 4,6……)。重复进行这样两趟的排序直到数组全部有序。

奇偶交换总是成对出现，这样才能保证比较和交换涉及到数组中的每一个元素。

分析

奇偶排序可以看做是冒泡排序的升级版，但冒泡排序中每个元素既可能与前面的元素交换，也可能与后面的元素交换，奇偶排序消除了这种数据的相关性，所以可以实现并行化设计。

串行算法

public class Solution {
   public void oddEvenSort(int[] array) {
       int start = 1;
       boolean swap = true;
       while (!(swap == false && start == 1)) {
           swap = false;
           for(int i = start; i < array.length - 1; i += 2) {
               if(array[i] > array[i + 1]) {
                   int tmp = array[i];
                   array[i] = array[i + 1];
                   array[i + 1] = tmp;
                   swap = true;
               }
           }
           if (start == 1) {
               start = 0;
           } else {
               start =1;
           }
       }
   }
}

只有在没有发生交换且完成了一对奇偶交换时才代表数组已经有序，可以退出循环。这里由于是从奇交换开始的，所以只有完成了偶交换且没有交换发生才能退出循环。使用swap记录是否有交换发生，使用start值的变化实现奇偶交换的交替。初始时start为1，进行奇交换，之后变为0，进行偶交换。

并行算法

public class Solution {
    static int[] array = {1, 4, 5, 2, 3};
    static boolean swap;
    static ExecutorService es = Executors.newCachedThreadPool();

    public Solution(int[] a ) {
        this.array = a;
    }

    public static synchronized void setSwap (boolean s) {
        swap = s;
    }

    public static synchronized boolean getSwap() {
        return swap;
    }

    public static class oddEvenSort implements Runnable {
        int i;
        CountDownLatch latch;
        public oddEvenSort(int i, CountDownLatch latch) {
            this.i = i;
            this.latch = latch;
        }

        @Override
        public void run() {
            if(array[i] > array[i + 1]) {
                int tmp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = tmp;
                setSwap(true);
            }
            latch.countDown();
        }
    }

    public static void main(String[] args) throws InterruptedException{
        setSwap(true);
        int start = 1;
        while (!(getSwap() == false && start == 1)) {
            setSwap(false);
            CountDownLatch latch = new CountDownLatch((array.length - start) / 2);
            //或  CountDownLatch latch = new CountDownLatch(array.length/2 -(array.length%2 == 0?start:0));
            for(int i = start; i < array.length - 1; i += 2) {
                es.submit(new oddEvenSort(i, latch));
            }
            latch.await();
            if(start == 0) {
                start = 1;
            } else {
                start = 0;
            }
        }
        System.out.println(Arrays.toString(array));
        es.shutdown();
    }
}

通过CountDownLatch记录线程数量，在下一次迭代前必须完成所有线程的排序。