给定一个数组a[5]={1,2,3,4,5};
如何用最少的次数使这个排列倒序。
移动方法：一次只能移动相邻的几个数，可以把相邻的数插入到数列中任何位置。
计数方法:每插入一次计为一次。
看谁能用最快的方法求出结果，并打印过程。

比如我可以把1234同时移到5后面。
再比如，我可以把123移到4和5之间。

移动个数1-4个，5个也没意义。

绝对小于4次。

我也不知道用什么算法，但我知道结果。

用了四步，不对哦，用四步的话我完全可以把1后面的数往前插。
结果小于四步，不然也不会拿出来考大家。曾经高中时，有人拿扑克牌来考我，结果我一下午都没搞出来。
我想计算机可能能实现，就是算法不太好想。
我想了一个算法，不知可不可行。12345逆序数为0，54321逆序数为10，我们直接在3次以下凑这个逆序数的加减就可以了。

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

你拿扑克牌12345，三次就能排序。
我只是想用计算机算出这个过程。

九版，这些排序是你弄出来的吗？怎么让电脑弄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朵   附言：做得好~

关键是有时候调换的数据不止2个，有的时候又只有一个，不过调换函数还是要改进一下。
说一下，大体n个元素的排序大体分三步（优化以上算法）：
第一步,把n/2个元素移到前面第二个
第二步，把从数列最大值开始减k的连续两个数移到最前面加k+1的地方。如：15678234把82移到1号位置变成82156734再移动次大的，把73移动8和2之间，……这样一共移动(n-1)/2次。
第三步，如果该数列为偶数还需移动一次，就是把最后一个数移到它该去的地方，如87643215把5移动6和4之间。如果是奇数列此步就不用进行。
实现，大家看能不能优化一下，要能像吹版那样最好。

[此贴子已经被作者于2017-3-30 21:22编辑过]