计数排序 Java - 意外结果
Counting sort Java - Unexpected results
class CountingSort {
int[] csort(int[] arr) {
int n = arr.length;
int max = arr[0];
int[] out = new int[n];
for (int i : arr) {
if (max < i) {
max = i;
}
}
int range = max + 1;
int[] te = new int[range];
for (int i = 0; i < range; ++i) {
te[i] = 0;
}
for (int j = 1; j < n; j++) {
te[arr[j]] = te[arr[j]] + 1;
}
// case1: {0,0,0,1,0,1,1,0,1,1}
// case2: {0,0,0,1,0,1,1,0,1,1}
for (int k = 1; k < range; ++k) {
te[k] = te[k] + te[k - 1];
}
// case1: {0,0,0,1,1,2,3,3,4,5}
// case2: {0,0,0,1,1,2,3,3,4,5}
for (int l = n - 1; l >= 0; --l) {
out[te[arr[l]]] = arr[l];
te[arr[l]] = te[arr[l]] - 1;
}
return out;
}
}
以上是计数排序的代码。以下是我的观察
- 如果最小的输入数组是第一个元素,例如
{1, 6, 8, 3, 5, 9}
它给出预期的输出 {1, 3, 5, 6, 8, 9}
- 但是如果给输入数组使得第一个元素不是最小的,例如
{4, 6, 8, 3, 5, 9}
那么输出的第一个元素为零并且一个数字丢失。
我试过但似乎无法找到这是怎么发生的。
计算出现次数的循环不会遍历所有元素,您正在跳过 arr[0]
。
for (int j = 0; j < n; j++) {
te[arr[j]] = te[arr[j]] + 1;
}
另外,你可以写得更"elegant"的方式:
for (int j = 0; j < n; ++te[arr[j]], ++j);
class CountingSort {
int[] csort(int[] arr) {
int n = arr.length;
int max = arr[0];
int[] out = new int[n];
for (int i : arr) {
if (max < i) {
max = i;
}
}
int range = max + 1;
int[] te = new int[range];
for (int i = 0; i < range; ++i) {
te[i] = 0;
}
for (int j = 1; j < n; j++) {
te[arr[j]] = te[arr[j]] + 1;
}
// case1: {0,0,0,1,0,1,1,0,1,1}
// case2: {0,0,0,1,0,1,1,0,1,1}
for (int k = 1; k < range; ++k) {
te[k] = te[k] + te[k - 1];
}
// case1: {0,0,0,1,1,2,3,3,4,5}
// case2: {0,0,0,1,1,2,3,3,4,5}
for (int l = n - 1; l >= 0; --l) {
out[te[arr[l]]] = arr[l];
te[arr[l]] = te[arr[l]] - 1;
}
return out;
}
}
以上是计数排序的代码。以下是我的观察
- 如果最小的输入数组是第一个元素,例如
{1, 6, 8, 3, 5, 9}
它给出预期的输出{1, 3, 5, 6, 8, 9}
- 但是如果给输入数组使得第一个元素不是最小的,例如
{4, 6, 8, 3, 5, 9}
那么输出的第一个元素为零并且一个数字丢失。 我试过但似乎无法找到这是怎么发生的。
计算出现次数的循环不会遍历所有元素,您正在跳过 arr[0]
。
for (int j = 0; j < n; j++) {
te[arr[j]] = te[arr[j]] + 1;
}
另外,你可以写得更"elegant"的方式:
for (int j = 0; j < n; ++te[arr[j]], ++j);