Javaで1億の乱数をソートするにはどうすればよいですか?

1. 直接挿入ソート

1. 図解による挿入ソート

アイデア: 文字通り、挿入とは要素をセット内の特定の要素に入れることです。シーケンスを 2 つの部分に分割する必要があります。1 つの部分は順序付きセットで、もう 1 つの部分は並べ替えられるセットです。

図:

##理解を容易にするために、最も特殊な 4321 シーケンスを例として取り上げます。

上記の考え方によると、シーケンスを 2 つの部分に分割する必要があります。コーディングの便宜のために、要素が順序セットであると仮定すると、ループ

は 2 番目の要素 (3) から開始する必要があります。後続の操作で 3 を上書きしないようにするには、保存する一時変数 3。つまり、上記の

val=arr[1]

、配列を操作しているため、注文された

の終わりも取得する必要があります。 set 要素のインデックスがカーソルとして使用されます

カーソル

が境界

を越えず、挿入される値がカーソルで示された位置より小さい場合(上図の #4) 、要素 4 を後方に移動し、カーソルを前方に移動し、カーソルが交差するまでセット内の他の要素が挿入される要素より小さいかどうかを確認し続けます。境界。ループが終了します。次の比較ラウンドが始まります。2. コードの実装

public static void insertSort(int[]arr){
        for(int i = 1 ; i < arr.length; i++){
            int val = arr[i];
            int valIndex = i - 1; //游标
            while(valIndex >= 0 && val < arr[valIndex]){ //插入的值比游标指示的值小
                arr[valIndex + 1] = arr[valIndex];
                valIndex--; //游标前移
            }
            arr[valIndex+1] = val;
        }
    }
1234567891011

3. パフォーマンス テストと時間と空間の複雑さ

実際の実行800,000 件のデータには 1 分 4 秒かかります (正確な値ではなく、各マシンが異なる可能性があります)

ソート レコードとキーワードが少ない場合は、直接挿入の方が効率的です。高い

時間計算量:

キーワード比較の数: KCN=(n^2)/2 キーワードの総数移動数:

RMN= (n^2)/2

したがって、時間計算量は約 O(N^2)

2. ヒルソート (交換方法)1. アイデアの図解

#2. コード実装

public static void shellSort(int[] arr){ //交换法
        int tmp = 0;
        for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2){
            for(int i = gap ; i < arr.length ; i++){ //先遍历所有数组
                for(int j  = i - gap ; j >= 0 ; j -= gap){//开启插入排序
                    if(arr[ j ] > arr[ gap + j ]){ //可以根据升降序修改大于或小于
                        tmp = arr[gap + j];
                        arr[j+gap] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            System.out.println(gap);
            System.out.println(Arrays.toString(arr));
        }
    }
12345678910111213141516

ここが最も理解しにくいことです

j = i - gap

、グループ内の最初の要素を表します。つまり、

j=0

,最初の要素がグループ内の値が 2 番目の要素より大きい場合 (論理分類により、2 番目の要素のインデックスは最初の要素のすべての値の増分ギャップ である必要があります)、2 つを交換します。それ以外の場合は

j-=gap

、比較を続けるか、ループから抜け出します。 この方法ですべてのグループを走査した後、増分を減らします (つまり、gap/=2) )、増分ギャップが 1 になるまで上記の手順を続行します。値が 1 になると、シーケンスのソートは終了します。

3. 時間計算量ヒル ソートの時間計算量は、

関数に依存します。特定の問題の詳細な分析が必要な増分シーケンス

の値は明確な値ではなく、これは議論する必要がある4番目の点でもあります

4。増分シーケンスの選択について上記の並べ替えを行う場合

増分リダクション

選択されたモデルは

gap/=2

です。これは最適な選択ではありません。増分の選択は数学界の未解決の問題です。 しかし、それは決定することができます。はい、n->無限大の場合、時間計算量は次のように削減できることが多数の実験によって証明されています:

##次のポイント

シフト法

では、いくつかの実験も行っていますが、一定の規模 (800w ～ 100w など) 内の計算では確実に効果が得られます。 100 万)、ヒル ソートの速度はヒープ ソートの速度をはるかに上回ります

、少なくとも私のコンピュータではこれが当てはまります

3. ヒル ソート (シフト法) Exchange メソッドは、shift メソッドよりもはるかに遅いため、shift メソッド

を使用し、shift メソッドは、exchange メソッド

1 よりも挿入ソートに「似ています」。

アイデアは、実際には上記の 2 つの並べ替え方法です。grouping

と

insertion

の利点を組み合わせると、非常に効率的です。

のアイデアを具体化しています。 分割統治、比較的大きなシーケンスをいくつかの小さなシーケンスに分割する

2. コードの実装

public static void shellSort02(int[] arr){ //移位法
        for(int gap = arr.length/2 ; gap > 0 ; gap /= 2){ //分组
            for(int i = gap ; i < arr.length ; i++){ //遍历
                int valIndex = i;
                int val = arr[valIndex];
                if(val < arr[valIndex-gap]){ //插入的值小于组内另一个值
                   while(valIndex - gap >=0 && val < arr[valIndex-gap]){ //开始插排
                       // 插入
                       arr[valIndex] = arr[valIndex-gap];
                       valIndex -= gap; //让valIndex = valIndex-gap (游标前移)
                   }
                }
                arr[valIndex] = val;
            }
        }
    }
12345678910111213141516

3. 実験的結果＃＃＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃＃＃

以上がJavaで1億の乱数をソートするにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。