Chapter 10 排序

1. 概述
   1. 串行排序回顾
   2. 加速比
2. 比较和交换
3. 冒泡排序 和奇偶互换排序（并行冒泡）
4. 并行归并排序
5. 并行快速排序
6. 奇偶归并排序
7. 双谐调归并排序
8. 秩排序
9. 计数排序
10. 基数排序
11. 采样排序

比较

冒泡排序

下一次的比较交换动作可以在前一次完全完成之前就开始， 只要其操作不影响前一次的冒泡即可。

• 整个过程分为奇阶段和偶阶段（从0开始）
• 在偶阶段，偶数编号的数与其右侧的数进行比较交换操作。（数的排序也从0开始）
• 在奇阶段，奇数编号的数与其右侧的数进行比较交换操作。

在并行环境下复杂度为O（n）。（n个进程,每个进程一个数）

归并排序

归并操作

归并算法

归并排序可以直接映射为并行模式

复杂度为O（n）。

快速排序

最优为O(n)

奇偶归并排序

1. Let A and B be sorted lists of length n, n is even
2. Let OM be the sorted list of length n formed by sorting the elements in the odd positions (1, 3, 5, ...) of A and B
3. Let EM be the sorted list of length n formed by sorting the elements in the even positions (2, 4, 6, ...) of A and B
4. Let R be the sorted list of size 2n formed by merging A and B.

5. Let AJ, BJ, OMJ, EMJ, RJ be the J'th element of the corresponding lists A, B, OM, EM, R.

6. Example

7. A 1 2 3 15 20 21

8. B 6 7 8 9 10 30

9. OM 1 3 6 8 10 20

10. EM 2 7 9 15 21 30
11. R 1 2 3 6 7 8 9 10 15 20 21 30

Lemma.

• R1 = OM1, R2n = EMn
• R2k = min(OMk+1, EMk)
• R2k+1 = max(OMk+1, EMk)

并行算法

1. n个数,n个进程
2. 总体复杂度O（log^2（2，n））,资料显示为nlog^2(2,n)

双调归并排序

对无序数列的排序:

1. 第一步：
   1. 先把数分成两两的数对。通过比较和交换操作，邻进的数对形成升序或降序数列。（左升右降）
   2. 短序列归并为长序列
   3. 重复以上过程直到整个数列变为一个大的双调数列
2. 第二步：
   1. 对此数列进行折半比较交换，方法同前。
   2. 如果是奇数个，随机复制一个，随后删除之。

秩排序-n*n个处理器

复杂度O(n)

复杂度O(log(n))

计数排序

设数的范围为1-m

for (i = n; i >= 1; i--) 
            {
        b[c[a[i]]] = a[i]
        c[a[i]]--;   /* ensures stable sorting */
}

复杂度O(n+m)

基排序