我正在尝试实现整数的基数排序，其中包括负整数。对于非负整数，我计划创建一个由10个队列组成的队列，分别对应数字0-9，并实现LSD算法。但是我对负整数有点困惑。现在我考虑的是，继续为它们创建另一个由10个队列组成的队列，并单独对它们进行排序，最后我会得到两个列表，一个包含已排序的负整数，另一个包含非负整数。最后我会将它们合并。
你对此有何看法？是否有更有效的处理负整数的方法？
11个回答
34
你可以将符号视为一种特殊类型的数字。你按照个位、十位等进行排序，最后再按照符号排序。这会导致负数的顺序相反，因此你只需要反转该桶的内容即可。这是旧的机械卡片分类器的工作原理。
- Peter Wooster
2
这需要比必要的多一次遍历。在排序之前只需翻转符号位即可。 - cbarrick
非常聪明，但这是否需要两次遍历（一次翻转位，然后再翻转回来）？当然，您不需要移动任何数据，这是一个优点。 - hippo-dancer
5
请注意，在有符号整数中，符号位是最高位，但是默认情况下，基数排序将所有数字作为无符号整数处理。因此，您需要告诉算法负数比正数小。对于32位有符号整数，可以先排序三个较低的字节，然后将第四个（上位）字节排序，并且反转符号位，以便0将用于负数而不是1，并因此它们将首先出现。
我强烈建议按字节而不是按十进制位排序数字，因为机器更容易提取字节而不是提取数字。
我强烈建议按字节而不是按十进制位排序数字，因为机器更容易提取字节而不是提取数字。
- punpcklbw
1
2不必反转符号位，您也可以按不同的顺序组合桶。如果您使用16个桶，请从桶8-15开始，然后返回执行0-7，这将产生相同的排序。 - Eagle
5
另一种解决方案是将数组中的负整数分离出来，使它们变为正数，使用基数排序作为正值进行排序，然后反转它并与已排序的非负数数组连接起来。
- gtkesh
4
接受的答案比必要的多一步。
只需翻转符号位即可。
这假定您正在使用二进制补码表示，这对我们中的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。这允许您读取字节而不是十进制数字。
- cbarrick
3
如果您不使用“位移”和“按位与”进行基数计算，那么您的基数排序将不会比著名的比较排序更快。
计算机使用2的补码表示有符号数字，在内存表示中，符号位位于二进制位的最左端
例如
436163157（作为32位数字）= 00011001 11111111 01010010 01010101
-436163157（作为32位数字）= 11100110 00000000 10101101 10101011
1（作为32位数字）= 00000000 00000000 00000000 00000001
-1（作为32位数字）= 11111111 1111111 1111111 11111111
0表示为= 00000000 00000000 00000000 00000000
最高负值为= 10000000 00000000 00000000 00000000
在基数排序中，排序负数的关键是如何处理最后8位，在负数中至少要将最后一位设为1，在32位方案中，它必须从
10000000 00000000 00000000 00000000（即最远离零的最负值）到11111111 11111111 11111111 11111111（即-1）。如果你看左边的8位，幅度范围从10000000到11111111，即从128到255。
这些值可以通过这段代码获得。
V = ( A[i] >> 24 ) & 255
对于负数，V的值总是位于128到255之间。对于正数，它将从0到127。如前所述，M的值为-1时为255，在32位方案中最高的负数为128。像往常一样建立直方图。然后从索引128到255进行累积求和，然后将255的频率添加到0，并继续从0到索引127进行累积求和。像往常一样执行排序。这种技术在理论上和实践中都是最优、快速、优雅和整洁的。不需要任何类型的单独列表，也不需要在排序后进行顺序反转或将所有输入转换为正数，这会使排序变得缓慢和混乱。
有关代码，请参见基数排序优化。可以使用相同的概念构建64位版本。
进一步阅读：
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html
- ytoamn
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);
}
}
- John Q.
1
似乎是在http://www.codercorner.com/RadixSortRevisited.htm中提出的建议。去看看吧。 - cassepipe
2
当然可以！不过你需要把负数和正数分开处理，但幸运的是这很容易。在排序算法开始时，你只需要围绕值为0对数组进行划分。之后，对于划分点下面的数字使用基数排序，对于划分点上面的数字也使用基数排序。
以下是该算法的实际应用。我从Kevin Wayne和Bob Sedgewick的MSD基数排序中得出了此算法：http://algs4.cs.princeton.edu/51radix/MSD.java.html
以下是该算法的实际应用。我从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;
}
- AtlasMeh-ed
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;
}
}
- Abhijit Sarkar
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
- Alexander Shostak
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;
}
- cktan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 基数排序算法
- 13 将一个整数数组转换为非负整数数组
- 4 Python 基数排序
- 212 原地基数排序
- 9 C++实现的基数排序
- 5 基数排序解释
- 3 JavaScript中的基数排序
- 3 二进制中的负整数
- 7 JavaScript 基数排序
- 3 基数排序优化