浮点数基数排序

日期: 05 月 25日, 2014
标签:

IEEE 754浮点数的机器表示如下:

符号 指数 尾数

比较大小时先比较符号位，再比较指数，最后比较尾数。

反码整数的机器表示如下:

符号 尾数

比较大小时先比较符号位，再比较尾数。

可以看出，要比较两个浮点数的大小，等价于比较相同机器表示的反码整数的大小。因此，可以把浮点数当成反码整数来进行计数排序或基数排序。需要注意的是，计算机的整数是用补码表示的，还需要一些额外的处理。

代码如下:

#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "fsort.h"

typedef unsigned long long uint64;
typedef long long int64;
typedef unsigned short uint16;

static void sort_word(double *array, size_t n, int word, double *buf)
{
	int cnt[65536];
	memset(cnt, 0, sizeof(cnt));

	for (size_t i = 0; i < n; i++)
	{
		uint16 tmp = ((uint16 *)(array+i))[word];
		cnt[tmp]++;
	}

	for (size_t i = 1; i < 65536; i++)
	{
		cnt[i] += cnt[i-1];
	}

	memcpy(buf, array, sizeof(double)*n);

	for (int i = (int)n-1; i >= 0; i--)
	{
		uint16 tmp = ((uint16 *)(buf+i))[word];
		array[cnt[tmp]-1] = buf[i];
		cnt[tmp]--;
	}
}

void fsort(double *array, size_t n)
{
	double *buf = (double *)malloc(sizeof(double)*n);

	sort_word(array, n, 0, buf);
	sort_word(array, n, 1, buf);
	sort_word(array, n, 2, buf);
	sort_word(array, n, 3, buf);

	memcpy(buf, array, sizeof(double)*n);

	for (int i = (int)n-1; i >= 0; i--)
	{
		if (((int64 *)buf)[i] < 0)
		{
			array[n-i-1] = buf[i];
		}
		else
		{
			memcpy(array+n-i-1, buf, sizeof(double)*(i+1));
			break;
		}
	}

	free(buf);
}