アイデア: 文字通り、挿入とは要素をセット内の特定の要素に入れることです。シーケンスを 2 つの部分に分割する必要があります。1 つの部分は順序付きセットで、もう 1 つの部分は並べ替えられるセットです。
図:
##理解を容易にするために、最も特殊な 4321 シーケンスを例として取り上げます。上記の考え方によると、シーケンスを 2 つの部分に分割する必要があります。コーディングの便宜のために、要素が順序セットであると仮定すると、ループは 2 番目の要素 (3) から開始する必要があります。後続の操作で 3 を上書きしないようにするには、保存する一時変数 3。つまり、上記の
val=arr[1]、配列を操作しているため、注文された
カーソル
が境界を越えず、挿入される値がカーソルで示された位置より小さい場合(上図の #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. パフォーマンス テストと時間と空間の複雑さ
キーワード比較の数: KCN=(n^2)/2 キーワードの総数移動数:
RMN= (n^2)/2したがって、時間計算量は約
O(N^2)
2. ヒルソート (交換方法)1. アイデアの図解
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
,最初の要素がグループ内の値が 2 番目の要素より大きい場合 (
論理分類により、2 番目の要素のインデックスは最初の要素のすべての値の増分ギャップ
である必要があります)、2 つを交換します。それ以外の場合は
、比較を続けるか、ループから抜け出します。 この方法ですべてのグループを走査した後、増分を減らします (つまり、gap/=2
) )、増分ギャップが 1 になるまで上記の手順を続行します。値が 1 になると、シーケンスのソートは終了します。
3. 時間計算量ヒル ソートの時間計算量は、
4。増分シーケンスの選択について上記の並べ替えを行う場合
増分リダクション です。これは最適な選択ではありません。増分の選択は数学界の未解決の問題です。 しかし、それは決定することができます。はい、n->無限大
の場合、時間計算量は次のように削減できることが多数の実験によって証明されています:
##次のポイント
では、いくつかの実験も行っていますが、一定の規模 (800w ~ 100w など) 内の計算では確実に効果が得られます。 100 万)、ヒル ソートの速度はヒープ ソートの速度をはるかに上回ります
、少なくとも私のコンピュータではこれが当てはまります3. ヒル ソート (シフト法) Exchange メソッドは、shift メソッドよりもはるかに遅いため、shift メソッド
を使用し、shift メソッドは、exchange メソッド1 よりも挿入ソートに「似ています」。アイデアは、実際には上記の 2 つの並べ替え方法です。grouping
とのアイデアを具体化しています。 分割統治、比較的大きなシーケンスをいくつかの小さなシーケンスに分割する
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
以上がJavaで1億の乱数をソートするにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。