• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C#实现鸽巢排序

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
        /// <summary>
        /// 鸽巢排序
        ///     创建一个长度大于等于待排序数组array元素中最大值的标记数组mark,
        /// 将数组array中元素值个数映射到mark数组中。
        ///     即array数组中的元素值对应mark数组的索引,
        ///       array数组中该元素出现的个数对应mark数组索引的值。
        /// 然后将mark元素中出现的(不等于0)的索引值及个数依次放入array中。
        /// </summary>
        /// <param name="array">待排序数组</param>
        /// <param name="maxValueInArray">数组array中的最大元素值</param>
        public void PigeonholeSort(int[] array, int maxValueInArray)
        {
            int[] mark = new int[maxValueInArray + 1];
            for (int i = 0; i < array.Length; i++)
            {
                ///标记array数组中元素出现的次数
                mark[array[i]]++;
            }
            int arrayIndex = 0;
            ///重新对array的赋值
            for (int i = 0; i < mark.Length; i++)
            {
                ///从array最小元素值 i 开始,i 出现的次数
                for (int j = 0; j < mark[i]; j++)
                {
                    ///依次对数组array的元素更新为最小值 i 及 个数 j
                    array[arrayIndex++] = i;
                }
            }
        }
        /// <summary>
        /// 获取数组array中的最大元素值
        /// </summary>
        /// <param name="array">数组</param>
        /// <returns>最大元素值</returns>
        public int Max(int[] array)
        {
            int max = -1;
            foreach (int item in array)
                if (item > max)
                    max = item;
            return max;
        }

最坏时间复杂度: O(N+n)
最好时间复杂度: O(N+n)
平均时间复杂度: O(N+n)
最坏空间复杂度: O(N*n)


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[c#]协议模拟编程之ADSL模式下IP自动换发布时间:2022-07-13
下一篇:
c#在cmd中用7z解压缩文件发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap