时间戳

首页 > 解决方案 > 计数排序实现

java - 计数排序实现

问题描述

你好我在java中实现计数排序方法有困难。我相信问题来自我在方法中的最后两个循环。我收到一个 ArrayIndexOutOfBounds 异常：8。我相信这来自我倒数第二个 for 循环，当索引 5 处的值为 8 但我不知道如何解决这个问题。任何帮助表示赞赏。谢谢！

在我的代码中，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;
    }
}

标签： javaarraysindexoutofboundsexceptioncounting-sort

解决方案

问题出在第一个循环中，因为数组temp长度为 6，并且您在那里进行了 7 次交互。

所以在for它试图做temp[6]=0的最后，你的数组的最后一个位置是temp[5].

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

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

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

推荐阅读