关注本公众号，一天一个知识点，持续精进！
这是代码荣耀的第122篇原创
00、引言
任何一本讲算法的计算机专业书籍，有两种算法是必然不会被遗漏的——查找与排序。也许是为了编程练手、也许是为了技术面试，大家都会把这些算法思想烂熟于心。虽然这些算法都会得到编程语言原生库的支持，但是了解这些算法背后的思想对于提升我们的技术思路与认知还是大有裨益的。串行的实现我们见的很多了，但是并行化的查找与排序编程实现会长成什么样了？
前文NO.64 分头行动：并行Search模式，我们实现了并行查找；今天我们来看看排序，排序算法有很多，今天我们先从最基本的冒泡排序算法说起，看看并行冒泡是否会让我们有一种脑洞大开的感觉？
01、图解冒泡
冒泡排序是一种计算机科学领域的较简单的排序算法。其基本原理是：重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换位置。遍历数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“下沉”到数列的底部，相反，越小的数则会经由交换逐步上浮到顶部。
一图胜千言，有图有真相，上图——
02、串行冒泡
按照上述冒泡排序思想，我们可以很快写出其实现，具体详见下述代码。
//大家应该都很清楚实现原理了，这里就不详细注释了
public class SortDemo {
////串行的冒泡方法实现从小到大的排序
public static void bubbleSort(int[] array){
int length = (null == array) ? 0 : array.length;
for (int i = length-1;i>0;i--){
for(int j=0;j<i;j++){
if(array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
//打印数组内容
public static void print(int[] array){
int length = (null == array) ? 0 : array.length;
for(int i=0;i<length;i++){
System.out.print(array[i]+";");
}
System.out.println();
}
//排序功能测试
public static void main(String[] args){
//构造一个随机数组
Random random=new Random();
int size = 20;
int[] array = new int[size];
for(int i=0;i<size;i++){
array[i] = random.nextInt(9999);
}
//排序前的数组打印
print(array);
//对数组进行从小到大的排序
bubbleSort(array);
//排序后的数组打印
print(array);
}
}
03、并行冒泡
学过并行以后，那么我们就能多一个维度去思考问题的解决方案。
按照上述的比较交换过程是很难进行并行的，由于每次交换的两个元素存在数据冲突，对于每个元素，它既可能与前面的元素进行交换，也可能和后面的元素进行交换。不能并行的原因就一句话——存在数据相关性。
如果我们能够解开这种数据相关性，就可以比较容易使用并行算法进行实现。写到这里，“分而治之”的思想又会排上用场。下面我们介绍一种被称为“奇偶交换排序”的算法来实现并行冒泡。
所谓“奇偶交换排序”就是把排序过程分为两个阶段——奇交换和偶交换。对于“奇交换”来说，就是比较奇数索引以及相邻的后续元素。而“偶交换”总是比较偶数索引以及相邻的后续元素。并且，“奇交换”和“偶交换”是成对出现，这样才能保证比较和交换涉及到数组中的每一个元素。具体原理见图示。
可见，结合“分而治之”的思想，由于将整个比较交换独立切分为奇交换阶段和偶交换阶段。这样使得在一个完整的交换阶段中所有的比较和交换是没有数据相关性的。因此，每一次比较和交换都可以独立执行，符合并行运行条件。以下是具体的代码实现。
package weixin.test.forkjoin.layerdemo;
import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
//利用奇偶排序算法实现并行冒泡
public class PSortDemo {
//用于标识当前迭代是否发生了数据交换
static boolean exchanged = true;
static ExecutorService pool = Executors.newCachedThreadPool();
static synchronized void setExchanged(boolean v) {
exchanged = v;
}
static synchronized boolean isExchanged() {
return exchanged;
}
//按照奇偶交换策略，相邻的两个数进行交换
public static class OddEventSortTask implements Runnable {
int i;
CountDownLatch latch;
int[] array;
public OddEventSortTask(int i, int[] array, CountDownLatch latch) {
this.i = i;
this.array = array;
this.latch = latch;
}
public void run() {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
setExchanged(true);
}
latch.countDown();
}
}
public static void pOddEventSort(int[] arr) throws InterruptedException {
//stage为0，表示进行偶交换阶段；stage为1，则表示进行奇交换阶段
int stage = 0;
while (isExchanged() == true || stage == 1) {
setExchanged(false);
// 偶数的数组长度,当为奇交换时,只有len/2-1 个线程
CountDownLatch latch = new CountDownLatch(arr.length / 2
- (arr.length % 2 == 0 ? stage : 0));
for (int i = stage; i < arr.length; i += 2) {
pool.submit(new OddEventSortTask(i,arr, latch));
}
// 等待所有线程结束
latch.await();
//每次迭代结束后，切换stage的状态
if (stage == 0) {
stage = 1;
} else {
stage = 0;
}
}
}
// 打印数组内容
public static void print(int[] array) {
int length = (null == array) ? 0 : array.length;
for (int i = 0; i < length; i++) {
System.out.print(array[i] + ";");
}
System.out.println();
}
// 排序功能测试
public static void main(String[] args) throws InterruptedException {
// 构造一个随机数组
Random random = new Random();
int size = 20;
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(9999);
}
// 排序前的数组打印
print(array);
// 对数组进行从小到大的排序
pOddEventSort(array);
// 排序后的数组打印
print(array);
}
}
04、小结
本文以串行的冒泡排序算法为引，对其并行化问题进行了分析，最后介绍了一种并行冒泡算法与具体实现，希望能够给老铁们带来启发。欢迎老铁们在留言区写下心得，与大家共同交流。
如果本文对老铁有所启发，
请多转发、转载、打赏、点赞！
代码荣耀
程序员都关注了，来不及解释，长按图片，快上车
