并发算法之并行排序

大部分排序算法都是串行执行的，当排序元素很多时，使用并行排序算法可以有效利用CPU，提高运算效率，但将串行算法改成并行算法将会极大的增加原有算法的复杂度。

1、分离数据相关性：奇偶交换排序

冒泡排序：如果数据较小，会逐步被交换到前面，对于大的数字会下沉，交换到数组的尾部。

冒泡排序算法

在每次迭代交换过程中，由于每次交换的两个元素存在数据冲突，对于每个元素，它既可能与前面的元素交换，也可能与后面的元素交换，因此很难直接改成并行算法。如果能够解开这种数据的相关性，就可以更容易的使用并行算法，奇偶交换排序就是基于这种思想的。

对于奇偶交换排序，它将排序过程分成两个阶段，奇交换和偶交换。奇交换总是比较奇数索引及其相邻的后续元素，而偶交换总是比较偶数索引及其相邻的后续元素。并且奇交换和偶交换会成对出现，这样才能保证比较和交换涉及到数组中的每一个元素。在每个阶段内，所有的比较和交换是没有数据相关性的，每次比较和交换都可以独立执行。

奇偶交换排序的串行实现

flag用来记录当前迭代释放发生了数据交换，start用来表示奇交换或偶交换。初始start=0，表示进行偶交换，每次迭代结束切换start状态。如果上次比较交换发生了数据交换，或当前正在进行的是奇交换，循环不会停止，直到不再发生交换，并且当前进行的是偶交换为止。

奇偶交换排序的并行实现

2、改进的插入排序：希尔排序

插入排序思想：一个未排序的数组可以分为两部分，前半部分是已排序的，后半部分是未排序的，在进行排序时，只需在未排序的部分中选择一个元素，将其插入到前面有序的数组中即可。最终未排序的部分越来越少，直至为0排序完成。

插入排序示例

插入排序很难并行化，因为上一次的数据插入依赖于上一次得到的有序序列，多个步骤之间无法并行。

希尔排序将整个数组根据间隔h分割为若干个子数组，子数组相互穿插在一起，每次排序时分别对每一个子数组进行排序。每次排序时总是交换间隔为h的两个元素。在每组排序完成后，可以递减h的值，进行下轮排序，直到h=1，此时等价于一次插入排序。

希尔排序优点：即使一个较小的元素在数组末尾，由于每次元素移动都以间隔h进行，数组末尾的元素可以在很少的交换次数下，被置换到最接近元素最终位置的地方。

希尔排序串行示例

改造成并行希尔排序：

希尔排序并行示例 希尔排序并行示例

--参考文献《实战Java高并发程序设计》