-1

这是我的计数排序程序：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int arr[] = new int[n];
        int b[] = new int[n+1];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int c[] = new int[100];
        for (int i = 1; i < 100; i++) {
            c[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            c[arr[i]] = c[arr[i]] + 1;
        }
        for (int i = 1; i < 100; i++) {
            c[i] = c[i] + c[i - 1];
        }
        for (int i = n-1; i > 0; i--) {
            b[c[arr[i]]] = arr[i];
            c[arr[i]] = c[arr[i]] -1;
        }
        for (int i = 1; i < n; i++) {
            System.out.print(b[i] + " ");
        }
    }

输入：

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 72 3 4 86 960 2 729 3 86 960 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 79 77 61 75 1 2 2 33

预期输出：

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 45 44 45 56 6 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

实际输出：

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 45 44 45 56 6 57 59 60 61 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 9 90 91 98 9 9 9 9 9 9 9 92

我得到的输出缺少一个数字63。我无法纠正这个问题。

4

1 回答 1

5

你从 1 而不是 0 迭代，所以你错过了第一个数字，即 63

for (int i = 1; i < n; i++) {
    c[arr[i]] = c[arr[i]] + 1;
}

在最后一个循环中，你打破 when i>0，而不是i>=0

于 2013-10-23T20:08:34.457 回答