|
|
有趣的位图排序算法
这几天在看《编程珠玑》，其中看到了一个非常有趣的排序算法，个人认为这个算法比较另类，在这里拿出来和大家分享。此算法代码量十分的少，排序效率又很高，但它是也有一些特定条件在里面。
先说说思路和特定条件，实际的问题是，有一个文件里面包含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开发技术 』 → 『 数据结构和算法专题 』 → 有趣的位图排序算法
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密