我查看了我能找到的排序算法，但我没有看到任何一种算法使用数字位。我想，我创造了一种新型的排序算法。我命名为 Bitsort。说明在 github 中。
你知道这样的排序算法吗？
复杂度是O(nk)。 k 是数组元素的位大小。数组顺序并不重要。 每次复杂度都是O(nk)。但它使用了一点点内存。这取决于N。但是当N增加时，内存相对减少。如果 N 为 1，则它是最大内存比率(R = Node/N)(=bitsize)。如果 N 最大，则内存比率降低到 R = 2。因此 R*N 是存储整个位树所需的节点数。如果 N 等于最大值 ->(整数为 2^32)，我们需要 2N 个节点来存储所有数组。每个节点都有 2 个地址指针。
同时 N 不是数组中数字的计数。 N 是唯一 的数字计数。
如果数组中的所有元素都相同，则N等于1。
总结
Memory = P*N*R (P: pointer size, N: unique count, R: NodeCount(C)/N)
I create a formula for R for 32 bit integer.
R = 31 - 3.3*LOG10(N)
我将数字放入从 MSB(最高有效位)到 LSB(最低有效位)的二叉树中。如果之前添加了它们，我将增加值(value)叶的数量。
我只在源数组上从头到尾移动了 1 次，“排序树”就被填满了。
void bitSort(int * array, int arraySize) {
int i, j;
Block* block;
clock_t start, end;
//create a buffer. root node is first node in buffer.
root = initBlockBuffer();
const unsigned long long digit = ((unsigned long long) 1) << (ARRAY_ELEMENT_TYPE_SIZE_1);
//for every array element (n !IMPORTANT)
for (i = 0; i < arraySize; i++) {
// start at root
Block* activeBlock = root;
register int value = array[i];
register int bit;
//for every bit of value (k !IMPORTANT)
for (j = 0; j < ARRAY_ELEMENT_TYPE_SIZE_1; j++){
//from msb to lsb get the bit
bit = (digit & (value << j)) >> (ARRAY_ELEMENT_TYPE_SIZE_1);
// get the related node from bit
block = activeBlock->node[bit];
// if the node is not exists
if (block == 0) {
// get next blank node from the buffer.
block = nextFreeBlock();
//connect new node to previous node
activeBlock->node[bit] = block;
}
// jump to new node.
activeBlock = block;
}
//after all last node is leaf.
//Getting from last bit of value
if(activeBlock->cnt[value & 1] == 0) leafCount++;
//and count of this leaf, increasing 1
activeBlock->cnt[value & 1]++;
}
}
一些结果
如果我们创建一个包含 1000000(一百万)个 4 字节整数的数组，如下所示: - 相同的号码 - 从 1 增加到 1000000 - 随机均匀分布
相同的数字
Leaf Count : 1
Node Count : 31
Node Size : 16 byte
Total Memory : 512 byte
Duration Sort : 178721 us (0.02s)
Duration Read : 4994 us (0.005s)
从 1 增加到 1000000
Leaf Count : 1000000
Node Count : 1000018
Node Size : 16 byte
Total Memory : 16000304 byte (16MB)
Duration Sort : 218556 us (0.2s)
Duration Read : 14321 us (0.01s)
随机均匀分布
Leaf Count : 999768 (uniq numbers, >%0,02 repetition)
Node Count : 11181318
Node Size : 16 byte
Total Memory : 178913456 byte (179MB)
Duration Sort : 1460578 us (1.4s)
Duration Read : 666933 us (0.7s)
你知道有这样的算法吗？
例子
例子: 我们假设我们有 3 位 长度的数字。
array = {7, 3, 2, 5, 0, 7, 3, 2, 7};
L : level
msb : most significant bit
lsb : least significant bit
msb lsb
L1 L2 L3
7 = 111 --> 1 1 1
3 = 011 --> 0 1 1
2 = 010 --> 0 1 0
5 = 101 --> 1 0 1
0 = 000 --> 0 0 0
7 = 111 --> 1 1 1
3 = 011 --> 0 1 1
2 = 010 --> 0 1 0
7 = 111 --> 1 1 1
首先二叉树只有根节点。
0_____________________|_____________________1
/ \
使用从 msb 到 lsb 的自己的位将第一个数字添加到二叉树。 (相加数: 7 =>(111)(3bit space))
0_____________________|_____________________1
L1 -----> \
0_________\_________1
L2 -----------------------------------------> \
0___\___1
L3 ----------------------------------------------------------> \
[1]
然后是其他人。 (添加数字:3、2、5、0)
0_____________________|_____________________1
/ \
0_________/_________1 0_________\_________1
/ \ / \
0___/___1 0___\___1 0___/___1 0___\___1
/ / \ \ \
[1] [1] [1] [1] 1
如果一个数字已经在树中，它的计数增加 1。 (数字:7、3、2、7)
0_____________________|_____________________1
/ \
0_________/_________1 0_________\_________1
/ \ / \
0___/___1 0___\___1 0___/___1 0___\___1
/ / \ / \ / \
[1] [2] [2] [1] [3]
递归读取时，可以得到排序好的数组。
sorted_array = [1x(000), 2x(010), 2x(011), 1x(101), 3x(111)]
sorted_array = [1x0, 2x2, 2x3, 1x5, 3x7]
sorted_array = [0, 2, 2, 3, 3, 5, 7, 7, 7]
最佳答案
你错了。你设计了一个排序的二叉树(这不是你的发明)。实际上，您不需要拥有所有键(就像您在示例中所做的那样)来完成树。因此它的平均运行树为 O(n*log(n)) ，因为每次插入都需要覆盖所有树节点，直到您要放置 key 的位置。另外，如果你得到一个已经有序的集合，树在列表中退化(你总是去正确的分支直到你到达插入的地方)退化为 O(n²) .
此外，如果您要考虑集合中的每个键(就像您在所有示例中所做的那样)，您可以通过实现大小为 2^n 的数组来节省指针空间。 ，并考虑到 A[n] 的左儿子是索引为 2*n 的单元格, 而右子是索引为 2*n+1 的单元格.在这种情况下，您只需存储与键关联的数据，而不是指针。如果您考虑构建多维数组(与您拥有的位一样多的维度)并且每个索引从 0 开始的可能性，您也会采用这种方法。至 1 .在这种情况下，考虑到全尺寸数组，您可以将数据直接线性存储到数组单元格中，将数组视为线性数组。
关于c - 是否有一种排序算法使用二叉树按位排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57221212/