对于排序算法相信大家都不陌生，大部分排序的程序都是串行的排序算法，比如冒泡排序，插入排序，选择排序，堆排序等等，但是随着计算机的发展，现在的计算机都是多核的处理器，串行排序无法高效的利用CPU，为了更加有效的利用CPU，我们在这里介绍一下在并行世界中的排序算法。
在介绍并行排序之前，我们有必要介绍一下奇偶排序，为了将串行排序算法改为并行排序，使用奇偶排序可以更加方便的修改程序为并行排序。
1.什么是奇偶交换排序？ 奇偶排序分为两个阶段，奇交换和偶交换。奇交换就是将比较数组奇数索引以及与其相邻的之后的元素，偶交换就是比较数组偶数索引和其相邻的后续元素，并且，奇交换和偶交换总是成对出现，这样才能保证涉及到数组中的每一个元素。
这里我们举一个例子，图解一下奇偶交换排序，假如这里我们对5，45，6，3，4 这五个数进行排序，下面我们来看看它具体是怎么进行奇偶交换的。（图画的有点丑哈_） 通过上面的图解我们可以很清除的明白奇偶交换排序的原理。下面我们来写一下串行的奇偶交换排序的代码：
package cn.just.thread.concurrent; /** * 奇偶排序 * @author Shinelon * */ public class OddEventSort { public static void sort(int[] arr){ int exchange=1,start=0,temp; //exchange记录当前循环是否进行了数据交换 while(exchange==1||start==1){ //start==1保证奇偶排序成对出现 exchange=0; //没有发生交换 for(int i=start;i<arr.length-1;i+=2){ //刚开始进行偶排序 if(arr[i]>arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; exchange=1; } } if(start==0) start=1; else start=0; } } public static void main(String[] args) { int[] a={12,25,45,78,69,45,58,26,78,49,12,2,23,5,89,45,78,58,20,19}; sort(a); for(int i=0;i<a.length;i++){ System.out.println(a[i]); } } }二、并行排序 下面我们开始今天的正题，现在我们就开始将上面的串行的排序方式修改为并行排序，此时我们已经很清楚的认识了奇偶交换排序，【它总是和奇索引或者偶索引对应的数据之后的数进行比较并且交换，这样就不会出现一个数既可以和它之前的数进行交换，也可以和它之后的数进行交换，从而在并行的模式下多个线程之间不会相互干扰，这是使用奇偶交换排序来进行并行排序的关键所在。】 那么我们将怎么去分配线程的数量呢？并行的过程是怎么样的呢？我们还是以上面的数据为例进行讲解，在第一次偶交换的时候我们可以开启两个线程来分别交换5，45和6，3。同理，我们在接下来的奇交换时也开启两个线程来比较交换45，3和6，4。这样两个线程之间没有任务干扰，也不互相依赖，这样我们就正确的进行了并行排序。对于每次交换开启的线程数，我们可以通过以下方式来计算得到：
threadNumber=arr.length/2-(arr.length%2==0?start:0);下面我们来写出完整的并行排序的程序：
package cn.just.thread.concurrent; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; /** * 并行排序 * @author Shinelon * */ public class CurrOddEventSort { public static int exchange=1; public static int[] arr={12,25,45,78,69,45,58,26,78,49,12,2,23,5,89,45,78,58,20,19}; public static int getExchange() { return exchange; } public static synchronized void setExchange(int exchange) { CurrOddEventSort.exchange = exchange; } public static class OddEventSortTask implements Runnable{ int i; CountDownLatch latch; public OddEventSortTask(int i, CountDownLatch latch) { super(); this.i = i; this.latch = latch; } public void sort(int[] arr){ int temp; if(arr[i]>arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; setExchange(1); } latch.countDown(); } @Override public void run() { sort(arr); } } public static void OddEventSort(int[] arr) throws InterruptedException { ExecutorService pool=Executors.newCachedThreadPool(); int start=0; while(getExchange()==1||start==1){ setExchange(0); //偶数的数组长度，当start为1时，只有length/2-1个线程 CountDownLatch l=new CountDownLatch(arr.length/2-(arr.length%2==0?start:0)); for(int i=start;i<arr.length-1;i+=2) pool.submit(new OddEventSortTask(i, l)); //等待所有线程结束 l.await(); if(start==1) start=0; else start=1; } } public static void main(String[] args) throws InterruptedException { OddEventSort(arr); for(int i=0;i<arr.length;i++){ System.out.println(arr[i]); } } }上面的代码不是很难读懂，有的人可能不了解CountDownLatch ，这里我们简单介绍一下CountDownLatch ，它是多线程控制的一个工具类，是一个倒计时器，构造函数 new CountDownLatch(int number)中的参数number是开启的计时器数目，CountDownLatch.await()方法要求主线程等待所有线程池中所有任务都执行完。CountDownLatch.countDown()是当一个任务执行完后数目减去1。
这里我们已经介绍完并行排序，在数据少的时候也许体现不出并行排序的优势，所以我们会选择串行排序，但是现在是大数据时代，当数据剧增时，并行排序就很有优势，效率很高，现在有很多大数据框架就是并行计算来处理海量数据的，感兴趣的小伙伴可以自己去了解，我们就介绍到这里（其实是比较菜，说不清楚，O(∩_∩)O哈哈~）。
如果你想和我们一起学习探讨，可以扫码加群：
