等等~~~

12345678-87654321只用了5步~

16782345-
82167345-
87321645-
87321654-
87654321~

有规律的！~~~

当n=4时~

1 2 3 4

1 4 2 3
4 2 1 3
4 3 2 1

3步~

当n=5时~

1 2 3 4 5

1 4 5 2 3
5 2 1 4 3
5 4 3 2 1

3步~

当n=6时~

1 2 3 4 5 6

1 5 6 2 3 4
6 2 1 5 3 4
6 5 3 2 1 4
6 5 4 3 2 1

4步~

当n=7时~

1 2 3 4 5 6 7

1 5 6 7 2 3 4
7 2 1 5 6 3 4
7 6 3 2 1 5 4
7 6 5 4 3 2 1

4步~

当n=8时~

1 2 3 4 5 6 7 8

1 6 7 8 2 3 4 5
8 2 1 6 7 3 4 5
8 7 3 2 1 6 4 5
8 7 6 4 3 2 1 5
8 7 6 5 4 3 2 1

5步~

当n=9时~

1 2 3 4 5 6 7 8 9

1 6 7 8 9 2 3 4 5
9 2 1 6 7 8 3 4 5
9 8 3 2 1 6 7 4 5
9 8 7 4 3 2 1 6 5
9 8 7 6 5 4 3 2 1

5步~

所以n的步数可以为  


           n-1;(n<5)
S(n)=    {
          n/2+1;(n>=5)
~~~                  

这个移动规律用C实现算法复杂度应该不大~

[此贴子已经被作者于2017-3-25 11:43编辑过]

感觉这个公式应该是最优解~~

证明如下~

设~定义排序效率为改变相邻数据单调性的次数~

1 2 3 4 5
的单调性为
+ + + +
1 4 5 2 3
的单调性为
+ + - +

"-"号多了一个~
就意味着本次排序效率为1
1 4 5 2 3
到
5 2 1 4 3
的单调性为
- - + -

这里"-"号多了两个
就意味着本次排序效率为2

5 2 1 4 3
到
5 4 3 2 1
- - - -

这里"-"号多了一个
就意味着排序本次排序效率为1~


对于n的排序来说最少要改变数据单调性n-1次~
如果按照单个入排序~则至少要排n-1次~
不难得出单个插入排序的效率最多为1~

按照公式分块移动的平均效率趋近于2但不会大于2~
这也就意味着分块移动其实每次排序效率最多等于普通插入的两倍~这点很重要~~

这里可以用反证法~

假设当n>=5时存在某总移动规则比(n)/2+1的移动效率更高~

然而对于n的排序来说最少要改变数据单调性n-1次~

则意味着存在某次移动使得分块移动每次排序效率大于2~

也就是说意味着存在某次移动使其"-"的增量大于2~

然而分块插入不会改变中间数据的单调性~

就是说每次分块把中间的数据看成是一个整体~
这样可以看成有效改变数据单调性的就只有头尾两个数据对其产生影响~
这就意味着等效于连续移动两个数据的单个排序~
所以分块移动的排序效率<=2~

这与存在某次移动使得分块移动每次排序效率大于2这个假设矛盾。
所以假设不成立。

假设存在某种移动规则满足公式n/2时总成立~则意味着每次排序效率都必须等于2~
然而第一次移动数据时是不存在某种移动规则使其排序效率等于2的~

所以不存在某种移动规则比n/2+1这个公式的移动规则效率更高~

固公式为移动规则公式的最优解~~~~~~~~~~~~~

[此贴子已经被作者于2017-3-25 04:18编辑过]

收到的鲜花

• 寒风中的细雨 于 2017-03-25 09:02 送鲜花  10朵  
• 寒风中的细雨 于 2017-03-25 09:10 送鲜花  10朵   附言：1 2 3 4 5 6 7 8 1 6 7 8 2 3 4 5 8 2 1
• 书生牛犊 于 2017-04-18 07:20 送鲜花  10朵   附言：我很赞同

如果无规则限制，将一n个数的数列用换位法逆序，至多也交换int(n/2)次。

九版，这些排序是你弄出来的吗？怎么让电脑弄5个的数的排序都不好弄。
这方面电脑真不如人。😄

人工写的~哈哈~ 编程也行啊~有规律的~

找出了规律，程序丑了点，已完工。
下面程序并不是算出来的，而是根据规律演化的。
更正一下九版公式:
           n-1;(n<=2)
 S(n)=    {
           n/2+1;(n>2)
#include <stdio.h>
#include <stdlib.h>
#define N 16
void insert(int a[],int frompos,int len,int topos)
{
    int *p,j,l,k;
    k=frompos;
    if(len==0)return;
    p=(int *)malloc(len*sizeof(int));
    if((N-k-len)<=2)
        for(int i=0;i<len;i++,frompos++)
        {
        p[i]=a[frompos-1];
        if((frompos+len-1)<=N-2)
        a[frompos-1]=a[frompos+len-1];
        else
        a[frompos-1]=0;
        }
    else
    for(int i=0;i<N-k-len;i++,frompos++)
    {
        if(i<len)
        p[i]=a[frompos-1];
        if((frompos+len-1)<=N-2)
        a[frompos-1]=a[frompos+len-1];
        else
        a[frompos-1]=0;
    }
   
    a[frompos-1]=0;
    for(j=0;a[j]!=0;j++);
    l=j-topos+1;
    for(int i=N-2;l>0;i--)
    {
        a[i]=a[i-len];
        l--;
    }
   
    for(int i=topos-1;i-topos<len-1;i++)
    {
        a[i]=*p++;
    }
    free(p);
}

main()
{
    int a[N]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},m,step=0,n,i,l=1,lastlen=0,k;
    n=N-1;
    k=(N-2)/2;
    if((N-1)%2==0)m=(N-2)/2;
    else m=(N-2)/2-1;
    for(int i=0;i<N-1;i++)
    {
        printf("%2d ",a[i]);
    }
    printf("\n");
    insert(a,N-k,k,2);
    for(int i=0;i<N-1;i++)
    {
        printf("%2d ",a[i]);
    }
    printf("\n");
   
    while(m--)
    {
        for(i=0;a[i]!=n;i++);
        insert(a,i+1,2,l);
        n--;
        l++;
        for(int i=0;i<N-1;i++)
        {
        printf("%2d ",a[i]);
        }
        printf("\n");
    }
   
    for(int j=1;j<N-1;j++)
    {
        if((a[j-1]-a[j])>1)l=j;
        if((a[j]-a[j-1])>0)i=j;
    }
    lastlen=N-1-i;
    insert(a,i+1,lastlen,l+1);
    for(int i=0;i<N-1;i++)
    {
        printf("%2d ",a[i]);
    }
}

[此贴子已经被作者于2017-3-25 19:43编辑过]

收到的鲜花

• 九转星河 于 2017-03-25 19:46 送鲜花  10朵   附言：做得好~

不懂...

meikandong

我赞同你的方法，就算用数组来实现，为(O/2)：i = n/2+n%2;
i 为循环次数, n 为元素个数，以头尾对调的方式。