洗牌算法与重新排序

发表于2015-08-12
评论1 2.1k浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594

     这次我来说说洗牌算法以及重新排序问题~(前几天回家了,而且也没遇到什么我觉得值得写的。。。所以木有写新的文章- -)
     这个洗牌算法,其实就是一种打乱顺序的算法。在网上有很多种方法,今天我自己写了写,参考了下别人写的,总结了两种方法。以下全是在C#工程下写的,所以不用打开Unity了- -。。。。

     第一种:利用数组,这种方法应该说是最基本最基本的了。
[code]csharpcode:
    //利用数组 
               int[] int_array = new int [100]; 
     
               //放入数据 
               for (int i = 0; i < int_array.Length; i++ ) 
               { 
                   int_array[i] = i + 1 ; 
               } 
               Random r = new Random (); 
     
               //打乱顺序 
               for (int i = int_array.Length - 1; i > 0; i-- ) 
               { 
                   int index = r.Next( 0, i); 
     
                   int temp = int_array[ i]; 
                   int_array[i] = int_array [index]; 
                   int_array[index ] = temp ; 
               } 
               //输出 
               foreach (int a in int_array) 
               { 
                   Console.WriteLine (a); 
               }  
     第二种:利用List

[code]csharpcode:
    //定义两个List 
             List< int   > origin_list = new List <int   >(); 
             List< int > reshuffle_list = new List <int   >(); 
     
             //添加元素 
             for (int i = 0; i < 100; i++ ) 
             { 
                 origin_list.Add((i + 1 )); 
             } 
     
             Random c = new Random (); 
             int num = origin_list.Count ; 
     
             //有序List中元素打乱后向新list转移 
             for (int i = 0; i < num; i++ ) 
             { 
                 int random_index = c.Next( 0, origin_list.Count ); 
                 reshuffle_list.Add(origin_list [random_index]); 
                 origin_list.RemoveAt(random_index ); 
             } 
     
             //输出 
             for (int i = 0; i < reshuffle_list.Count; i++ ) 
             { 
                 Console.WriteLine (reshuffle_list[ i]); 
             } 

     以上是两种洗牌算法,下面我来说重新排序。

     对于重新排序,我相信大家的第一反应是冒泡了。。那些什么桶排序啊、快速排序啊、各种各样的排序算法啊我就不说了,我想说的重新排序是基于我上述的第二种方法的。

     下面我把我的第二种方法添加一句话(在输出之前添加这句话):
reshuffle_list.Sort ();

     这是list中存在的一个方法,目的就在于重新排序。可是这种排序方法有种限制,就是list中所存放的类型必须是int类型。
     但是在Unity中,我们所涉及的list中的类型绝不可能只有int类型,假如将来我们在做项目时,碰到需要排序的非int类型,那该怎么办呢?

     我们先来看看sort中的参数有哪些。


     先不解释sort中的参数,我现在把我之前第二种方法改写一下,让list中存放的是string类型。
[code]csharpcode:
    //定义两个List 
          List< string > origin_list = new List <string > (); 
          List< string > reshuffle_list = new List <string > (); 
     
          //添加元素 
          for (int i = 0; i < 100; i++ ) 
          { 
              origin_list.Add((i + 1 ).ToString ()); 
          } 
     
          Random c = new Random (); 
          int num = origin_list.Count ; 
     
          //有序List中元素打乱后向新list转移 
          for (int i = 0; i < num; i++ ) 
          { 
              int random_index = c.Next( 0, origin_list.Count ); 
              reshuffle_list.Add(origin_list [random_index]); 
              origin_list.RemoveAt(random_index ); 
          } 
     
          //重新排序 
          reshuffle_list.Sort(( string x , string y ) => 
          { 
              return int .Parse(x ) - int.Parse (y); 
          }); 
     
          //输出 
          for (int i = 0; i < reshuffle_list.Count; i++ ) 
          { 
              Console.WriteLine (reshuffle_list[ i]); 
          } 

     这时候请注意我的排序方式,你可以试着运行一下,看看结果。
     下面我来解释一下,在list中的sort方法,其实用到了委托。委托是什么?我的理解其实就是给方法一个专门的“类型”,这个“类型”其实跟 string、int差不多的。关于委托,网上有太多的资料可以查阅。而C#中,对于委托有一个非常酷的方法就是lambda表达式。利用lambda表 达式避免了定义一个新的方法,直接套用lambda表达式的固定格式,在中括号内写方法体就可以了,非常高效。
     至于我上述的重新排序中的方法体,为什么这样写?下面我来把sort的代码实现写在下面:
[code]csharpcode:
    namespace LambdaWar 
    { 
        public delegate int Comparer (int x , int y); 
        public  class MyList 
        { 
            public   void Sort( Comparer compare) 
            { 
                for (int i = 0; i < data_list.Length - 1; i++ ) 
                { 
                    for (int j = 0; j < data_list .Length - i -1; j++ ) 
                    { 
                        if (compare(data_list [j], data_list [j + 1]) > 0) 
                        { 
                            int temp = data_list[ j]; 
                            data_list[j ] = data_list [j + 1]; 
                            data_list[j + 1 ] = temp ; 
                        } 
                    } 
                } 
            } 
        } 
        class Program 
        { 
            static void Main( string [] args) 
            { 
            } 
        } 
    } 

     其实sort就是利用冒泡排序所进行排序的,不过此时传递的是一个方法。
     仔细看下sort的代码实现,再回到重新排序中的方法体,不难发现,当x - y大于0时,它俩就会进行一次交换,从而实现从小到大的排序方式;假如方法体内换成 y -x ,那自然就是从大到小的排序方式了。
     也许有人会问这在unity中什么时候会用到,其实如果说你在做一个棋牌类的游戏时(尤其是牌类),这个关于sort的ambda表达式就一定会用到!你想想,就好比打升级,你手里的牌是不是随机发到你手上的(洗牌算法),之后在你手里在排序一次(重新排序)?
    
     现在我越发的觉得基础的重要性,就比如这个lambda表达式,用好了能提高效率。现在我也在每天补习下基础的东西,希望跟我一样的那些新手们一定要重视起基础啊。。。。。

原文链接

著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台