ソート挿入[Sort](ソートを挿入)


整列挿入

  • から、要素の位置に移動する位置
  • に挿入する.
    入力リスト:(7,3,2,8,9,4,6,1,5)

  • 現在のターゲットの数値と前の位置の要素を比較します.(最初のターゲットは2番目の要素から始まります.)

  • ターゲットの数が以前の位置の要素より小さい場合は、位置を交換します.

  • 次にターゲットを見つけ、上記の方法で繰り返します.
  • 配置解析の挿入

  • 一次ナビゲーション時間複雑度:O(i)
  • 総演算時間:O(n 2)
  • リストの部分を並べ替えたほうがいいです.小nの最適ソート方法
  • インプリメンテーション

    public class Main {
    
        public static void main(String[] args) {
            int[] arr = {7, 3, 2, 8, 9, 4, 6, 1, 5};
            insertSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void insertSort(int[] arr) {
            for (int end = 1; end < arr.length; end++) {
                for (int i = end; i > 0; i--) {
                    if (arr[i - 1] > arr[i])
                        swap(arr, i - 1, i);
                }
            }
        }
    
        private static void swap(int[] arr, int a, int b) {
            int tmp = arr[a];
            arr[a] = arr[b];
            arr[b] = tmp;
        }
    }
    reference
    高麗(コリョ)大学の金相昆(キム・サンクン)教授講座の
  • Java[JAVA]-挿入位置合わせ
  • [アルゴリズム]挿入ソート-挿入シーケンス(Python,Java)