>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 19567 个阅读者 刷新本主题
 * 贴子主题:  有趣的位图排序算法 回复文章 点赞(0)  收藏  
作者:mary    发表时间:2020-03-15 18:56:09     消息  查看  搜索  好友  邮件  复制  引用

     有趣的位图排序算法

               这几天在看《编程珠玑》,其中看到了一个非常有趣的排序算法,个人认为这个算法比较另类,在这里拿出来和大家分享。此算法代码量十分的少,排序效率又很高,但它是也有一些特定条件在里面。

               先说说思路和特定条件,实际的问题是,有一个文件里面包含7位电话号码,对电话号码进行排序,电话号码之间不重复。我将其归纳为:对一个最多可以是1千万个数字的集合的数组进行排序,数组中最大的数字是1千万,数字之间不能重复。

                  算法的思路是(我这里以c#代码为例),创建一个byte[n]的比特数据,n=1千万。

1、关闭所有的位,将集合初始化为空
2、读取集合中的每一个整数,打开相应的位
3、检查每个位,如果打开就输出整数

源代码为:
public static int[] Sort(int[] arr)
{
   int n = 10000000;
   byte[] bytes = new byte[n];
   for (int i = 0; i < arr.Length; i++)
   {
     bytes[url=] = 1;
    }

     List<int> result = new List<int>();
     for (int i = 0; i < bytes.Length; i++)
     {
        if (bytes[i] == 1)
          { result.Add(i); }
      }
     return result.ToArray();
  }

做一个简单的单元测试

//测试方法
public void BitmapSortTest()
{
   int[] i = new int[] { 10, 50, 90, 11, 51, 91, 2, 3, 4, 80, 5 };
   i = BitmapSort.Sort(i);
   Assert.IsTrue(i[0] == 2);
   Assert.IsTrue(i[1] == 3);
   Assert.IsTrue(i[2] == 4);
   Assert.IsTrue(i[3] == 5);
   Assert.IsTrue(i[4] == 10);
   Assert.IsTrue(i[5] == 11);
   Assert.IsTrue(i[6] == 50);
   Assert.IsTrue(i[7] == 51);
   Assert.IsTrue(i[8] == 80);
   Assert.IsTrue(i[9] == 90);
   Assert.IsTrue(i[10] == 91);
}

     这个算法的思路很帅气,而且我们只在内存中开了一个byte[10000000]的比特数组,也就是说内存的消耗很小。当然我们还可以改进,如果中间数字有重复的怎么办呢?其实也很简单,用字符串数组代替比特数组,将设置为1的操作变成自增1,在进行输出的时候数字是几,这个数组输出几次,不就完美的解决问题了吗。

     看是不是很有趣。



----------------------------
原文链接:https://blog.51cto.com/realzjy/1317523
作者:-张隽永


程序猿的技术大观园:www.javathinker.net



[这个贴子最后由 flybird 在 2020-03-16 11:54:34 重新编辑]
  Java面向对象编程-->Java语言中的修饰符
  JavaWeb开发-->访问数据库(Ⅰ)
  JSP与Hibernate开发-->映射一对多关联关系
  Java网络编程-->用Swing组件展示HTML文档
  精通Spring-->创建综合购物网站应用
  Vue3开发-->虚拟DOM和render()函数
  有关图片的LZW算法的原理
  深度学习之图片压缩算法
  算法的概念、特征和基本类型简介
  进程调度算法总结
  分布式一致Hash算法-存储之道
  对称算法非对称算法哈希算法区别
  Citrix Netscaler负载均衡算法
  活动安排问题(贪心算法)
  天干地支算法
  全排列的六种算法
  用Java实现回文数算法
  Binary Search二分查找算法
  字节跳动面试官这样问消息队列:分布式事务、重复消费、顺序...
  RSA 非对称加密原理(小白也能看懂哦~)
  RSA算法的数学原理
  更多...
 IPIP: 已设置保密
树形列表:   
1页 0条记录 当前第1
发表一个新主题 开启一个新投票 回复文章


中文版权所有: JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶,分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权,请与本站管理员联系。