一，遗忘比较交换算法
出自算法导论：
遗忘比较交换算法是指算法只按照事先定义好的操作执行，即需要比较的位置下标必须事先确定好。
虽然算法可能依靠待排序元素的个数，但它不能依靠待排序元素的值，也不能依赖任何之前的比较交换操作的结果。
在排序算法一文中有提到，插入排序、选择排序、冒泡排序、归并排序、堆排序、快速排序、希尔排序都是基于比较的排序，而这里面，冒泡排序是遗忘比较，希尔排序是嵌套了其他排序算法的，如果嵌套了遗忘比较算法，那么整个希尔排序也是遗忘比较算法，另外几个都不是遗忘比较算法。
二，0-1排序引理
0-1排序引理：如果一个遗忘比较交换算法能够对所有只包含0和1的输入序列排序，那么它也可以对包含任意值的输入序列排序。
三，列排序
即使不知道奇数步中，对每一列的排序采取的是什么排序算法，我们仍然可以认为，列排序算法是遗忘比较交换算法。
书中后面有提示，如何根据0-1排序引理证明上述八步操作可以完成排序，不难，略。
以s=5为例，我们把数组的长度补到50的倍数x（x>=250），那么r=x/5，r>=50，即满足条件，排序完成之后再把多余的元素删掉即可。
代码：
template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
if (len < 250 || len % 50) {
int b = max(len / 50, 5);
int len2 = b * 50;
T m = GetMax(arr, len);
T* p = new T[len2];
for (int i = 0; i < len; i++)p[i] = arr[i];
for (int i = len; i < len2; i++)p[i] = m;
Sort(p, len2, cmp);
for (int i = 0; i < len; i++)arr[i] = p[i];
return;
}
const int s = 5;
int r = len / s; //r行s列
T* p = new T[len];
for (int i = 0; i < len; i += r)Sort2(arr + i, r, cmp);//每一列排序
for (int i = 0; i < len; i++) p[i / s + i % s * r] = arr[i];//转置
for (int i = 0; i < len; i += r)Sort2(p + i, r, cmp);//每一列排序
for (int i = 0; i < len; i++) arr[i] = p[i / s + i % s * r];//逆转置
for (int i = 0; i < len; i += r)Sort2(arr + i, r, cmp);//每一列排序
for (int i = r / 2; i < len - r; i += r)Sort2(arr + i, r, cmp);//最后一次排序
}其中的sort2是调用别的排序算法，比如插入排序。
四，比较网络
来自?OI之外的一些东西：简单谈谈排序网络 | Matrix67: The Aha Moments
1，比较算子
对于一个数列{ai}，任取2个数ai和aj，比较大小并（可能）交换位置，使得ai<=aj成立，这样的一个操作叫比较算子。
PS：可以理解为这是递增比较算子，对应的还有一个递减比较算子。
2，比较网络
一系列有序的比较算子，构成一个比较网络。
例如下面是4个比较算子构成的网络：
3，比较网络的可并行性
以上面的网络为例，中间的2个比较算子，如果改变先后顺序，或者说同时操作，显然整个网络的结果是一样的。
五，排序网络
1，排序网络
如果一个比较网络对于任何输入数列，输出的都是有序数列，那么称这个比较网络为排序网络。
上面的比较网络不是排序网络，如输入3 1 4 2输出的是1 3 2 4，不是有序的。
2，排序网络的判定
排序网络和遗忘比较交换算法是对应的。
所以判定一个比较网络是不是排序网络，可以用0-1排序引理。
即如果一个比较网络能够对所有只包含0和1的输入序列排序，那么它就是排序网络。
3，冒泡排序的排序网络
?可以调整为：
?这样，就可以提高并行程度，加快速度。
4，希尔排序（内嵌冒泡）的排序网络
?