2

初歩的な質問でしたらすみません...

アルゴリズムについてもっと勉強しようとしています...

挿入ソートを昇順で行う簡単なコードを書いたのですが、なぜか降順でソートすることができませんでした。

比較キーを変更してみました (while (i > 0 && a[i] > key) to (i > 0 && a[i] < key)).. 部分的に動作するようですが、最初の要素がソートされていません。以下の結果が得られます。どこが間違っているか教えてもらえますか?

1 11 10 9 5 4 3 2

public class InsertionSort {
    public static void main(String args[]) {
        int[] a = { 1,10,11,5, 9, 3, 2, 4 };
        // Loop through the entire array length. Consider you already have one
        // element in array, start comparing with
        // first element
        for (int j = 1; j < a.length; j++) {
            // Get the key (The value that needs to be compared with existing
            // values.
            int key = a[j];
            // Get the array index for comparison, we need to compare with all
            // other elements in the array with
            // key
            int i = j - 1;
            // While i > 0 and when key is less than the value in the array
            // shift the value and insert
            // the value appropriately.
            //System.out.println(j);
            while (i > 0 && a[i] < key) {
                a[i + 1] = a[i];
                i = i - 1;
                a[i + 1] = key;
            }
        }
        for (int k = 0; k < a.length; k++) {
            System.out.println(a[k]);
        }
    }
}
4

4 に答える 4

9

あなたは決して触れa[0]ていません

while (i > 0 && a[i] < key) {

そのため、本来の場所に分類されません。>=の代わりに使用>:

while (i >= 0 && a[i] < key) {

昇順で並べ替えると、同じ問題が発生します。

于 2013-03-08T15:56:52.913 に答える
2

配列の最初の要素は ですa[0]。あなたはどこでもそれを比較していません。

于 2013-03-08T15:56:58.630 に答える
1

配列 a[] で 0 から開始して、最初の要素 a[0] に到達します。したがって、a[j] の最初の要素は a[1] ではなく a[0] になります。

于 2013-03-08T15:59:24.923 に答える
1 
public static void insertionSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int curNumber = arr[i];
            int curIndex = i-1;
            while ( curIndex >= 0 && arr[curIndex] < curNumber)
            {
                arr[curIndex+1] = arr[curIndex];
                curIndex--;
            }
            arr[curIndex+1] = curNumber;
        }
    }
于 2020-04-01T03:22:06.210 に答える