public static void sort( int[] a, int radix)
{
int i, m = a[0], exp = 1, n = a.length;
int[] b = new int[10];
for (i = 1; i < n; i++)
if (a[i] > m)
m = a[i];
while (m / exp > 0)
{
int[] bucket = new int[10];
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
}
}
try
int[] b = new int[a.length];
或自n = a.length
int[] b = new int[n];
我只是指出了最明显的问题，并将细节留给您。
时桶必须保留一个数字列表，因此仅使用一个int
List<Integer>[] bucket = new List<Integer>[10];
用于收集新顺序的元素的数组必须与原始数组相同。你只是把它长了10。
a[i] = b[i];
tells b的大小必须等于或大于a。因此，请@rcgldr答案。此外，传递给您功能的radix的值也未使用。您还可以通过交换数组指针而不是复制元素，即避免循环的最后一个。
int swap[] = a;
a = b;
b = swap;
return a;
above是您的程序以升序排序。我在下面提供以下顺序排序的程序。唯一需要的更改是开始添加从基本数组末端（在这种情况z）端的频率到索引零。
对于非阴性整数而不是使用
binary而不是
decimal，对于机器来说可能更有效，直观。 我写的是我编写的实现，带有测试案例：radixsort.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* Radix sort.
*
* @author eric
* @date 3/12/20 12:05 PM
*/
public class RadixSort {
/**
* Sort given array, the array will be modified.
*
* @param data array of integer of non-negative integers,
* @throws IllegalArgumentException if input contain negative integer,
*/
public static void sort(int[] data) {
int numSys = 2;
int bits = validAndfindHighestBit(data); // find highest bit,
// create queues,
List<List<Integer>> queues = new ArrayList<>(numSys);
for (int i = 0; i < numSys; i++) queues.add(new LinkedList<>());
// sort bit by bit, low to high,
for (int i = 0; i < bits; i++) {
// re-init queues,
for (int j = 0; j < numSys; j++) queues.get(j).clear();
// array -> queues,
for (int x : data) {
int bit = (x >> i) & 1; // get the i-th bit,
queues.get(bit).add(x);
}
// queues -> array,
int t = 0;
for (List<Integer> queue : queues) {
for (int x : queue) data[t++] = x;
}
}
}
/**
* Valid input number, and find highest bit that has 1.
*
* @param data
* @return
* @throws IllegalArgumentException if input contain negative integer,
*/
private static int validAndfindHighestBit(int[] data) {
// find max number,
int max = 0;
for (int x : data) {
if (x < 0) throw new IllegalArgumentException("negative integers are not supported");
if (x > max) max = x;
}
System.out.printf("max number: %d, ", max);
// find highest bit,
int highestBit = 0;
while (max != 0) {
highestBit++;
max >>= 1;
}
System.out.printf("highest bit: %d\n", highestBit);
return highestBit;
}
}
（通过
TestNG
import org.testng.Assert;
import org.testng.annotations.Test;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;
import static org.testng.Assert.*;
/**
* RadixSort test.
*/
public class RadixSortTest {
@Test
public void testSort() {
int[] data;
// generated un-sorted random array,
do data = genRandomArr(); while (data.length > 1 && isSorted(data));
System.out.printf("input arr:\t%s\n", Arrays.toString(data));
if (data.length > 1) Assert.assertFalse(isSorted(data));
// sort
RadixSort.sort(data);
System.out.printf("output arr:\t%s\n", Arrays.toString(data));
Assert.assertTrue(isSorted(data));
}
// corner case,
@Test
public void testSort_corner() {
int[] dataEmpty = new int[0]; // empty array,
RadixSort.sort(dataEmpty);
Assert.assertTrue(isSorted(dataEmpty));
int[] dataSingle = new int[]{5}; // single element,
RadixSort.sort(dataSingle);
Assert.assertTrue(isSorted(dataSingle));
}
// invalid input,
@Test(expectedExceptions = IllegalArgumentException.class)
public void testSort_invalid() {
int[] dataSingle = new int[]{1, -1}; // negative number,
RadixSort.sort(dataSingle);
}
/**
* generate random array, of size 10, in range [0, 1024),
*
* @return
*/
public static int[] genRandomArr() {
return genRandomArr(10, 100);
}
/**
* generate random array,
*
* @param size array size, default to 10,
* @param bound upper bound, default to 100,
* @return
*/
public static int[] genRandomArr(int size, int bound) {
if (size <= 0) size = 10;
if (bound <= 0) bound = 100;
ThreadLocalRandom rd = ThreadLocalRandom.current();
int[] arr = new int[size];
for (int i = 0; i < arr.length; i++) arr[i] = rd.nextInt(bound);
return arr;
}
// check whether array is sorted,
private static boolean isSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) return false;
}
return true;
}
}
公共类Radixsort {
static void countSort(int arr[], int n, int exp){
//output array
int output[] = new int[n];
// Count array for digits (0-9)
int count[] = new int[10];
for(int i = 0; i < 10; i++)
count[i] = 0;
// Count occurrences of digits at the current place value(exp)
for(int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// update count[i] to store actual positons in output[]
for(int i = 1; i < 10; i++)
count[i] += count[i-1];
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// copy the sorted output array back to arr[]
for(int i = 0; i < n; i++)
arr[i] = output[i];
}
public static void main(String[] args) {
}