完善算法 -将一个具有n个元素的数组向左循环移动i个位置

完美算法 --将一个具有n个元素的数组向左循环移动i个位置

实验问题：

将一个具有n个元素的数组向左循环移动i个位置。

有许多应用程序会调用这个问题的算法，例如在文本编辑器中移动行的操作，磁盘整理时交换两个不同大小的相邻内存块等。所以，这个问题的算法要求有较高的时间和空间性能。

基本要求：

⑴在原数组中实现循环右移，不另外申请空间；

⑵时间性能尽可能好；

⑶分析算法的时间复杂度。

要在不另申请空间的情况下，保证算法的时间性能尽可能好，如果先设计一个函数将数组向左移动一位，然后再调用该算法i次，是一些人通常想到的方法，但显然这个算法的时间性能不是最好的。要在有限的资源中解决这个问题，似乎比较困难，是否存在这种既不另申请存储空间，又能够达到最好时间性能的完美算法呢。

求解步骤：

1）可以通过下面的方法解决这个问题：先将数组中的前i个元素存放在一个临时数组中，再将余下的n-i个元素左移i个位置，最后将前i个元素从临时数组复制回原数组中后面的位置。但是这个算法使用了i个额外的存储单元，使得空间性能降低。

2）如上所述，先设计一个函数将数组向左循环移动一个位置，然后再调用该算法i次，显然，这个算法的时间性能不好。

3）现在我们换一个角度看这个问题：将这个问题看作是把数组ab转换成数组ba（a代表数组的前i个元素，b代表数组中余下的n-i个元素），先将a逆置得到arb，再将b逆置得到arbr，最后将整个arbr逆置得到(arbr)r=ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3个位置的过程如下：
Reverse(0, i-1); //得到cbadefgh
　　 Reverse(i, n-1); //得到cbahgfed
　　 Reverse(0, n-1); //得到defghabcclass Program

class Program  
    {  
        static void Main(string[] args)  
        {  
            ArrReverse arr = new ArrReverse();  
            string[] str = "a,b,c,d,1,2,3,4".Split(",".ToCharArray());  
            arr.Reverse(ref str, 0, 3);  
            arr.Reverse(ref str, 4, 7);  
            arr.Reverse(ref str, 0, 7);  
            foreach (string s in str)  
            {  
                Console.WriteLine(s);  
            }  
        }         
    }  
    // <summary>  
    // 数组为abcd1234，循环右移4位的话，我们希望到达的状态是1234abcd  
    // </summary>  
    public class ArrReverse  
    {          
        // <summary>  
        // 翻转数组(数组为abcd1234,Reverse(...,0,3)=>dcba1234)  
        // </summary>  
        // <param name="start">开始点</param>  
        // <param name="length">结束点</param>  
        // <returns></returns>  
        public string[] Reverse(ref string[] str,int start,int end)  
        {  
            for (; start < end; start++, end--)  
            {  
                string temp = str[end];  
                str[end] = str[start];  
                str[start] = temp;  
            }  
            return str;  
        }  
          
    }

其原理可以用一个简单的游戏来理解：将两手的掌心对着自己，左手在右手上面，可以实现将一个具有10 个元素的数组向左循环移动5位，如图所示。

该算法在时间和空间上都很有效，并且是这么简短和简单，想出错都很难。 Brian Kernighan在Software Tools in Pascal中使用了这个算法在文本编辑器中移动各行。

作为一个规律，一个好的算法是反复努力和重新修正的结果，即使足够幸运地得到了一个貌似完美的算法思想，我们也应该尝试着改进它。

最后推荐几个关于此问题的博客链接：http://blog.thpiano.com/?p=251

http://blog.****.net/v_JULY_v/article/details/6322882

完善算法 -将一个具有n个元素的数组向左循环移动i个位置

相关推荐