-2

我的程序(一个使用字母频率来解密事物的解密器)有两个 ArrayList,用于跟踪字母频率。我将这些 ArrayList 配对,以便一个(输入中的字符列表)始终链接到另一个(输入中的频率列表),以便索引 i 处的字符始终对应于索引 i 处的频率在另一个。我使用快速排序算法按降序排序。这是快速排序和交换方法的代码:

private static void quickSort(int low, int high){


    int i = low;
    int j = high;
    long middle = freqInCiphertext.get((low+high)/2);

    while (i < j) {
        while (freqInCiphertext.get(i) > middle) {
            i++;
        } //End while
        while (freqInCiphertext.get(j) < middle) {
            j--;
        }//End while
        if (j >= i) {
            swap(i, j);
            i++;
            j--;
        } // End if
    } // End while


    if (low<j) {
        quickSort(low, j);
    } else if (i<high) {
        quickSort(i, high);
    } //end if
}//End quickSort

private static void swap(int i, int j) {
int tempInt = freqInCiphertext.get(i);
String tempString = charsInCiphertext.get(i);

freqInCiphertext.set(i, freqInCiphertext.get(j));
charsInCiphertext.set(i, charsInCiphertext.get(j));

freqInCiphertext.set(j, tempInt);
charsInCiphertext.set(j, tempString);
}// End swap

但是,当我运行我的代码时,它会返回部分排序的数组列表,如下所示:

[ , e, t, a, o, n, i, h, r, d, l, u, s, m, z, q, x, j, v, k, p, f, w, c, b, y, g]
[64031, 25856, 19326, 17571, 16398, 14349, 14200, 12784, 11617, 9930, 8391, 5820, 12934, 5636, 173, 178, 312, 356, 1929, 2175, 3186, 4310, 5479, 4666, 3491, 4673, 5100]

任何人都可以看到算法中的任何错误吗?我已经尝试了几种不同的方法(比如 >= 而不是 > 等),但没有运气。

4

1 回答 1

5

由于 j 可以 > 低于 low 并且 i 可以同时 < high,因此您不想执行“else if (i < high)”。如果这样的话,那应该是单独的:

if (low<j) {
    quickSort(low, j);
}

if (i<high) {
    quickSort(i, high);
}
于 2012-07-15T03:47:04.540 回答