我想实现的整数基数排序，包括负整数。 对于非负整数，我正打算建立的10个队列队列相应的数字0-9和实现LSD算法。 但我是那种困惑着负整数。 我现在在想，是继续创建10个队列，为他们的另一个队列，并分别对它们进行排序，然后在结束时，我会得到2名列表，整理一个包含负整数，另一个包含非负整数。 最后我想将它们合并。
你怎么看待这件事？ 是否有处理与负整数更有效的方式？
谢谢！
Answer 1:
你可以把符号作为一种特殊的数字的。 你排序的单位桩，然后是几十等，终于标志。 这确实能产生相反的顺序为底片，你则只需扭转这种桶的内容。 这是旧的机械卡分拣机是如何工作的。
Answer 2:
需要注意的是符号位是一个有符号整数最高位，但全部数字的基数排序为无符号整数默认处理。 所以，你需要告诉算法负数比正面的小。 在32位带符号的整数的情况下，可以三个下部字节第一排序，然后用翻转，使得0将用于负数代替1-符号位的第四（上部）字节排序，并且因此它们将首先去。
我强烈建议，以数字逐字节而不是十进制数字排序，因为它更容易为整机拿起比提取物位字节。
Answer 3:
一个更解决方案是负整数从阵列分开，使它们正使用基数排序为正值，扭转它并用分选的非负阵列追加。
Answer 4:
绝对！ 当然，你要照顾从阳性分手了负面的但幸运的是这很容易。 在您的排序算法的开始所有你需要做的就是你的分区阵列周围值0之后，排序如下基数，分区之上。
这是在实践中的算法。 我得出这个从凯文·韦恩和鲍勃·塞奇威克的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;
}
Answer 5:
大概处理符号值的最简单的方法是，以抵消积累的起始位置上最显著位操作时（即，生成位置偏移）。 变换所述输入端，以便所有数字可以被视为无符号也是一种选择，但是需要的值阵列上施加的操作至少两次（一次准备输入和再次恢复输出）。
这将使用第一技术以及字节大小的数字（字节访问通常是更有效的）：
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);
}
}
注：代码是未经测试。 道歉对任何错误/错别字。
Answer 6:
如果你不使用“位位移”和“按位与”为基数计算的基数排序不会比著名的比较排序更快。
计算机使用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位，大小范围从千万到11111111，即从128到255。
这些值可通过此代码片而获得
V = ( A[i] >> 24 ) & 255
对于负数V将总是位于从128高达255对于正数将是从0到127正如前面所说，M的值将是255 -1和128为在32位方案最高负数。 建立你的直方图如常。 然后从索引128至255执行累积和，再加入255频率为0，从0进行的累积和，直到索引127执行排序如常。 这种技术既优化，速度快，优雅，整洁无论在理论上还是在实践中。 排序也将全部投入到积极的哪个后不需要任何单独的列表，也为了逆转的做那种缓慢和混乱。
对于代码中看到的基数排序优化
64位版本可以使用相同的概念来构建
进一步阅读：
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html
Answer 7:
这可以无需分区或有切实反转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;
}
}
Answer 8:
接受的答案，需要一个比需要更多的传球。
只需翻转符号位。
这实质上是张贴punpcklbw答案，但有一个需要解决的一个微小的警告。 具体而言，这是假定你是一个二进制补码表示，这对于我们的99.999％，是真正的工作。 例如，Java和锈指定符号整数使用二进制补码。 C和C ++的规格不要求任何特定的格式，但既不是MSVC，GCC，也不LLVM支持其他表示。 在装配中，几乎你会处理任何CPU是二进制补码，你一定会已经知道，否则。
下面的表格表明，简单地翻转符号位将使字典顺序进行排序，当补码整数正确排序。 第一列给出一个二进制值，第二列给出的那些比特作为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给出的答案只有建议翻转位当你在看字节的最高位，但我的直觉告诉我，这将是更快每次只需翻转榜首位，你找出你看字节前。 这是因为每次做一个异或翻转位将超过每来决定是否应该翻转或没有时间做一个分支更快。
[一个重要的细节说，其中一些教科书未能妥善解决，是一个真正的实现应该按字节进行排序，而不是十进制数字。 这显然仍是正确的，因为你只是256，而不是10基数排序，但考虑这种方式会带来更好的实现。]
文章来源: Radix Sort for Negative Integers
