並べ替え、並べ替え、泡並べ替えテストの挿入

ソフトウェアエンジニアリングの“最も簡単なのが最も良いです”の思想の影響を受けて、あるずっと計算方のこれらのものに対して風邪を引かないで、それからプログラミングの深く入り込むことに従って、よく整理して、この方面の知識を学ぶ必要があると感じました.アルゴリズムは基本です.以下では三つの最も一般的なO(N＊N)時間複雑度のアルゴリズムについて試験し,ついでにそれらの性能を分析して理解を深めた.(MergeSortは正規並べ替えです.参考にします.)
    テストコード:

public static void main(String[] args) {
		int length = 100000;
	        testInsertSort(length);
	        testInsertSortWhenSorted(length);
		testSelectSort(length);
		testSelectSortWhenSorted(length);
		testMergeSort(length);
		testMergeSortWhenSorted(length);
		testBubbleSort(length);
		testBubbleSortWhenSorted(length);
		//testInsertSortRecu(length);
		//testInsertSortRecuWhenSorted(length);
}

public static void testInsertSort(int length){
		int[] array = SortUtil.createArray(length);
		SortUtil.printArray(array);
		long l1 = System.currentTimeMillis();
		SortUtil.insertSort(array);
		long l2 = System.currentTimeMillis();
		System.out.println("InsertSort time takes " + (l2 - l1) + " ms");
		SortUtil.printArray(array);
		
}
	
	public static void testInsertSortWhenSorted(int length){
		int[] array = SortUtil.createArray(length);
		SortUtil.mergeSort(array, 0, length -1);
		SortUtil.printArray(array);
		long l1 = System.currentTimeMillis();
		SortUtil.insertSort(array);
		long l2 = System.currentTimeMillis();
		System.out.println("InsertSortWhenSorted time takes " + (l2 - l1) + " ms");
		SortUtil.printArray(array);
		
}

    そのうちのarrayの要素はいずれもJavaのMath.random()でランダムに生成され、範囲は0から1000以内である.
    配列の長さ:1000
InsertSort time tars 0 ms
InsertSortWhenSorted time tars 0 ms
SelectSort time tars 0 ms
testSelectSortWhenSorted time tars 0 ms
MergSort time tars 0 ms
MergSortWhenSorted time tars 0 ms
Bbble Sort time tars 15 ms
Bbble SortWhenSorted time tars 0 ms
    配列の長さは10000
InsertSort time tars 63 ms
InsertSortWhenSorted time tars 0 ms
SelectSort time tars 109 ms
testSelectSortWhenSorted time tars 109 ms
MergSort time tars 0 ms
MergSortWhenSorted time tars 0 ms
Bbble Sort time tars 250 ms
Bbble SortWhenSorted time tars 0 ms
    配列の長さは100000です.
InsertSort time tars 5453 ms
InsertSortWhenSorted time tars 0 ms
SelectSort time tars 11000 ms
testSelectSortWhenSorted time tars 11047 ms
MergSort time tars 15 ms
MergSortWhenSorted time tars 16 ms
Bbble Sort time tars 25250 ms
Bbble SortWhenSorted time tars 0 ms
    もう一回の配列の長さは100000です.
InsertSort time tars 5454 ms
InsertSortWhenSorted time tars 0 ms
SelectSort time tars 11031 ms
testSelectSortWhenSorted time tars 11031 ms
MergSort time tars 32 ms
MergSortWhenSorted time tars 16 ms
Bbble Sort time tars 2572 ms
Bbble SortWhenSorted time tars 0 ms
    配列長:5000000
InsertSortWhenSorted time tars 15 ms
Bbble SortWhenSorted time tars 16 ms
 
まとめてみます
    1,これらの3つの並べ替えの時間複雑度はO(n＊n)であるが、やはり違いがある.
    2,配列が無秩序な場合、一番速く挿入され、順番を選ぶと泡が一番遅くなります.並べ替えの選択時間の複雑さはO(n＊n)であり、挿入順序が最悪の場合はO(n＊n)であるため、平均するとその半分しかない.一方、泡立て並べ替えは、移動データが多いため、時間の消費がもっと大きいです.
    3,配列が整然としている場合、泡が発生する(ここではホイッスル判定を加えて、配列が移動しない時は早目に飛び出す循環)と挿入順序(時間複雑度はO(n)))が比較的速い.選択の順序はあまり影響がありません.
 
    主な実現コードの参考:

    public static int[] createArray(int length) {
		int[] array = new int[length];
		for (int index = 0; index < length; index++) {
			array[index] = (int) (Math.random() * 1000 +  Math.random() * 100 +Math.random() * 10);
		}
		return array;
    }

    public static void insertSort(int[] array) {
		for (int i = 1; i < array.length; i++) {
			int key = array[i];
			int j = i - 1;
			for (; j > -1 && key < array[j]; j--) {
				array[j + 1] = array[j];
			}
			array[j + 1] = key;
		}
	}

	public static void selectSort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			int min = i;
			for (int j = i; j < array.length; j++) {
				if (array[min] < array[j]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = array[i];
				array[i] = array[min];
				array[min] = temp;
			}
		}
	}

	public static void mergeSort(int[] array, int begin, int end) {
		if (end > begin) {
			int sep = (begin + end) / 2;
			mergeSort(array, begin, sep);
			mergeSort(array, sep + 1, end);
			merge(array, begin, sep, end);
		}
	}

	private static void merge(int[] array, int begin, int sep, int end) {
		int[] left = new int[sep - begin + 1];
		int[] right = new int[end - sep];
		System.arraycopy(array, begin, left, 0, sep - begin + 1);
		System.arraycopy(array, sep + 1, right, 0, end - sep);

		int i = 0, j = 0;

		// Copy left or right array to the array
		while (i < left.length && j < right.length) {
			if (left[i] <= right[j]) {
				array[begin + i + j] = left[i];
				i++;
			} else {
				array[begin + i + j] = right[j];
				j++;
			}
		}
		// If left array has more elements
		if (i < left.length) {
			System.arraycopy(left, i, array, begin + i + j, left.length - i);
		} else if (j < right.length) { // If right array has more elements
			System.arraycopy(right, j, array, begin + i + j, right.length - j);
		}
	}

	public static void bubbleSort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			boolean isSorted = true;
			for (int j = 0; j < array.length - i - 1; j++) {
				int temp;
				if (array[j] > array[j + 1]) {
					isSorted = false;
					temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
				}
			}
			if(isSorted){
				break;
			}
		}
	}