瞎掰一个效率最高的整数排序算法，bitmap排序，时间复杂度O(n)

先上结果，速度上秒掉各种排序：
1e4 Straight Insertion: 0.109916 Sec
1e4 Bitmap sorting    : 0.000214 Sec
1e8 Bitmap sorting    : 6.568575 Sec

前提条件是一般测试数据偏差不大，因此可以用bitmap来标记数据，标记完了自然就排序完成。比堆排序还要快一两个数量级。
缺点也很明显：占内存，只能使用不是特别多的数据排序。
内存评估：一字节8bit, 1M内存是8M bitmap, 1G内存可以排序偏差为8e9的数据，所以一般开发时如果内存够用可以快速出结果。上面1e8个随机数，生成的时候取值在1e9之内，所以内存占用125M.

实现：先扫描出最大最小值，然后分配bitmap内存，再扫描一次做标记，完工。复杂度应该是O(n)

参考：各种排序1万条随机数对比：https://wenku.baidu.com/view/65a02500168884868662d637.html

int *bitmap_sort(int *d, int n, int *r_min, int *r_count) {
	//first scan find min and max
	//create bitmap, size(max-min)
	//2nd scan map existance of each number
	int i;
	int min = d[0];
	int max = d[0];

	for (i = 1; i < n; ++i) {
		if (d[i] < min)
			min = d[i];
		else if (d[i] > max)
			max = d[i];
	}

	int int_bits = sizeof(int) * 8;
	*r_min = min;
	*r_count = (max - min + 1) / int_bits + 1;
	int *bitmap = (int *) calloc(int_bits, *r_count);
	for (i = 0; i < n; ++i) {
		int idx = d[i] - min;
		bitmap[idx / int_bits] |= 1 << (idx % int_bits);
	}
	return bitmap;
}

void bitmap_dump(int min, int count, int* bitmap) {
	int i, j, v;
	int idx = 0;
	for (i = 0; i < count; ++i) {
		v = bitmap[i];
		for (j = 0; j < sizeof(int) * 8; ++j) {
			if (v & (1 << j)) {
				if (idx % 50 == 49)
					printf("\n");
				printf("%d ", min + i * sizeof(int) * 8 + j);
				idx++;
			}
		}
	}
	printf("\n");
}

void bitmap_sort_test(int n, int* d) {
	clock_t start;
	int min, count;
	int* bitmap;

	if (n < 1000)
		bitmap_dump(min, count, bitmap);

	start = clock();

	bitmap = bitmap_sort(d, n, &min, &count);

	printf("Bitmap Sort total time: %f\n",
			(clock() - (double) start) / CLOCKS_PER_SEC);

	if (n < 1000)
		bitmap_dump(min, count, bitmap);
}

int main(int argc, char **argv) {
	clock_t start;
//	int d[] = { 2, 5, 9, 3, 4 };
//	int n = sizeof(d) / sizeof(d[0]);

	int n = 1e8;
	int *d = (int *) malloc(n * sizeof(int));
	if (!d) {
		printf("not enough memory\n");
		return -1;
	}

	make_random_data(d, n);

	if (n <= 1e5) {
		if (n < 1000)
			dump_data(d, n, 0);
		start = clock();
		straight_insertion_sort(d, n);
		printf("Straight Insertion total time: %f\n",
				(clock() - (double) start) / CLOCKS_PER_SEC);
		if (n < 1000)
			dump_data(d, n, 1);
	}

	bitmap_sort_test(n, d);

	return EXIT_SUCCESS;
}

评论

1 楼 steeven 2017-03-28  

后记，网上一搜，这个算法有人贴过。再仔细看看其他算法，这就是统计排序的特例，重复为1才可以用bitmap

另外设想过，俩俩排序，然后上升到四个四个排序，因为排序过的两组合并很快。很不幸发现这是归并排序。。。

然而算法还是很好玩的，比较排序基于cpu的弱项，只能逐个比较。如果不用cpu，搜索最快的就是tcam。排序是不是可以用fpga什么的，让数据自行交换，并行执行。如果矩阵之间数据自行移动，复杂度就是定点到定点, O(sqrt(N))? 终于看到比O(N)小的排序方法 如果三维四维甚至多维。。。硬件工程师要撞墙了。。。