有一定了解的可以直接看最后一部分的代碼。
雙調(diào)排序是一種并行排序算法。
- 如果以串行的方式運行，其復(fù)雜度：O(nlog(n))
- 如果有 n（其實是 n/2） 個可同時運行的線程，則復(fù)雜度：O(log(n))。
上面的復(fù)雜度是基于輸入序列為雙調(diào)序列。
雙調(diào)序列
雙調(diào)序列(Bitonic Sequence) 是指由一個 非嚴格增序列X 和 非嚴格減序列Y 構(gòu)成的序列，任意兩個數(shù)，都是雙調(diào)序列。
（非嚴格指的是可以出現(xiàn)重復(fù)元素，或者NaN不參與排序）
定義：一個序列 a1,a2, …,an 是雙調(diào)序列(Bitonic Sequence)，如果：
（1）存在一個 ak(1 ≤ k ≤ n)，使得 a1 ≥ … ≥ ak ≤ … ≤ an 成立；或者
（2）序列能夠循環(huán)移位滿足條件(1)
條件（2）非常重要，因為好多序列表面不是，其實是雙調(diào)的。
雙調(diào)排序
基本的雙調(diào)排序只能處理 2^n 個數(shù)的序列。
首先定義操作 sortSeq，輸出是一個雙調(diào)序列。
下圖中 s 為雙調(diào)序列，s1 為升序（紅），s2 為降序（藍）。
交換之后，s1 中的序列就是兩兩比較的較小值，s2 的序列就是兩兩比較的較大值。本來 s1是升序，s2 是降序的，經(jīng)過如此操作之后，s1，s2 都是雙調(diào)的，參考紅藍多邊形。在構(gòu)建 s1 和 s2 時，可以用 n/2 個線程對兩兩元素進行比較交換，從而實現(xiàn)并行運算。
再對 s1，s2 分別進行 sortSeq 操作，就這樣遞歸操作，直到傳入 sortSeq 的序列長度為2，最終 s 就是升序排列的。
下面舉個例子說明雙調(diào)排序過程：
初始值：(10 11 13 14 15 16 17 18, 19 15 13 12 12 11 9 8)
(10 11 13 14 15 16 17 18) (19 15 13 12 12 11 9 8)
網(wǎng)絡(luò)1排序： (10 11 13 12 12 11 9 8) (19 15 13 14 15 16 17 18)
(10 11 13 12) (12 11 9 8) (19 15 13 14) (15 16 17 18)
網(wǎng)絡(luò)2排序→ (10 11 9 8) (12 11 13 12) (15 15 13 14) (19 16 17 18)
(10 11) (9 8) (12 11) (13 12) (15 15) (13 14) (19 16) (17 18)
網(wǎng)絡(luò)3排序→ (9 8) (10 11) (12 11) (13 12) (13 14) (15 15) (17 16) (19 18)
最終結(jié)果：(8 9 10 11 11 12 12 13 13 14 15 15 16 17 18 19)
網(wǎng)絡(luò)2排序的結(jié)果中 (12 11 13 12) 經(jīng)過循環(huán)位移之后也是雙調(diào)序列。
那么如何構(gòu)建最初的雙調(diào)序列？
雙調(diào)排序的初始序列是雙調(diào)序列，所以對于普通的無序數(shù)列要先轉(zhuǎn)換。
算法采用 自底向上 的方法逐步構(gòu)建雙調(diào)序列，因為任意兩個數(shù)都可以視為雙調(diào)序列。
（1）將無序的輸入序列轉(zhuǎn)換成雙調(diào)序列
對于無序數(shù)組 A，相鄰的兩個數(shù)肯定是雙調(diào)序列，比如 (a0,a1), (a2,a3) 等等
首先步長為 2：(a0,a1) 傳入 sortSeq，變成升序序列，
(a2,a3) 傳入 sortSeq，變成降序序列，……
然后步長為 4：(a0,a1,a2,a3) 是雙調(diào)序列，傳入 sortSeq 變成升序序列，
(a4,a5,a6,a7) 也是雙調(diào)的，傳入 sortSeq 變成降序序列，……
步長依次為 2^n：
……
最后變?yōu)榍?n/2 元素是升序，后 n/2 是降序的完整雙調(diào)序列。
無序變雙調(diào)
將無序的輸入序列轉(zhuǎn)換成雙調(diào)序列
上圖中，16個數(shù)據(jù)，8個比較器，無序數(shù)列需要 log(8) = 3 部分完成全局雙調(diào)序列，步長分別為：20，21，22。理解為 1 增序、2 增序、4 增序。
- 設(shè)比較的步長為 s，則比較的層數(shù)為 log(s)+1，理解為自頂向下比較的層數(shù)
- 每一層都比較 8 次。（8個比較器）
所以比較的總次數(shù)為：(1+2+3) * 8 = 48
（2）雙調(diào)序列合并成為有序序列
完整的雙調(diào)序列傳入 sortSeq 變成完整的升序序列。
這一部分，步長為 8，比較層數(shù)為 4。
構(gòu)建雙調(diào)序列：自底向上
排序雙調(diào)序列：自頂向下
雙調(diào)合并網(wǎng)絡(luò)
綜上，雙調(diào)排序比較的總次數(shù)為：(1+2+3+4) * 8 = 80
下面的代碼分為：
- 基本雙調(diào)排序（非遞歸）（2^n）
- 顯示排序過程的雙調(diào)排序（非遞歸）（2^n）
- 基本雙調(diào)排序（遞歸）（2^n）
- 任意雙調(diào)排序（遞歸）（任意正數(shù)）（真正普適的雙調(diào)排序）
1. 基本雙調(diào)排序（非遞歸）（2^n）
#include <iostream>
#include <iomanip>
using namespace std;
void printArr(int *arr, int len) {
for (int i = 0; i < len; ++i) {
cout << setw(3) << arr[i];
}
cout << endl << endl;
}
// 雙調(diào)排序
void bitonicSort(int *arr, int len, bool asd) { // asd 升序
int step = len / 2; // len = 2^k
for (; step > 0; step /= 2) {
for (int i = 0; i < len; i += 2 * step) { // 2 * step 一組序列
for (int j = i; j < i + step; ++j) { // 遍歷序列內(nèi)部，i是序列起點
if (asd) {
if (arr[j] > arr[j + step]) swap(arr[j], arr[j + step]);
} else {
if (arr[j] < arr[j + step]) swap(arr[j], arr[j + step]);
}
}
}
}
}
int main() {
int len = 16;
auto *arr = new int[len]; // 自動識別類型
bool asd = true;
// 1.隨機生成無序序列
srand((unsigned int) time(nullptr));
for (int i = 0; i < len; ++i) {
arr[i] = (int) random() % 100;
}
cout << "無序序列: ";
printArr(arr, len);
// 2.將無序的輸入序列轉(zhuǎn)換成雙調(diào)序列
for (int step = 2; step < len; step *= 2) {
for (int i = 0; i < len; i += 2 * step) {
bitonicSort(arr + i, step, asd);
bitonicSort(arr + step + i, step, !asd);
}
}
cout << "雙調(diào)序列: ";
printArr(arr, len); // 雙調(diào)序列
// 3.雙調(diào)序列合并成為有序序列
bitonicSort(arr, len, asd);
cout << "有序序列: ";
printArr(arr, len); // 有序序列
}
無序序列: 26 25 38 50 29 19 91 80 7 46 15 78 19 32 86 66
雙調(diào)序列: 19 25 26 29 38 50 80 91 86 78 66 46 32 19 15 7
有序序列: 7 15 19 19 25 26 29 32 38 46 50 66 78 80 86 91
2. 顯示排序過程的雙調(diào)排序（非遞歸）（2^n）
#include <iostream>
#include <iomanip>
using namespace std;
void printArr(int *arr, int len) {
for (int i = 0; i < len; ++i) {
cout << setw(3) << arr[i];
}
cout << endl << endl;
}
// 雙調(diào)排序
void sortSeq(int *arr, int len, bool asd) {
int step = len / 2;
for (; step > 0; step /= 2) {
for (int i = 0; i < len; i += 2 * step) {
for (int j = 0; j < step; ++j) {
if (asd) {
if (arr[i + j] > arr[i + step + j]) swap(arr[i + j], arr[i + step + j]);
} else {
if (arr[i + j] < arr[i + step + j]) swap(arr[i + j], arr[i + step + j]);
}
}
}
cout << "步長為: " << step << ", ";
cout << "序列長: " << len << ", ";
printArr(arr, len);
}
}
int main() {
int len = 16;
int *arr = new int[len];
srand((unsigned) time(NULL));
for (int i = 0; i < len; ++i) {
arr[i] = rand() % 100;
}
cout << "初始數(shù)據(jù)" << endl;
printArr(arr, len);
bool asd = true;
for (int step = 2; step < len; step *= 2) {
for (int i = 0; i < len; i += 2 * step) {
sortSeq(arr + i, step, asd); // 前半升序
sortSeq(arr + i + step, step, !asd); // 后半降序
}
}
cout << "雙調(diào)序列" << endl;
printArr(arr, len);
sortSeq(arr, len, asd);
cout << "雙調(diào)排序" << endl;
printArr(arr, len);
}
初始數(shù)據(jù)
36 15 27 57 4 32 69 46 76 99 21 31 92 31 90 13
# 自底向上的構(gòu)建過程中也包含了自頂向下的排序過程
步長為: 1, 序列長: 2, 15 36
步長為: 1, 序列長: 2, 57 27
步長為: 1, 序列長: 2, 4 32
步長為: 1, 序列長: 2, 69 46
步長為: 1, 序列長: 2, 76 99
步長為: 1, 序列長: 2, 31 21
步長為: 1, 序列長: 2, 31 92
步長為: 1, 序列長: 2, 90 13
步長為: 2, 序列長: 4, 15 27 57 36
步長為: 1, 序列長: 4, 15 27 36 57
步長為: 2, 序列長: 4, 69 46 4 32
步長為: 1, 序列長: 4, 69 46 32 4
步長為: 2, 序列長: 4, 31 21 76 99
步長為: 1, 序列長: 4, 21 31 76 99
步長為: 2, 序列長: 4, 90 92 31 13
步長為: 1, 序列長: 4, 92 90 31 13
步長為: 4, 序列長: 8, 15 27 32 4 69 46 36 57
步長為: 2, 序列長: 8, 15 4 32 27 36 46 69 57
步長為: 1, 序列長: 8, 4 15 27 32 36 46 57 69
步長為: 4, 序列長: 8, 92 90 76 99 21 31 31 13
步長為: 2, 序列長: 8, 92 99 76 90 31 31 21 13
步長為: 1, 序列長: 8, 99 92 90 76 31 31 21 13
雙調(diào)序列
4 15 27 32 36 46 57 69 99 92 90 76 31 31 21 13
# 自頂向下完成雙調(diào)序列的排序
步長為: 8, 序列長: 16, 4 15 27 32 31 31 21 13 99 92 90 76 36 46 57 69
步長為: 4, 序列長: 16, 4 15 21 13 31 31 27 32 36 46 57 69 99 92 90 76
步長為: 2, 序列長: 16, 4 13 21 15 27 31 31 32 36 46 57 69 90 76 99 92
步長為: 1, 序列長: 16, 4 13 15 21 27 31 31 32 36 46 57 69 76 90 92 99
雙調(diào)排序
4 13 15 21 27 31 31 32 36 46 57 69 76 90 92 99
3. 基本雙調(diào)排序（遞歸）（2^n）
根據(jù) 01 原則，遞歸時分治的兩段必須 前半降序，后半升序。
#include <iostream>
#include <iomanip>
using namespace std;
void printArr(int *arr, int len) {
for (int i = 0; i < len; ++i) {
cout << setw(3) << arr[i];
}
cout << endl << endl;
}
// 由bitonicSort中的順序可知，這里傳入的arr已是雙調(diào)序列
void bitonicMerge(int *arr, int len, bool asd) {
if (len > 1) {
int m = len / 2;
for (int i = 0; i < m; ++i) {
if (arr[i] > arr[i + m] == asd)
swap(arr[i], arr[i + m]); // 根據(jù)asd判斷是否交換
}
// for循環(huán)結(jié)束后又生成了2個雙調(diào)序列，分別merge直到序列長度為1
bitonicMerge(arr, m, asd); // 都是按照asd進行merge
bitonicMerge(arr + m, m, asd);
}
}
void bitonicSort(int *arr, int len, bool asd) { // asd 升序
if (len > 1) {
int m = len / 2;
bitonicSort(arr, m, !asd); // 前半降序
bitonicSort(arr + m, len - m, asd); // 后半升序
// 前2個sort之后形成了1個雙調(diào)序列，然后傳入merge合并成asd規(guī)定的序列
bitonicMerge(arr, len, asd); // 合并
}
}
int main() {
int len = 16;
auto *arr = new int[len]; // 自動識別類型
bool asd = true;
// 1.隨機生成無序序列
srand((unsigned int) time(nullptr));
for (int i = 0; i < len; ++i) {
arr[i] = (int) random() % 100;
}
cout << "無序序列: ";
printArr(arr, len);
// 2.雙調(diào)排序
bitonicSort(arr, len, asd);
cout << "雙調(diào)排序: ";
printArr(arr, len);
}
無序序列: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26
雙調(diào)排序: 15 21 26 27 35 49 59 62 63 77 83 86 86 90 92 93
4. 任意雙調(diào)排序（遞歸）（任意正數(shù)）
遞歸實現(xiàn)的任意雙調(diào)排序與基本雙調(diào)排序區(qū)別在于歸并部分
// 基本雙調(diào)排序歸并
void bitonicMerge(int *arr, int len, bool asd) {
if (len > 1) {
int m = len / 2;
for (int i = 0; i < m; ++i) {
if (arr[i] > arr[i + m] == asd)
swap(arr[i], arr[i + m]); // 根據(jù)asd判斷是否交換
}
// for循環(huán)結(jié)束后又生成了2個雙調(diào)序列，分別merge直到序列長度為1
bitonicMerge(arr, m, asd);
bitonicMerge(arr + m, m, asd);
}
}
// 任意雙調(diào)排序歸并
void bitonicMergeAnyN(int *arr, int len, bool asd) {
if (len > 1) {
int m = getGreatest2nLessThan(len);
for (int i = 0; i < len - m; ++i) {
if (arr[i] > arr[i + m] == asd)
swap(arr[i], arr[i + m]); // 根據(jù)asd判斷是否交換
}
bitonicMergeAnyN(arr, m, asd); // 一般情況下，m > len-m
bitonicMergeAnyN(arr + m, len - m, asd);
}
}
對于任意雙調(diào)排序，因為 len 不一定等于 2^n，所以 m 取 Greatest2nLessThan(len)，即在滿足 2^n < len 的情況下，n 取最大值時，m = 2^n，對于基本雙調(diào)排序，len = 2^n，m = len/2 也即為Greatest2nLessThan(len)。
任意雙調(diào)排序主要思想：
- 首先不斷的二分，直到每組只剩下一個元素，然后開始歸并。
- 雙調(diào)排序歸并時以不大于 n 的最大 2 的冪次方 2k 為界限，把 2k..n 的元素分別與 0..(n-2k) 的元素比較，然后再分別在0..2k 和 2k..n 這兩段上分別應(yīng)用比較網(wǎng)絡(luò)。
- 雙調(diào)排序難以理解的地方就在于這個歸并的過程，假設(shè)我們要把長度為 n 的序列 arr 升序排列，由于二分時是把前 n/2 的序列降序排列后 n/2 的序列升序排列的，而 n-2k < n/2，所以前 n-2k 和后 n-2k 個元素都大于中間的元素，當前 n-2k 個元素和后 n-2k 個元素比較時，會把序列中最大的 n-2k 個元素放到最后 n-2k 個位置上，也就是說比較后，2k..n 的元素都比 0..2k 的元素大（這一點是確定的，因為前半段遞減，后半段遞增，比較的時候相當于“極大值”與“極小值”的比較，有點田忌賽馬的味道），這樣在分別對這兩段用同樣的方法歸并，最終得到完整的升序序列。
雙調(diào)排序分治的核心理論：任意的正整數(shù)都能表示成 2 的冪指數(shù)和的形式，其實就是所有的正整數(shù)都能用二進制表示。因為序列在不斷地拆分成 2 的冪指數(shù)的長度。
n = 6, 4+2
n = 7, 4+3 = 4+2+1
n = 8, 4+4
舉個例子：
以6個元素的序列為例，前3個元素已經(jīng)降序排好，后3個元素已經(jīng)升序排好（遞歸到底時是從1個元素開始返回的，所以對6個元素歸并時前后3個元素已經(jīng)排好序），這個以4（不大于6的最大2的冪次方）為界限，分別讓第1個和第5個、第2個和第6個元素比較，使得這6個元素中最大的兩個處于第5、6個位置上，然后再分別對前4個和后2個元素按此方法歸并，最終遞歸完成排序。
然后在 bitonicSort 函數(shù)中，只需將 bitonicMerge 改為 bitonicMergeAnyN，另外，bitonicSort 分治的兩段長度不一定相等，即 m >= len-m，只有當 len = 2^n 時，m = len-m = len/2，此時任意雙調(diào)排序?qū)嶋H為基本雙調(diào)排序。
void bitonicSort(int *arr, int len, bool asd) { // asd 升序
if (len > 1) {
int m = len / 2;
bitonicSort(arr, m, !asd); // 前半降序
bitonicSort(arr + m, len - m, asd); // 后半升序
// 前2個sort之后形成了雙調(diào)序列，然后傳入merge合并成asd規(guī)定的序列
// bitonicMerge(arr, len, asd); // 注釋掉基本雙調(diào)排序
bitonicMergeAnyN(arr, len, asd);
}
}
完整代碼
#include <iostream>
#include <iomanip>
using namespace std;
void printArr(int *arr, int len) {
for (int i = 0; i < len; ++i) {
cout << setw(3) << arr[i];
}
cout << endl << endl;
}
int getGreatest2nLessThan(int len) {
int k = 1;
while (k < len) k = k << 1; // 注意一定要加k=
return k >> 1;
}
// 基本雙調(diào)排序歸并
void bitonicMerge(int *arr, int len, bool asd) {
if (len > 1) {
int m = len / 2;
for (int i = 0; i < m; ++i) {
if (arr[i] > arr[i + m] == asd)
swap(arr[i], arr[i + m]); // 根據(jù)asd判斷是否交換
}
// for循環(huán)結(jié)束后又生成了2個雙調(diào)序列，分別merge直到序列長度為1
bitonicMerge(arr, m, asd);
bitonicMerge(arr + m, m, asd);
}
}
// 任意雙調(diào)排序歸并
void bitonicMergeAnyN(int *arr, int len, bool asd) {
if (len > 1) {
int m = getGreatest2nLessThan(len);
for (int i = 0; i < len - m; ++i) {
if (arr[i] > arr[i + m] == asd)
swap(arr[i], arr[i + m]); // 根據(jù)asd判斷是否交換
}
bitonicMergeAnyN(arr, m, asd); // 一般情況下，m > len-m
bitonicMergeAnyN(arr + m, len - m, asd);
}
}
// 雙調(diào)排序（基本 + 任意）
void bitonicSort(int *arr, int len, bool asd) { // asd 升序
if (len > 1) {
int m = len / 2;
bitonicSort(arr, m, !asd); // 前半降序
bitonicSort(arr + m, len - m, asd); // 后半升序
// 前2個sort之后形成了雙調(diào)序列，然后傳入merge合并成asd規(guī)定的序列
// bitonicMerge(arr, len, asd); // 注釋掉基本雙調(diào)排序
bitonicMergeAnyN(arr, len, asd);
}
}
int main() {
int len = 16;
auto *arr = new int[len]; // 自動識別類型
bool asd = true;
// 1.隨機生成無序序列
srand((unsigned int) time(nullptr));
for (int i = 0; i < len; ++i) {
arr[i] = (int) random() % 100;
}
cout << "無序序列: ";
printArr(arr, len);
// 2.雙調(diào)排序
bitonicSort(arr, len, asd);
cout << "雙調(diào)排序: ";
printArr(arr, len);
}
無序序列: 83 86 77 15 93 35 86 92 49 21 62
雙調(diào)排序: 15 21 35 49 62 77 83 86 86 92 93
