【算法设计与分析】5个数7次比较排序的算法

找到最快的算法，一直是计算机界的目标之一，而排序就是其中最基本的算法。什么样的排序才是最快的呢？

1.最少的比较次数，算法理论证明n个数排序，如果是基于比较的算法，至少需要 ㏒(n!) 向上取整数。下面给出小数目下，最少比较次数：

   

n 1 2 3 4 5 6 7 8
㏒(n!) 0 1 3 5 7 10 13 16

2.移动次数最少，根据群论置换群理论，n个数的序列，变换到这n个数组成另一个序列，一定可以在最多n次移动内做到。

    在理论的指引下，人们开始寻找这些传说中的极限。人们开始简单地完成了n=1,2,3,4的极限算法，但是当n=5时，人们长期停留在了8次比较。但是在1956年，H.B.Demuth在终于首先找到5个次7次比较的排序方法，并在他的博士论文中进行了阐述。下面就是对这个算法的C语言实现：

[cpp] view plaincopy
  1. /* 1956年H.B.Demuth找到的5个数7次的比较方法，后来Lester Ford,Selmer Johnson归并插入排序中使用*/  
  2.   
  3.         /******************************************************************** 
  4.          *      示意图如下                                                  * 
  5.          *                                                                  * 
  6.          *    [0] [1] 排序得 [0]<=[1]                                       * 
  7.          *    [2] [3] 排序得 [2]<=[3]                                       * 
  8.          *    [1] [3] 排序得 [1]<=[3]                                       * 
  9.          *    此时有关系：[0]<=[3],,[2]<=[1]<=[3]                           * 
  10.          *                                                                  * 
  11.          *                          [1] [4]                                 * 
  12.          *                      _______|_______                             * 
  13.          *                     |               |                            * 
  14.          *                 [1]<=[4]         [1]>[4]                         * 
  15.          *                 ___|___          ___|___                         * 
  16.          *                |       |        |       |                        * 
  17.          *            [0]<=[1] [0]>[1] [2]<=[4] [2]>[4]                     * 
  18.          *               ①      ②       ③      ④                        * 
  19.          *                                                                  * 
  20.          *   情况①：[0][2]比较一次，[3][4]比较一次，即可确定顺序           * 
  21.          *   情况②：[0][4]比较一次，[0]<=[4]则[3][4]再比较一次             * 
  22.          *   情况③：[0][4]比较一次，[0]<=[4]则比较[0][2],否则比较[0][1]    * 
  23.          *   情况④：[0][2]比较一次，[0]<=[2]则比较[0][4],否则比较[0][1]    * 
  24.          *                                                                  * 
  25.          *   伪代码如下：                                                   * 
  26.          *   SORT([0],[1]);                                                 * 
  27.          *   SORT([2],[3]);                                                 * 
  28.          *   SORT([1],[3]);                                                 *                                                              
  29.          *   IF [1]<=[4]                                                    * 
  30.          *      IF [0]<=[1]                                                 * 
  31.          *          IF [0]<=[2]                                             * 
  32.          *              IF [3]<=[4]  ①                                     * 
  33.          *              ELSE         ②                                     * 
  34.          *          ELSE                                                    * 
  35.          *              IF [3]<=[4]  ③                                     * 
  36.          *              ELSE         ④                                     * 
  37.          *      ELSE                                                        * 
  38.          *          IF [0]<=[4]                                             * 
  39.          *              IF [3]<=[4]  ⑤                                     * 
  40.          *              ELSE         ⑥                                     * 
  41.          *          ELSE             ⑦                                     * 
  42.          *   ELSE                                                           * 
  43.          *      IF [2]<=[4]                                                 * 
  44.          *          IF [0]<=[4]                                             * 
  45.          *              IF [0]<=[2]  ①                                     * 
  46.          *              ELSE         ②                                     * 
  47.          *          ELSE                                                    * 
  48.          *              IF [0]<=[1]  ③                                     * 
  49.          *              ELSE         ④                                     * 
  50.          *       ELSE                                                       * 
  51.          *          IF [0]<=[2]                                             * 
  52.          *              IF [0]<=[4]  ⑤                                     * 
  53.          *              ELSE         ⑥                                     * 
  54.          *          ELSE                                                    * 
  55.          *              IF [0]<=[1]  ⑦                                     * 
  56.          *              ELSE         ⑧                                     * 
  57.          *     共15种情形，针对每种情形都可以有最佳移动顺序 0-8次,平均4.5次 * 
  58.          ********************************************************************/  
  59.   
  60.   
  61.         /*比较[0][1]*/  
  62.         if( arr[0] > arr[1])   
  63.             swap(arr[0],arr[1]);  
  64.         /*比较[2][3]*/  
  65.         if( arr[2] > arr[3])  
  66.             swap(arr[2],arr[3]);  
  67.         /*比较[1][3]*/  
  68.         if( arr[1] > arr[3])  
  69.             swap(arr[1],arr[3]);  
  70.           
  71.   
  72.         if( arr[1] <= arr[4] )  
  73.         {  
  74.             if( arr[0] <= arr[1])  
  75.             {  
  76.                 if( arr[0] <= arr[2] )  
  77.                 {  
  78.                     if( arr[3] <= arr[4] )  
  79.                     {   /* ① 正确顺序为：[0][2][1][3][4]*/  
  80.                         swap(arr[1],arr[2]);  
  81.                         return 0;  
  82.                     }  
  83.                     else/*②正确顺序为：[0][2][1][4][3]*/  
  84.                     {  
  85.                         swap(arr[1],arr[2]);  
  86.                         swap(arr[3],arr[4]);  
  87.                         return 0;                         
  88.                     }  
  89.                 }  
  90.                 else/* arr[3] >= arr[1] >= arr[0] > arr[2] */  
  91.                 {  
  92.                     if( arr[3] <= arr[4])/*③正确顺序为：[2][0][1][3][4]*/  
  93.                     {  
  94.                         int temp = arr[2];  
  95.                         arr[2] = arr[1];  
  96.                         arr[1] = arr[0];  
  97.                         arr[0] = temp;  
  98.                         return 0;                         
  99.                     }  
  100.                     else/*④正确顺序为：[2][0][1][4][3]*/  
  101.                     {  
  102.                         int temp = arr[2];  
  103.                         arr[2] = arr[1];  
  104.                         arr[1] = arr[0];  
  105.                         arr[0] = temp;  
  106.                         swap(arr[3],arr[4]);  
  107.                         return 0;                     
  108.                     }                 
  109.                 }             
  110.             }  
  111.             else/* arr[1]<= arr[4] && arr[0] > arr[1] */  
  112.             {  
  113.                 if( arr[0] <= arr[4])  
  114.                 {  
  115.                     if( arr[3] <= arr[4])/* ⑤正确顺序为[2][1][0][3][4]*/  
  116.                     {  
  117.                         swap(arr[0],arr[2]);  
  118.                         return 0;  
  119.                     }  
  120.                     else/* ⑥正确顺序为[2][1][0][4][3]*/  
  121.                     {  
  122.                         swap(arr[0],arr[2]);  
  123.                         swap(arr[3],arr[4]);  
  124.                         return 0;  
  125.                     }  
  126.                 }  
  127.                 else/* ⑦正确顺序为[2][1][4][0][3]*/  
  128.                 {  
  129.                     int temp = arr[4];  
  130.                     arr[4] = arr[3];  
  131.                     arr[3] = arr[0];  
  132.                     arr[0] = arr[2];  
  133.                     arr[2] = temp;  
  134.                     return 0;  
  135.                 }  
  136.             }  
  137.           
  138.         }  
  139.         else/* arr[1] > arr[4] */  
  140.         {  
  141.             if( arr[2] <= arr[4] )/* [2][4][1][3]*/  
  142.             {  
  143.                 if( arr[0] <= arr[4] )  
  144.                 {  
  145.                     if( arr[0] <= arr[2])/*①正确顺序为[0][2][4][1][3]*/  
  146.                     {  
  147.                         int temp = arr[4];  
  148.                         arr[4] = arr[3];  
  149.                         arr[3] = arr[1];  
  150.                         arr[1] = arr[2];  
  151.                         arr[2] = temp;  
  152.                         return 0;  
  153.                     }  
  154.                     else/*②正确顺序为[2][0][4][1][3]*/  
  155.                     {  
  156.                         int temp = arr[4];  
  157.                         arr[4] = arr[3];  
  158.                         arr[3] = arr[1];  
  159.                         arr[1] = arr[0];  
  160.                         arr[0] = arr[2];  
  161.                         arr[2] = temp;  
  162.                         return 0;  
  163.                     }  
  164.                 }  
  165.                 else  
  166.                 {  
  167.                     if( arr[0] <= arr[1] )/*③正确顺序为[2][4][0][1][3]*/  
  168.                     {  
  169.                         int temp = arr[4];  
  170.                         arr[4] = arr[3];  
  171.                         arr[3] = arr[1];  
  172.                         arr[1] = temp;  
  173.                         swap(arr[0],arr[2]);  
  174.                         return 0;                     
  175.                     }  
  176.                     else/*④正确顺序为[2][4][1][0][3]*/  
  177.                     {  
  178.                         int temp = arr[4];  
  179.                         arr[4] = arr[3];  
  180.                         arr[3] = arr[0];  
  181.                         arr[0] = arr[2];  
  182.                         arr[2] = arr[1];  
  183.                         arr[1] = temp;  
  184.                         return 0;  
  185.                     }  
  186.                 }  
  187.             }  
  188.             else/* [4][2][1][3] */  
  189.             {  
  190.                 if( arr[0] <= arr[2] )  
  191.                 {  
  192.                     if( arr[0] <= arr[4] )/*⑤正确顺序为[0][4][2][1][3]*/  
  193.                     {  
  194.                         int temp = arr[4];  
  195.                         arr[4] = arr[3];  
  196.                         arr[3] = arr[1];  
  197.                         arr[1] = temp;  
  198.                         return 0;  
  199.                     }  
  200.                     else/*⑥正确顺序为[4][0][2][1][3]*/  
  201.                     {  
  202.                         int temp = arr[4];  
  203.                         arr[4] = arr[3];  
  204.                         arr[3] = arr[1];  
  205.                         arr[1] = arr[0];  
  206.                         arr[0] = temp;  
  207.                         return 0;  
  208.                     }                 
  209.                 }  
  210.                 else  
  211.                 {  
  212.                     if( arr[0] <= arr[1] )/*⑦正确顺序为[4][2][0][1][3]*/  
  213.                     {  
  214.                         int temp = arr[4];  
  215.                         arr[4] = arr[3];  
  216.                         arr[3] = arr[1];  
  217.                         arr[1] = arr[2];  
  218.                         arr[2] = arr[0];  
  219.                         arr[0] = temp;  
  220.                         return 0;  
  221.                     }  
  222.                     else/*⑧正确顺序为[4][2][1][0][3]*/  
  223.                     {  
  224.                         int temp = arr[4];  
  225.                         arr[4] = arr[3];  
  226.                         arr[3] = arr[0];  
  227.                         arr[0] = temp;  
  228.                         swap(arr[1],arr[2]);  
  229.                         return 0;  
  230.                     }                 
  231.                 }  
  232.             }         
  233.         }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lzhitian/p/2380947.html