{ Snake @ NET } 废寝忘食的程序工作者.

没有了Linq和扩展方法,一切都靠自己–手写Sort和Search方法.

Hello,我是Snake,欢迎阅读我的文章--没有了Linq和扩展方法,一切都靠自己–手写Sort和Search方法.

众所周知在ASP.NET3.5中对于实现了IEnumerable<T>接口的类相比于ASP.NET2.0多出了好多方法出来,他们大部分都是基于Linq.在Linq的帮助下我们可以用1行代码就完成Sort和Search方法.

当然在ASP.NET 2.0 中 Array类中有一个静态Sort方法,还是List中也有一个Sort方法.但是他们分别都是独立并且接收的参数过于"小众",面对Linq关于IEnumerable接口实现的那些强大的Sort方法来说真是小巫见大巫啊.不但少了Func<T,TResult>委托,还少了Lambda表达式..昨晚搞一个实体类集合的排序就被郁闷到了.今早起床立即写了两个会用到的方法,当然相对于Linq来说还是比较小众,这是水平问题和语言本身的限制性.

他们分别是泛型类,并且都是静态方法,接收一个实现了ICompareable<T>接口的类型T.另外所用到的Sort方法来自最简单的QuickSort,而Search方法来自于限制比较大的BinarySearch(需要已经排序好的数组)和最最普通的遍历查找.最后他们都接收一个实现与IList<T>接口的类型作为排序或查找对象(已知Array和List都实现了这2个接口).

下面放上代码:

public class Sort<T> where T : IComparable<T>
{
    public static IList<T> QuickSort(IList<T> list, bool desc)
    {
        int lo = 0;
        int hi = list.Count - 1;
        int tag;
        if (lo < hi)
        {
            tag = QuickSortPartion(list, lo, hi, desc);
            QuickSort(list, lo, tag - 1, desc);
            QuickSort(list, tag + 1, hi, desc);
        }

        return list;
    }
    public static IList<T> QuickSort(IList<T> list, int lo, int hi, bool desc)
    {
        int tag;
        if (lo < hi)
        {
            tag = QuickSortPartion(list, lo, hi, desc);
            QuickSort(list, lo, tag - 1, desc);
            QuickSort(list, tag + 1, hi, desc);
        }

        return list;
    }
    private static int QuickSortPartion(IList<T> list, int lo, int hi, bool desc)
    {
        T pos = list[lo];
        T temp;

        if (!desc)
        {
            while (lo < hi)
            {
                while (lo < hi && pos.CompareTo(list[hi]) <= 0) hi--;
                temp = list[lo];
                list[lo] = list[hi];
                list[hi] = temp;
                while (lo < hi && pos.CompareTo(list[lo]) >= 0) lo++;
                temp = list[hi];
                list[hi] = list[lo];
                list[lo] = temp;
            }
        }
        else
        {
            while (lo < hi)
            {
                while (lo < hi && pos.CompareTo(list[hi]) >= 0) hi--;
                temp = list[lo];
                list[lo] = list[hi];
                list[hi] = temp;
                while (lo < hi && pos.CompareTo(list[lo]) <= 0) lo++;
                temp = list[hi];
                list[hi] = list[lo];
                list[lo] = temp;
            }
        }

        return lo;
    }
}

public class Search<T> where T : IComparable<T>
{
    public static int NormalSearch(IList<T> list, T item)
    {
        for (int i = 0; i < list.Count;i++ )
        {
            if (list[i].CompareTo(item) == 0)
            {
                return i;
            }
        }
        return -1;
    }

    public static int BinarySearch(IList<T> list, T item)
    {
        bool desc = isDescList(list);
        int lo = 0;
        int hi = list.Count - 1;
        int idx;
        while (lo <= hi)
        {
            idx = lo + (hi - lo) / 2;
            if (item.CompareTo(list[idx]) < 0)
            {
                if (!desc) hi = idx - 1;
                else lo = idx + 1;
            }
            else if (item.CompareTo(list[idx]) > 0)
            {
                if (!desc) lo = idx + 1;
                else hi = idx - 1;
            }
            else
                return idx;
        }

        return -1;
    }

    private static bool isDescList(IList<T> list)
    {
        int _base = 0;
        while (_base + 1 < list.Count && list[_base].CompareTo(list[_base + 1]) != 0)
        {
            if (list[_base].CompareTo(list[_base + 1]) > 0) return true;
            else return false;
        }

        return false;
    }
}

由于目前紧张的开发进度,所以写代码是目光比较短浅.
另外我看到了Array.Sort中有一个实现IComparer接口的参数,目前不清楚他是干嘛的,不过现在我马上要求会会他.或许可以让上面的代码更加美观,接受面更加广泛.

希望能帮到你

站内任何内容未经作者声明,皆为作者原创,并采用知识共享署名2.5中国大陆许可协议进行许可.

欢迎转载,但转载者必须提供以下文字和连接:

本内容转载自{ Snake @ NET },原文地址:没有了Linq和扩展方法,一切都靠自己–手写Sort和Search方法.(http://bugunow.com/blog/write-the-sort-n-search-method-by-myself/)