整列挿入

1487 ワード
アルゴリズム#アルゴリズム# 整列挿入 テキストリンク

整列挿入

  • は2番目の要素から始まります.前の要素と比較して、挿入する位置を指定し、その後、要素を後方に移動し、指定位置に要素
    • を挿入する.
  • 最適の場合,O(n)効率は極めて高く,他の並べ替えアルゴリズムの一部である.

    • Process

  • ソート2番目の位置(インデックス)の値をtempに
    • 格納.
  • tempを前の要素と比較して挿入します.
  • 1を返し、次の場所の値をtempに保存して繰り返します.

    • Code

    void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           
   }
   System.out.println(Arrays.toString(arr));
}
  • は、まず第2の要素から始まる.この要素の値をtempに入れます.
  • は、要素の前の要素とその値を比較し、前の要素の値がより大きい場合は、その値を要素の値
    • に変更する.
  • prev--=>前の要素を比較し、
    • を繰り返す
  • 前のシーケンスの要素がその要素の値より大きくない場合、前のシーケンスにtempを代入する
    //1つの数字を含み、前の数字の概念を比較し続ける

    • 時間の複雑さ

  • 最悪の場合(逆配列の場合)は、(n-1)+(n-2)+...+を1つずつ比較する必要がある2 + 1 => n(n-1)/2 => O(n^2)
  • はいずれもソートされており,1回のみ比較されるため,O(n)の時間的複雑さを有する.
  • 最適:O(n 2)最悪:O(n^2)

    • くうかんふくざつさ

  • で与えられた配列では交換(swap)によって並べ替えられているのでO(n)

    • 長所

  • アルゴリズムは簡単な
    • です
  • ほとんどの要素がソートされている場合、非常に効率的である可能性があります.
  • は、ソートするアレイで交換されるため、異なるメモリ空間X(その場ソート)
    • が必要となる.
  • 安定ソート
  • 選択ソートやBubbleソートなどのO(n^2)アルゴリズムと比較して比較的速い.

    • 短所

  • の平均と最悪の時間複雑度はO(n^2)であり,効率はなかった.
  • 泡の配列と選択配列と同様に、アレイの長さが長ければ長いほど、効率は
    • 低下する.
    Kinx 実現技術 - Fiber
    KACA-新しいアイデンティティを推奨(java)