计数排序实现

Question

您好，我在java中实现计数排序方法时遇到困难。我相信问题来自我在方法中的最后两个循环。我收到一个 ArrayIndexOutOfBounds 异常：8。 我相信这来自我在索引 5 处的值为 8 时倒数第二个 for 循环，但我不确定如何解决这个问题。任何帮助，不胜感激。谢谢！

在我的代码中，k 是输入数组中的最大值。

法典：

public static void main(String[] args) {
int [] arrayOne = {0,1,1,3,4,5,3,0};
int [] output = Arrays.copyOf(arrayOne, arrayOne.length);
System.out.println(Arrays.toString(arrayOne));
countingSort(arrayOne, output, 5);
System.out.println(Arrays.toString(output));
}
public static void countingSort(int[] input, int[] output , int k){
int [] temp = Arrays.copyOf(input, k+1);
for (int i = 0; i <= k; i++){
temp[i] = 0;
}
for (int j = 0; j <= input.length - 1; j++){
temp[input[j]] = temp[input[j]] + 1;
}
for (int i = 1; i <= k; i++){
temp[i] = temp[i] + temp[i-1];
}
for (int j = input.length; j >= 1; j--){
output[temp[input[j]]] = input[j];
temp[input[j]] = temp[input[j]] - 1;
}
}

Answer 1

问题出在第一个循环中，因为数组temp长度为 6，而您在其中执行 7 次交互。

因此，在for结束时，它正在尝试执行temp[6]=0并且数组的最后一个位置是temp[5].

要解决此问题，请将您的第一个循环更改为：

for (int i = 0; i < k; i++){

在最后一个循环中，您将获得相同的异常原因input[8]不存在。

Answer 2

import java.util.Arrays;
public class CountingSort {
public static void main(String[] args) {
int[] input = {0,1,1,3,4,5,3,0};
int[] output = new int[input.length];
int k = 5; // k is the largest number in the input array
System.out.println("before sorting:");
System.out.println(Arrays.toString(input)); 
output = countingSort(input, output, k);
System.out.println("after sorting:");
System.out.println(Arrays.toString(output));
}
public static int[] countingSort(int[] input, int[] output, int k) {
int counter[] = new int[k + 1]; 
for (int i : input) { counter[i]++; } 
int ndx = 0; 
for (int i = 0; i < counter.length; i++) {
while (0 < counter[i]) { 
output[ndx++] = i;
counter[i]--; 
}
}
return output;
}
}

以上代码改编自： http://www.java67.com/2017/06/counting-sort-in-java-example.html

Answer 3

这可能会有所帮助，但请尝试使用 Arraya.sort(( 方法。 例如：

//A Java program to sort an array of integers in ascending order.
// A sample Java program to sort an array of integers 
// using Arrays.sort(). It by default sorts in 
// ascending order 
import java.util.Arrays; 
public class SortExample 
{ 
public static void main(String[] args) 
{ 
// Our arr contains 8 elements 
int[] arr = {13, 7, 6, 45, 21, 9, 101, 102}; 
Arrays.sort(arr); 
System.out.printf("Modified arr[] : %s", 
Arrays.toString(arr)); 
} 
}

示例是 https://www.geeksforgeeks.org/arrays-sort-in-java-with-examples/中的代码片段

Answer 4

根据实现后的算法，我已经为计数排序技术做好了准备

public static int[] countSort(int elements[]) {
int[] sorted = new int[elements.length+1];
int[] range = new int[getMax(elements)+1];
for(int i=0;i<range.length;i++) {
range[i] = getCount(i, elements);
try {
range[i] = range[i]+range[i-1];
}catch(ArrayIndexOutOfBoundsException ae) {
continue;
}
}       
for(int i=0;i<elements.length;i++) {
sorted[range[elements[i]]] = elements[i];
range[elements[i]] = range[elements[i]]-1;
}       
return sorted;
}
public static int getCount(int value,int[] elements) {
int count = 0;
for(int element:elements) {
if(element==value) count++;
}
return count;
}
public static int getMax(int elements[]) {
int max = elements[0];
for(int i=0;i<elements.length;i++) {
if(max<elements[i]) {
max = elements[i];
}           
}
return max;
}

请查看并让我知道是否有任何反馈，这更有帮助。 注意： 非负 no 在上述实现中不支持。 不要使用排序数组的第 0 个索引。