学步园

   今天复习《Data Structures and Algorithms using C#》的时候，想把书中的第三章的基础排序改为泛型版本。起初想得很简单，将int改为T即可，呵呵，结果发现T是不能直接比较的。然后，用了一下午和一晚上的时间才勉强实现。期间尝试了很多种不同的实现方法，最先想到的是用IComparer接口，通过传递接口来实现。但是有个很大的问题，静态类是不支持继承接口的，而我又不想改变开始的想法。所以想了很久，才使用委托方法做了一次尝试。

具体代码如下：

namespace ExercisesThree
{
    public static class BasicSort
    {
        public delegate bool GreaterThanHandler<T>(T first,T second);

        public static void BubbleSort<T>(ref T[] arr,GreaterThanHandler<T> greaterThan)
        {
            int upper = arr.Length;
            int outer = 0, inner = 0, index = 0;
            bool exchange = true;
            while (exchange && outer < upper)
            {
                exchange = false;
                inner = index;
                while (inner < upper-outer-1)
                {
                    if (greaterThan(arr[inner],arr[inner + 1]))
                    {
                        Swap<T>(ref arr[inner],ref arr[inner + 1]);
                        exchange = true;
                    }
                    inner++;
                    if (!exchange && greaterThan(arr[inner + 1],arr[inner]))
                        index++;
                }
                outer++;
            }
        }

        public static void BubbleSort2<T>(ref T[] arr, GreaterThanHandler<T> greaterThan)
        {
            int upper = arr.Length-1;
            for (int outer = upper; outer >=1 ; outer--)
            {
                for (int inner = 0; inner <= outer-1; inner++)
                {
                    if(greaterThan(arr[inner],arr[inner+1]))
                        Swap<T>(ref arr[inner],ref arr[inner+1]);
                }
            }
        }

        public static void SelectionSort<T>(ref T[] arr, GreaterThanHandler<T> greaterThan)
        {
            int upper = arr.Length;
            int min;
            for (int outer = 0; outer < upper; outer++)
            {
                min = outer;
                for (int inner = outer; inner < upper; inner++)
                {
                    if (greaterThan(arr[min], arr[inner]))
                    {
                        min = inner;
                    }
                }
                if (min != outer)
                    Swap<T>(ref arr[outer], ref arr[min]);
            }
        }

        public static void InsertionSort<T>(ref T[] arr,GreaterThanHandler<T> greaterThan)
        {
            int inner,upper = arr.Length;
            T tmp;
            for (int outer = 1; outer < upper; outer++)
            {
                tmp = arr[outer];
                inner = outer;
                while (inner > 0 &&  greaterThan(arr[inner - 1],tmp))
                {
                    arr[inner] = arr[inner - 1];
                    inner--;
                }
                arr[inner] = tmp;
            }
        }

        private static void Swap<T>(ref T val1, ref T val2)
        {
            T tmp = val1;
            val1 = val2;
            val2 = tmp;
        }

        //public static bool Compare<T>(ref T val1,ref T val2)
        //{
        //    return true;
        //}
    }
}

测试代码：

namespace ExercisesThree
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 10;
            int[] arr = new int[n];
            arr = GetArray(n);
            DisplayArray(arr);
           // BasicSort.BubbleSort<int>(ref arr, GreaterThan);
           // BasicSort.SelectionSort<int>(ref arr, GreaterThan);
            BasicSort.InsertionSort2<int>(ref arr, GreaterThan);
            Console.WriteLine();
            DisplayArray(arr);
            Console.Read();
            //BasicSort.BubbleSort();
        }

        static int[] GetArray(int n)
        {
            int[] arr = new int[n];
            Random rnd = new Random();
            for (int i = 0; i < 10; i++)
            {
                arr[i] = rnd.Next(0, 100);
            }
            return arr;
        }

        static void DisplayArray(int[] arr)
        {
                int upper=arr.Length;
                for (int i = 0; i < upper; i++)
                {
                    Console.Write(arr[i] + " ");
                }
        }

        private static bool GreaterThan(int i1, int i2)
        {
            return (i1 > i2);
        }
    }
}

   没什么好总结的，哎。C#有很多东西我还不会。有的东西仅仅是有个印象而已，路还很长，要一直下去才行。