按位LSD排序（基数排序）

最近，我发表了许多有关各种排序算法及其比较的文章，我决定自己赚5美分。

我想告诉您我最喜欢的算法，用于对LSD（最低有效位-最低有效位）进行按位排序（基数排序）。 作者对经典算法进行了一些重新思考，以实现一些优化，以实现加速和简化。

因此，建议的排序是可持续的。 我们将对32位整数进行排序。 要工作，您需要〜（n + 4KB）的额外内存，这虽然有些浪费，但可以使性能有所提高。

在这种LSD中，不使用比较和交换，该算法是完全线性的。 计算复杂度O（N）。

该算法的主要特点是对高度混合或随机数据集的高效率。 在几乎排序的集合上，使用其他算法是有意义的，因为增益不会那么显着。 它在少于两百个元素的小型阵列上效果不佳。

排序在本地进行以节省内存。

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

该代码是用Pascal编写的，但是将其移植到任何您方便的语言并不难。

执行顺序包括两个阶段：

1. 对于每个块（八个二进制数字-1个字节（最佳值）），通过计数，可以计算出其在新数组中的位置。
2. 对于每个块，顺序地（从最低有效到最高）移动到先前计算的位置。

改进之处：

1. 对于偏移量数组，我们使用内存中的对齐方式，并且由于体积较小，因此将其放置在L1（处理器缓存）中。
2. 偏移量数组会立即填充所有数字，这使您可以遍历数组仅计数一次。
3. 位置计算不是从数组的开头开始，而是从结尾开始，解决了两个问题：
   
   • 第一次通过时，数组的末尾已经在“预热”缓存中，对于较大的数组，缓存会稍有加速；
   • 其次，相对于上升周期，在该周期的每一步，由一个汇编指令将下降至零的周期缩短。
4. 对于每次迭代（四次迭代），虽然不那么精美，但不使用嵌套循环，但是会保存多条处理器指令。

由于其简单性，代码的速度几乎与32位和64位编译器版本相同。 如有必要，可以很容易地想象出16位和64位数字的算法版本。

在64位平台上比较随机采样算法与快速排序（平均每十遍）。



欢迎提供有关优化的建议和意见。

谢谢啦