並べ替え編(3)--並べ替えを直接挿入する

一、直接並べ替えを挿入する
基本思想:記録を並べられた秩序表に挿入し、それによって新しい記録数増1の秩序表を得る.
二、並べ替えコードの直接挿入例

package Sort;

/**
 * Created by LKL on 2017/2/28.
 */
public class TestInsertSort {
    public static void main(String[] args ){
        int[] adj={9,1,5,8,3,7,4,6,2};
        InsertSort(adj);
        for(int i : adj){
            System.out.print(i);
        }
    }
   private static void InsertSort(int[] adj){
       int temp=0;
       for (int i = 1; i < adj.length; i++) {
           for (int j = i-1; j >= 0 && adj[j]>adj[j+1]; j--) {
                   temp = adj[j +1];
                   adj[j + 1] = adj[j];
                   adj[j] = temp;
               }
           }
       }
   }

ステップ説明:i=1の場合、j=0、adj[0]>adj[1]は、forループに入り、データ交換を行います.このとき、j=-1は、内部層サイクル条件を満たしていません.このとき、adj[0]=1、adj[1]=9です.i=2の場合、現在adj[1]>adj[2]は、同様にforループを行い、データ交換を行う.次の手順は順次行いますが、再度紹介しません.
三、直接挿入並べ替えの複雑さ分析
空間から見ると、それは記録の補助空間だけが必要で、その時間の複雑さを主に見る.一番いい状況は順序表自体が秩序であり、全部でn-1回比較しました.移動記録がなく、時間の複雑さはO(n)です.最悪の場合は、ソートテーブル自体が逆順であり、その場合は比較(n＋2)(n−1)／2回が必要であり、移動の最大回数は(n＋4)(n−1)／2であり、この時点で総時間複雑度はO(n＾2)となる.特に,同じ時間での複雑さは,直接挿入秩序化法が泡の発生と簡単な選択秩序化の性能よりも優れていることを指摘した.
文章はただ自分の学習ノートとして、ネット上の例を参考にしました.