順序付けアルゴリズムjava実装--挿入法

4343 ワード
並べ替えはアルゴリズム導論に接触する時に最初に接触するアルゴリズムであり、学生時代に最も多く付き合ったアルゴリズムでもあります.この数日間はいくつかの違ったアルゴリズムをよく思い出して、自分の一番よく知らない外の並べ替えを含みます.
         並べ替えアルゴリズムを挿入します.直接並べ替え、二分割挿入順序、およびヒル並べ替えを含みます.
        直接コード
         メーン関数:
public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] is = new int[MAX];
		int[] shell = new int[MAX / 2];
		for (int i = 0; i < shell.length; i++) {
			if (i == 0) {
				shell[i] = MAX / 2;
			} else {
				shell[i] = shell[i - 1] / 2;
			}
		}
		shell[shell.length - 1] = 1;
		for (int i = 0; i < MAX; i++) {
//			is[i] = new Random().nextInt(MAX);
//			is[i] = i;
			is[i] = MAX - i;
		}
		long start = System.currentTimeMillis();
		
		shellSort(is, shell);
//		directSort(is);
//		binarySort(is);
		long end = System.currentTimeMillis();
		System.out.println("     " + (end - start) + "  ");
	}
 
          並べ替えの直接挿入:
/**
	 * @Title: directSort
	 * @Description: TODO(    )
	 * @param     
	 * @return void     
	 */
	public static void directSort(int[] is) {
		/**
		 *  0        ，          
		 */
		for (int i = 1; i < is.length; i++) {
			/**
			 *                   
			 */
			int k;
			int temp = is[i];
			for (k = i - 1; k >= 0 && is[k] > temp; k--) {
				is[k + 1] = is[k];
			}
			is[k + 1] = temp;
		}
	}
 直接的に並べ替えを挿入するという考えが一番分かりやすいということは、i番目の元素の前に並べられた数列を想定して、トランプを挿し込むように、後ろから前へ比較して、i番目の元素を適当な位置に挿し込むということです.
100万個の乱数を並べ替えます.直挿し法は1分56秒かかります.
     116072
 100万個の並べ替えられた配列を並べ替えて、直接挿入すると5ミリ秒かかります.
 
 
100万個の逆順の配列を並べ替えて、直挿し法は6分間かかります.
     249916
     二番目の挿入順序:
     
/**
	 * @Title: binarySort
	 * @Description: TODO(      )
	 * @param @param is     
	 * @return void     
	 */
	private static void binarySort(int[] is) {
		/**
		 *  0        ，          
		 */
		for (int i = 1; i < is.length; i++) {
			/**
			 *                   
			 */
			int temp = is[i];
			int left = 0;
			int right = i - 1;
			int mid = (left + right) / 2;
			while (left <= right) {
				if (temp > is[mid]) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
				mid = (left + right) / 2;
			}
			reverse(is, i, left);
		}
	}
           この方法もi番目の元素の前に並べられた数列を想定していますが、挿入する時はカードを挿す方法ではなく、2分で探す手段で、中間からi番目のカードの挿入すべき位置を調べて挿入します.この方法は直接的に挿入するよりも優れているところは、乱順であれば、検索する時の時間の複雑さはO(logn)だけである.
           二分割挿入法で1000万個の乱数を並べ替えると1分48秒かかります.
     108423
            二分割挿入法で1000万個の並べ替えられた配列は42秒かかります.
             二分割挿入法で1000万個の倒順を並べ替える行列は3分42秒です.
     224106
 
           ヒルの並べ替え:
/**
	 * @Title: shellSort
	 * @Description: TODO(    )
	 * @param @param is
	 * @return void     
	 */
	private static void shellSort(int[] is, int[] shell) {
		for (int i = 0; i < shell.length; i++) {
			int d = shell[i];
			for (int j = 0; j < d; j++) {
				for (int k = j + d; k < is.length; k = k + d) {
					int temp = is[k];
					int m;
					for (m = k - d; m >= 0 && is[m] > temp; m = m - d) {
						is[m + d] = is[m];
					}
					is[m + d] = temp;
				}
			}
		}
	}
            ヒルの並べ替えは直接挿入順序に似ています.彼の考えは主に順序を利用しています.直接並べ替えはほとんど時間がかかりません.最初に元の配列をいくつかの異なる配列に分けて並べ替え、最後に直接的に配列全体を挿入するまで再細分化します.しかし、この時は配列が基本的に整然としていますので、時間の消費はかなり少ないです.
        配列｛1、2、3、4｝のように、まず、ヒルの配列は2つのサブアレイに分かれています.｛1、3｝と｛2、4｝は、2つのサブアレイをそれぞれ直接挿入して並べ替えた後、再度直接に並べ替えを挿入します.ヒル順序付けの思想は分治アルゴリズムに似ています.大きな問題をいくつかの小さな問題に分けて、小さな問題の結果を利用して大きな問題を計算して、大きな問題を最適化します.
       ヒルが1000万個の乱数を並べ替えると、1秒未満の時間がかかります..
  
     209
            ヒルの並べ替えは1000万個で、並べ替えられた配列の所要時間は66ミリ秒です.
 
             ヒルは1000万個の倒順配列を並べ替えると82ミリ秒かかります.
          以上の比較から、挿入順序については、配列がほとんど順序を並べている場合に、直接挿入順序が一番いいが、現実にはこのような状況は多くない.現実にはほとんど乱れた順序の場合、このような状況でヒルが他の2つの挿入順序の方法を秒殺する.
KDツリーアルゴリズム
『アルゴリズム導論』第十五章第一練習問題コード