双调排序
什么是双调排序
百度百科：
双调排序（bitonic sort）属于排序网络(Sorting Network）的一种。相较于传统的排序算法，排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。简单来说，它是一种可以并行计算的排序算法。
very good的百度解释。
简单说：双调排序是比较顺序与数据无关的排序方法，特别适合做并行计算，例如用GPU、FPGA来计算。当要排序的数的个数不是2的幂时，处理时较为困难。
算法实现
以下是个简单实现：
function kernel(x, p, q) {
const d = 1 << (p - q);
for (let i = 0; i < x.length; i++) {
const up = ((i >> p) & 2) === 0;
if ((i & d) == 0 && (x[i] > x[i | d]) === up) {
const tmp = x[i];
x[i] = x[i | d];
x[i | d] = tmp;
}
}
}
function sort(x, n) {
for (let i = 0; i < n; i++) {
for(let j = 0; j <=i; j++) {
kernel(x, i, j);
}
}
}
举个例子：将一个包含从 0 到 255 的混合组合数字的数组sort(x, n)排序：
const n = 8;
const size = 2**n;
const x = Array.from({length: size}, (v, i) => );
x.forEach((v, i) => {
const j = Math.floor(Math.random() * size);
const tmp = x[i];
x[i] = x[j];
x[j] = tmp;
});
console.log(x);
// [75, 16, 59, 28, 110, 199, 188, 144, 10, ...]
sort(x, n);
console.log(x);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
过程如图：
图中显示了排序是如何从左到右进行的，右端是排序完成的状态。蓝色部分按升序排列，绿色部分按降序排列，箭头表示比较值的索引。
如果从水平方向看图像，它大致分为四个块。这是sort函数外的for循环。图中数组的长度很长，循环了四次。
另外，查看每个块的内部，它从左侧块开始按顺序包含 1、2、3、4 四 个子块。sort对应于函数内部的 for 循环。换句话说，kernel函数在一个子块中处理。
kernel函数首先需要满足条件 d = 1 << (p – q) 。该值是从数组索引到要比较索引的距离值。比如，在图像的第四个块的第一个子块中，p = 3, q = 0它d = 1 << (3 – 0) = 8，并且每个索引将索引和值相隔8。
kernel函数比较过程实际上是在for循环中进行的，在必要时会交换值。
对于第一个循环up = ((i >> p) & 2) = 0中的索引将要确定是否按升序排列，或者按值的降序排列。在第一个块中，每次索引前进2时，降序和升序交换，第二个块交换4个，第三个块为8，第四个为16，2^(p+1)依此类推。因此当(i >> p) & 2，p + 1时，可以通过检查位的值来确定是按升序排序还是降序排序的。
与索引比较的索引由 d 分隔。因此，当p – q时，第bit位的值还是0（最右边的位算作第0位）。如果靠近数组开头的索引是 i，p – q则要比较的索引便是 i || d 0 。换句话说，(i & d) 0我们正在检查 if语句中的索引是否更接近数组的开头，x[i] > x[i | d]并且我们正在检查两个值的大小。
GPU是交替写入两个缓冲区的，这个我也实现了kernel函数中值的交换。
function kernel(x, p, q) {
const y = new Array(x.length);
const d = 1 << (p - q);
for (let i = 0; i < x.length; i++) {
const up = ((i >> p) & 2) === 0;
if ((i & d) == 0 && (x[i] > x[i + d]) === up) {
y[i] = x[i + d];
} else if ((i & d) == d && (x[i - d] > x[i]) === up) {
y[i] = x[i - d];
} else {
y[i] = x[i];
}
}
return y;
}
function sort(x, n) {
for (let i = 0; i < n; i++) {
for(let j = 0; j <=i; j++) {
x = kernel(x, i, j);
}
}
return x;
}
const n = 8;
const size = 2**n;
const x = Array.from({length: size}, (v, i) => i);
x.forEach((v, i) => {
const j = Math.floor(Math.random() * size);
const tmp = x[i];
x[i] = x[j];
x[j] = tmp;
});
console.log(x);
const y = sort(x, n);
console.log(y);
code enjoy!😜😜😜
作者：indeex
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。