毎日少しのアルゴリズムを学ぶ-集計ソートアルゴリズム

集計ソートアルゴリズム
定義＃テイギ＃
集計ソート(Merge sort,台湾訳:集計ソート)は、集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.
ステップ
1.マージされたシーケンスを格納するために使用される2つのソートされたシーケンスの合計サイズの申請スペース
2.2つのポインタを設定し、最初の位置はそれぞれ2つの並べ替えられたシーケンスの開始位置である
3.2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージスペースに入れ、ポインタを次の位置に移動します.
4.あるポインタがシーケンスの最後に達するまで手順3を繰り返す
5.他のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーする
時間の複雑さ
O(nlogn)
コード#コード#

package com.sprd.test.algorithm;

/**
 * Copyright 2014 TJ SPREADTRUM TEST_AF All Right Reserved
 * 
 * @author: hui.qian Created on 2014 11 27    9:09:13 Description:
 */
public class Mergesort {

	public int[] sort(int[] a, int[] b) {
		int[] merge = new int[a.length + b.length];
		int indexA = 0;
		int indexB = 0;
		int i = 0;
		while (indexA < a.length && indexB < b.length) {
			if (a[indexA] <= b[indexB]) {
				merge[i++] = a[indexA++];
			} else {
				merge[i++] = b[indexB++];
			}
		}
		if (indexA == a.length) {
			for (int j = indexB; indexB < b.length; indexB++) {
				merge[i++] = b[indexB];
			}
		} else {
			for (int j = indexA; indexA < a.length; indexA++) {
				merge[i++] = b[indexA];
			}
		}
		return merge;
	}

	public static void main(String[] args) {
		int[] sortA = { 1, 3, 5, 7, 9 };
		int[] sortB = { 2, 4, 6, 8, 10 };
		Mergesort sorter = new Mergesort();
		long start = System.currentTimeMillis();
		int[] sorted = sorter.sort(sortA, sortB);
		long end = System.currentTimeMillis();
		System.out.println("   ： " + (end - start));
		System.out.println("    ： ");
		print(sortA);
		print(sortB);
		System.out.println("    ： ");
		print(sorted);
	}

	public static void print(int[] datas) {
		for (int i = 0; i < datas.length; i++) {
			System.out.print(datas[i] + " ");
		}
		System.out.println("");
	}
}

しゅつりょく

   ： 0
    ： 
1 3 5 7 9 
2 4 6 8 10 
    ： 
1 2 3 4 5 6 7 8 9 10