我正在尝试为整数（包括负整数）实现基数排序。对于非负整数，我计划为数字 0-9 创建一个包含 10 个队列的队列，并实现 LSD 算法。但我有点对负整数感到困惑。我现在在想的是，继续为它们创建另一个包含 10 个队列的队列并分别对它们进行排序，然后最后，我将给出 2 个列表，一个包含已排序的负整数，另一个包含非负整数。最后我会合并它们。
你怎么看待这件事？有没有更有效的方法来处理负整数？
问问题
19026 次
10 回答
32
您可以将符号视为一种特殊的数字。您将一堆堆放在单位上，然后是十位，等等，最后在标志上。这确实会为否定产生相反的顺序，然后您只需反转该存储桶的内容即可。这就是老式机械卡片分拣机的工作方式。
于 2013-03-09T03:10:31.973 回答
5
另一种解决方案是将负整数从数组中分离出来，使其为正数，使用基数排序为正值，然后将其反转并附加已排序的非负数组。
于 2013-03-09T19:25:00.533 回答
5
请注意，符号位是有符号整数中的最高位，但默认情况下，所有数字都被基数排序视为无符号整数。所以你需要告诉算法负数小于正数。对于 32 位有符号整数，您可以先对三个低字节进行排序，然后对第四个（高）字节进行排序，并将符号位反转，这样 0 将用于负数而不是 1，因此它们将首先出现。
我强烈建议按字节对数字进行排序，而不是按十进制数字排序，因为机器获取字节比提取数字容易得多。
于 2014-12-25T03:40:54.457 回答
3
接受的答案需要多过一次。
只需翻转符号位。
这假设您正在使用二进制补码表示，这对我们 99% 的人来说都是正确的。
下表演示了简单地翻转符号位将导致二进制补码整数在按字典顺序排序时正确排序。
第一列给出了一个 4 位二进制值，第二列给出了这些位作为有符号整数的解释，第三列给出了高位翻转后的这些位的解释。
Binary | 2s-comp | Flip sign
----------+----------+----------
0000 | 00 | -8
0001 | +1 | -7
0010 | +2 | -6
0011 | +3 | -5
0100 | +4 | -4
0101 | +5 | -3
0110 | +6 | -2
0111 | +7 | -1
1000 | -8 | 00
1001 | -7 | +1
1010 | -6 | +2
1011 | -5 | +3
1100 | -4 | +4
1101 | -3 | +5
1110 | -2 | +6
1111 | -1 | +7
punpcklbw 给出的答案建议仅在查看最高字节时翻转该位，但每次都简单地翻转符号位会更快。那是因为翻转位的单个 xor 将比分支更快地决定是否应该翻转。
[需要提及的一个重要细节，一些教科书未能正确解决，即真正的实现应该使用基数 256 而不是基数 10。这允许您读取字节而不是十进制数字。]
于 2018-09-24T04:15:37.280 回答
2
绝对地！当然，您确实必须注意将负面因素与正面因素分开，但幸运的是这很容易。在排序算法开始时，您所要做的就是围绕值 0 对数组进行分区。之后，在分区的下方和上方进行基数排序。
这是实践中的算法。我从 Kevin Wayne 和 Bob Sedgewick 的 MSD 基数排序中得出这个：http: //algs4.cs.princeton.edu/51radix/MSD.java.html
private static final int CUTOFF = 15;
private static final int BITS_PER_INT = 32;
private static final int BITS_PER_BYTE = 8;
private static final int R = 256;
public void sort(int[] a){
int firstPositiveIndex = partition(0, a, 0, a.length-1);
int[] aux =new int[a.length];
if(firstPositiveIndex>0){
recSort(a, firstPositiveIndex, a.length-1, 0,aux);
recSort(a, 0, firstPositiveIndex-1, 0,aux);
}else{//all positive
recSort(a, 0, a.length-1, 0, aux);
}
}
private void recSort(int[] a, int lo, int hi, int d, int[] aux){
if(d>4)return;
if(hi-lo<CUTOFF){
insertionSort(a,lo, hi);
return;
}
int[] count = new int[R+1];
//compute counts
int bitsToShift = BITS_PER_INT-BITS_PER_BYTE*d-BITS_PER_BYTE;
int mask = 0b1111_1111;
for(int i = lo; i<=hi; i++){
int c = (a[i]>>bitsToShift) & mask;
count[c+1]++;
}
//compute indices
for(int i = 0; i<R; i++){
count[i+1]=count[i]+count[i+1];
}
//distribute
for(int i = lo; i<=hi; i++){
int c = (a[i]>>bitsToShift) & mask;
aux[count[c]+lo] = a[i];
count[c]++;
}
//copy back
for(int i = lo; i<=hi; i++){
a[i]=aux[i];
}
if(count[0]>0)
recSort(a, lo, lo+count[0]-1, d+1, aux);
for(int i = 1; i<R; i++){
if(count[i]>0)
recSort(a, lo+count[i-1], lo+count[i]-1, d+1, aux);
}
}
// insertion sort a[lo..hi], starting at dth character
private void insertionSort(int[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && a[j] < a[j-1]; j--)
swap(a, j, j-1);
}
//returns the index of the partition or to the right of where it should be if the pivot is not in the array
public int partition(int pivot, int[] a, int lo, int hi){
int curLo = lo;
int curHi = hi;
while(curLo<curHi){
while(a[curLo]<pivot){
if((curLo+1)>hi)return hi+1;
curLo++;
}
while(a[curHi]>pivot){
if((curHi-1)<lo)return lo-1;
curHi--;
}
if(curLo<curHi){
swap(a, curLo, curHi);
if(a[curLo]!=pivot)curLo++;
if(a[curHi]!=pivot)curHi--;
}
}
return curLo;
}
private void swap(int[] a, int i1, int i2){
int t = a[i1];
a[i1]=a[i2];
a[i2]=t;
}
于 2014-05-17T04:06:07.980 回答
2
处理有符号值的最简单方法可能是在对最高有效位进行操作时偏移累加的起始位置（即位置偏移的生成）。转换输入以使所有数字都可以被视为无符号也是一种选择，但需要对值数组至少应用两次操作（一次用于准备输入，再次用于恢复输出）。
这使用第一种技术以及字节大小的数字（字节访问通常更有效）：
void lsdradixsort(int* a, size_t n)
{
// isolate integer byte by index.
auto bmask = [](int x, size_t i)
{
return (static_cast<unsigned int>(x) >> i*8) & 0xFF;
};
// allocate temporary buffer.
auto m = std::make_unique<int[]>(n);
int* b = m.get();
// for each byte in integer (assuming 4-byte int).
for ( size_t i, j = 0; j < 4; j++ ) {
// initialize counter to zero;
size_t h[256] = {}, start;
// histogram.
// count each occurrence of indexed-byte value.
for ( i = 0; i < n; i++ )
h[bmask(a[i], j)]++;
// accumulate.
// generate positional offsets. adjust starting point
// if most significant digit.
start = (j != 3) ? 0 : 128;
for ( i = 1+start; i < 256+start; i++ )
h[i % 256] += h[(i-1) % 256];
// distribute.
// stable reordering of elements. backward to avoid shifting
// the counter array.
for ( i = n; i > 0; i-- )
b[--h[bmask(a[i-1], j)]] = a[i-1];
std::swap(a, b);
}
}
于 2016-09-23T17:00:32.690 回答
2
如果您不使用“bitshift”和“bitwise AND”进行基数计算，您的基数排序不会比著名的比较排序快。
计算机使用 2 的补码来表示有符号数，这里符号位位于二进制数字的最左端，在内存表示中
例如
436163157（作为 32 位数）= 0 0011001 11111111 01010010 01010101
-436163157（作为 32 位数）= 1 1100110 00000000 10101101 10101011
1（作为 32 位数）= 0 0000000 00000000 00000000 00000001
-1（作为 32 位数）= 1 1111111 1111111 1111111 11111111
0 表示为 = 0 0000000 00000000 00000000 00000000
最大负值 = 1 0000000 00000000 00000000 00000000
所以你看，一个数越是负数，它就会失去很多1，一个小的负数有很多1，如果你只将符号位设置为0，它就会变成一个非常大的正数。反之亦然，一个小的正数变成一个大的负数。
在基数排序中，对负数进行排序的关键是如何处理最后 8 位，对于负数，至少最后一位必须为 1，在 32 位方案中，它必须从
1 0000000 00000000 00000000 00000000 开始，这是最从零到1最远的负值1111111 11111111 11111111 11111111 即 -1。如果你看最左边的 8 位，幅度范围从 10000000 到 11111111，即从 128 到 255。
这些值可以通过这段代码获得
V = ( A[i] >> 24 ) & 255
对于负数，V 总是从 128 到 255。对于正数，它将从 0 到 127。如前所述，对于 -1，M 的值为 255，对于 32 位方案中的最大负数，M 的值为 128。像往常一样建立你的直方图。然后从索引 128 到 255 进行累积和，然后将 255 的频率添加到 0，然后从 0 到索引 127 进行累积和。像往常一样执行排序。这种技术在理论上和实践中都是最优的、快速的、优雅的和整洁的。排序后不需要任何类型的单独列表，也不需要反转顺序，也不需要将所有输入转换为正数，这会使排序缓慢而混乱。
有关代码，请参阅基数排序优化
64 位版本可以使用相同的概念构建
进一步阅读：
http ://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html
于 2017-07-07T08:16:48.780 回答
1
这可以在不需要分区或实际上反转 MSB 的情况下完成。这是Java中的一个有效解决方案：
public class RadixSortsInterviewQuestions {
private static final int MSB = 64;
static Map.Entry<Integer, Integer> twoSum(long[] a, long sum) {
int n = a.length - 1;
sort(a, MSB, 0, n);
for (int i = 0, j = n; i < j; ) {
long t = a[i] + a[j];
if (t == sum) {
return new SimpleImmutableEntry<>(i, j);
} else if (t < sum) {
i++;
} else {
j--;
}
}
return null;
}
// Binary MSD radix sort: https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations
private static void sort(long[] a, int d, int lo, int hi) {
if (hi < lo || d < 1) return;
int left = lo - 1;
int right = hi + 1;
for (int i = left + 1; i < right; ) {
if (isBitSet(a[i], d)) {
swap(a, i, --right);
} else {
left++;
i++;
}
}
sort(a, d - 1, lo, left);
sort(a, d - 1, right, hi);
}
private static boolean isBitSet(long x, int k) {
boolean set = (x & 1L << (k - 1)) != 0;
// invert signed bit so that all positive integers come after negative ones
return (k == MSB) != set;
}
private static void swap(long[] a, int i, int j) {
long tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
于 2018-06-11T04:23:37.507 回答
1
这里提出的所有解决方案都意味着性能损失：
- 在分组阶段通过 (a[i] XOR 0x8000000000000000) 翻转最高位；
- 将符号位视为基数并使用额外的通道，按其排序；
- 将负数与数组分开；
- 使用特殊的位掩码等。
你不需要它们。使用常规基数排序。在最后一次迭代中，您将数组项分成 0..255 个组。示例项目：1 50 200 -500 -300 -2 -1
唯一需要调整的是我们如何将这些组复制回原始数组。我们应该开始复制签名的 128..255 组（实际上是 -128..-1），然后是 0..127。
结果：-500 -300 -2 -1 1 50 200
在 PHP 7.4 中测试。常规基数排序实现比 QuickSort 快 2-2.5 倍。添加额外的异或运算会使结果减慢到 1.7-1.8 倍。使用上述方法完全没有性能损失。
编码：
function sortRadix (array &$arr) {
static $groups;
isset($groups) or $groups = [];
$numRadix = 8;
$arrSize = count($arr);
$shift = 0;
for ($i = 0; $i < $numRadix; $i++) {
// Cleaning groups
for ($j = 0; $j < 256; $j++) {
$groups[$j] = [];
}
// Splitting items into radix groups
for ($j = 0; $j < $arrSize; $j++) {
$currItem = $arr[$j];
$groups[(($currItem >> $shift) & 0xFF)][] = $currItem;
}
// Copying sorted by radix items back into original array
$arrPos = 0;
// Treat the last radix with sign bit specially
// Output signed groups (128..256 = -128..-1) first
// Other groups afterwards. No performance penalty, as compared to flipping sign bit
// via (($currItem ^ 0x8000000000000000) >> $shift) & 0xFF)
if ($i === 7) {
for ($j = 128; $j < 256; $j++) {
foreach ($groups[$j] as $item) {
$arr[$arrPos++] = $item;
}
}
for ($j = 0; $j < 128; $j++) {
foreach ($groups[$j] as $item) {
$arr[$arrPos++] = $item;
}
}
} else {
foreach ($groups as $group) {
foreach ($group as $item) {
$arr[$arrPos++] = $item;
}
}
}
// Change shift value for next iterations
$shift += 8;
} // .for
} // .function sortRadix
于 2020-09-15T13:16:59.127 回答
1
您还可以对最高有效字节（包含有符号位）以不同方式解释直方图 (count[])。这是C中的解决方案：
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
static void sortbno(const int32_t* tab, // table of entries
int tabsz, // #entries in tab
int bno, // byte number in T
int* inidx, // current sorted index before this byte
int* outidx) // indices after sorting this byte
{
int count[256];
memset(count, 0, sizeof(count));
// count occurrences of each byte value
for (int i = 0; i < tabsz; i++) {
int32_t x = tab[i];
int v = (x >> (8 * bno)) & 0xff;
count[v]++;
}
// change count[i] so it now reflects the actual
// position of this byte value in outidx
if (bno == sizeof(tab[0]) - 1) {
/* account for signed bit for most-significant-byte */
for (int i = 129; i < 256; i++) {
count[i] += count[i - 1];
}
count[0] += count[255];
for (int i = 1; i < 128; i++) {
count[i] += count[i - 1];
}
} else {
for (int i = 1; i < 256; i++) {
count[i] += count[i - 1];
}
}
// fill outidx[]
for (int i = tabsz - 1; i >= 0; i--) {
int in = inidx[i];
int32_t x = tab[in];
int v = (x >> (8 * bno)) & 0xff;
outidx[--count[v]] = in;
}
}
/**
* Sort tab[].
* Return the indices into tab[] in ascending order.
*/
int* rsort(const int32_t* tab, int tabsz)
{
int* r[2];
r[0] = malloc(tabsz * sizeof(*r[0]));
r[1] = malloc(tabsz * sizeof(*r[1]));
if (! (r[0] && r[1]))
goto bail;
// Artificially assign indices to items
for (int i = 0; i < tabsz; i++) {
r[0][i] = i;
}
// Sort byte by byte. byte #0 is x & 0xff.
int bin = 0;
for (int i = 0; i < (int)sizeof(tab[0]); i++) {
sortbno(tab, tabsz, i, r[bin], r[1-bin]);
bin = !bin;
}
free(r[1-bin]);
return r[bin];
bail:
if (r[0]) free(r[0]);
if (r[1]) free(r[1]);
return 0;
}
于 2020-10-05T18:34:41.463 回答