排序算法与查找算法在项目中的实际应用

排序和查找是学习数据结构这门课程时的重要知识，不管是哪种编程语言都会用到。

现在主流的查找算法有顺序查找、二分查找、斐波那契查找、插值查找、分块查找、哈希查找、树查找等等，这里不再详细介绍各种查找算法。

现在主流的排序算法有交换排序、插入排序、选择排序、归并排序、计算排序、桶排序、基数排序等等，这里不再详细介绍各种排序算法。

我平时在项目中应该使用哪种排序或查找算法呢？其实啊，每种排序和查找的算法都有不同的使用场景，就拿查找算法来说，有些是针对链表结构的集合(Link)，有些是针对数组结构的集合(Array)，拿数组来说，有些适合有序数组查找，有些适合无序数组查找。

本人作为一名C#程序员，平时用得最多的排序查找算法都是微软提供 lambda 表达式，因为这个语法糖实在是太甜。很少去考虑哪些场景不应该使用 lambda 表达式。这样就会导致程序性能低下，不是说 lambda 提供的算法不行。

我们应该如何在项目中使用这些由前人总结出的排序和查找算法？这些算法大多是用数字元素作为例子，而我的项目使用最多是各种复杂类型，难道这些算法就不能用在复杂类型的集合里？

其实不然，“万物皆数字”，我们可以参考数据库的索引原理，将集合里每个元素通过自定义的 hash 算法转换成数字进行存储，这样就可以使用到各种查找算法。

假设，有这么一个类，

public class MyHashcode
    {         
        public int Value { get; set; }

        public string Name { get; set; } 

        public int Index { get; set; }

        public override int GetHashCode()
        {
            return 10_000_000 + Value;
        }
    }

需求就是从该类型的数组集合中查找 Value 为？？的元素。在 lambda里就是 list.Where(t => t.Value == ??),这是最快实现代码，但并不是运行效率最好的代码。

除非是直接从数据库查询出来的结果，数据一般都是无序，这里使用基数排序加哈希查找作为演示。为属性值 Value 补齐成统一的位数做索引，这样一来既能使用最快的基数排序算法，又能使用哈希查找。

class Program
    {
        const int Total = 50000;
        static List<MyHashcode> list = new List<MyHashcode>(Total);
        static List<int> dict = new List<int>(Total);
        
        static void Main(string[] args)
        {
         

            Test1();
            Console.ReadKey();
        }

        static void Test1()
        {
          
          
            Random r = new Random();
            for (int i = 0; i < Total; i++)
            {
                var code = new MyHashcode() { Name = i.ToString(), Value = r.Next(1,1000001), Index = i };
                dict.Add(code.GetHashCode());
                list.Add(code);
            }

            TestNormalFind();
            TestHashFind();

            Console.WriteLine("");
        }

        static void TestNormalFind()
        {
            var begin = DateTime.Now;
            Random r = new Random();
            int findCount = 0;
            for (int i = 0; i < Total; i++)//Total
            {
                int rnd = dict[r.Next(0, dict.Count)] - 10_000_000;
                var result = list.FirstOrDefault(t => t.Value == rnd);
                if (result != default(MyHashcode))
                    findCount++;
            }
            var end = DateTime.Now;
            Console.WriteLine($"TestNormalFind:{(end - begin).TotalMilliseconds},findCount:{findCount}");
        }

        static void TestHashFind()
        {
            
            var begin = DateTime.Now;
            var array = list.Select(t => t.GetHashCode()).ToArray();
            radix_sort(array);
            Random r = new Random();
            int findCount = 0;
            for (int i = 0; i < Total; i++)//Total
            {
                int rnd = dict[r.Next(0, dict.Count)];
                var index = 0;
                var result = dict.Contains(rnd);
                if (result)
                {
                    index = dict.IndexOf(rnd);
                    var value = array[index];
                    findCount++;
                }
                    
              
            }
            var end = DateTime.Now;
            Console.WriteLine($"TestHashFind:{(end - begin).TotalMilliseconds},findCount:{findCount}");
        }

假设从一个50000个的类型集合里查找某个元素，哈希查找比 lambda要快上3倍多（这里的哈希查找还没有做最大值边界判断，假设要查的值不在集合里，lambda 查询仍然需要遍历全部元素才有结果）。如果集合的数量是十万甚至百万，差距会更加明显。

结束语，这只是个最基础场景，实际情况中往往会更复杂，例如同时查找多个属性值（Value + Name），非等值判断等等。这就需要灵活运用各种数据结构和算法，例如 Redis 里的 skiplist 不也是灵活运用数据结构而来的。