一，遗忘比较交换算法

出自算法导论：

遗忘比较交换算法是指算法只按照事先定义好的操作执行，即需要比较的位置下标必须事先确定好。

虽然算法可能依靠待排序元素的个数，但它不能依靠待排序元素的值，也不能依赖任何之前的比较交换操作的结果。

在排序算法一文中有提到，插入排序、选择排序、冒泡排序、归并排序、堆排序、快速排序、希尔排序都是基于比较的排序，而这里面，冒泡排序是遗忘比较，希尔排序是嵌套了其他排序算法的，如果嵌套了遗忘比较算法，那么整个希尔排序也是遗忘比较算法，另外几个都不是遗忘比较算法。

二，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，希尔排序（内嵌冒泡）的排序网络

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/121412679