c# 桶排序 基数排序

桶排序

如果数据操作的基础是只能比较大小,那么有数学家证明了最小复杂度是O(NlgN);

但是,很多数据集合并不一定依赖两两比较,而依赖和基数的比较.

比如10000个学生考试,分数只分0,1,2,3,4,5;那么拿两个学生比较就不如

直接拿1个学生和分数比较了.

这样,准备好6个分数桶,分别把学生扔进对应的桶中,扔完后,再按照桶的顺序挨个拿出来,就好了,这样就实现了线性的复杂度.

定义一个桶:

 public class Bucket
    {
        public int Value { get; set; }
        public Bucket Next { get; set; }

        public Bucket(int i)
        {
            this.Value = i;
        }
    }

1把数据放入桶,2把桶排序(要保证桶的数量比较少,这一步的时间复杂度跟其他排序是一样的,所以要保证桶的数量比较少),3再把数据拿出来;

public static void Bucket_Sort(int[] nums)
        {
            List heads = new List();
            Dictionary<int, Bucket> buckets = new Dictionary<int, Bucket>();
            //把数据都放入桶中
            foreach (var i in nums)
            {
                if (buckets.ContainsKey(i))
                {
                    var temp= new Bucket(i);
                    buckets[i].Next = temp;
                    buckets[i] =temp;
                }
                else
                {
                    var head = new Bucket(i);
                    buckets.Add(i,head);
                    heads.Add(head);
                }
            }
            //对heads进行排序
            m_SortHeaders(heads);
            //从桶中取得元素
            int index = 0;
            foreach (var head in heads)
            {
                var temp = head;
                while (temp != null)
                {
                    nums[index++] = temp.Value;
                    temp = temp.Next;
                }
            }
        }

对桶排序的子函数:

        private static void m_SortHeaders(List heads)
        {
            int lengh = heads.Count();
            //比如用冒泡法
            for (int p = lengh - 1; p > 0; p--)
            {
                bool flag = true;
                for (int i = 0; i < p; i++)
                {
                    //比较相邻元素,交换;
                    if (heads[i].Value > heads[i + 1].Value)
                    {
                        var temp = heads[i];
                        heads[i] = heads[i + 1];
                        heads[i + 1] = temp;
                        flag = false;
                    }
                }
                if (flag) break;
            }
           
        }

基数排序

这是一种桶排序的拓展

考虑2个场景

1.英文单词,仅有26个字母组成,但是有很多位数,怎样利用桶排序?

2.十进制阿拉伯数字,仅有10个数字组成,但也有很多不等的位数组成,怎样对其排序?

上述场景中有多个关键字,而且每个关键字的权重是不一样的,比如10>01,字典中ab排在ba前面.

针对这样的场景,就有了基数排序,具体思路是先按照权重最低的属性进行一轮桶排序,再按照次低的桶排序...直到权重最高的

下面展示了对十进制数字的基数排序

子函数,找某整数的x位数是多少

    public static class IntExtension
    {
        public static int baseNumber(this int a, int weishu)
        {
            int chushu =(int) Math.Pow(10, weishu - 1);
            int shang = a / chushu;
            int result = shang % 10;
            return result;
        }
    }

过程函数,根据第x位进行桶排序,其中的bool返回值表示,下一轮排序是否有意义,比如数列中全是6以内位数,按第7位排序就没有意义.

        private static bool PutInBucket(int[] nums,int weishu)
        {
            bool result = false;
            Listint>> TenBuckets = new Listint>>();
            for (int i = 0; i < 10; i++)
            {
                TenBuckets.Add(new List<int>());
                
            }

            //如果循环做完result还是false,说明weishu再增加已经没有意义了.
            foreach (var number in nums)
            {
                var tongshu = number.baseNumber(weishu);
                TenBuckets[tongshu].Add(number);
                if (number / Math.Pow(10, weishu - 1) > 0&&result==false) result = true;
            }

            if (result == false) return result;

            int index = 0;
            foreach (var list in TenBuckets)
            {
                if (list.Count != 0)
                {
                    for (int i = 0; i < list.Count; i++)
                    {
                        nums[index++] = list[i];
                    }
                }
            }

            return result;
        }

整体排序是按照由个位开始,循环进行桶排序,直至最高位也进行了桶排序.

        public static void Radix_Sort(int[] nums)
        {
            int startBase = 1;
            while (PutInBucket(nums,startBase))
            {
                startBase++;
            }
        }