JAvaソートアルゴリズムと複雑度

泡のソート:
 

public class Bubble {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 77, 1, 65, 13, 81, 93, 10, 5, 23, 17 };
		for (int m = a.length - 1; m > 0; m--) {
			for (int n = 0; n < m; n++) {
				if (a[n] > a[n + 1]) {
					int temp = a[n];
					a[n] = a[n + 1];
					a[n + 1] = temp;
				}
			}
		}
		for (int i : a) {
			System.out.println(i);
		}
	}

}

 
複雑度分析:泡の順序付けは不安定な順序付けアルゴリズムであり、全部で比較しなければならない((n-1)+(n-2)+...+3+2+1)=n*(n−1)/2回なので,時間的複雑度はO(n^2)である.
 
クイックソート:
 

public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] initArray = { 1, 545, 23, 334, 876, 222, 111, 8, 9, 7, 6, 57, 89,
				0, -23, 670 };
		qsort(initArray, 0, initArray.length - 1);
		outprint(initArray);
	}

	public static void outprint(int[] initArray) {
		for (int i : initArray) {
			System.out.println(i);
		}
	}

	public static void swap(int[] array, int a, int b) {
		System.out.println("a=" + a);
		System.out.println("b=" + b);
		int temp = array[b];
		array[b] = array[a];
		array[a] = temp;
	}

	public static int getPivotIndex(int[] array, int begin, int end) {
		Random r = new Random();
		return begin + r.nextInt(end - begin + 1);
	}

	public static void qsort(int[] array, int begin, int end) {
		if (end > begin) {
			int index = getPivotIndex(array, begin, end);
			index = portions(array, begin, end, index);
			qsort(array, begin, index - 1);
			qsort(array, index + 1, end);
		}
	}

	public static int portions(int[] array, int begin, int end, int index) {
		int pivot = array[index];
		swap(array, index, end);
		for (int i = index = begin; i < end; i++) {
			if (array[i] < pivot) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		return index;
	}
} 

最悪の場合は泡立ちと同様に時間的複雑度はO(n^2)であり、n*lognが望ましい.
 
ソートの挿入:
 

public class InsertSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = { 77, 1, 65, 13, 81, 93, 10, 5, 23, 17 };
		isort(array, 0, array.length);
		outprint(array);
	}

	public static void outprint(int[] initArray) {
		for (int i : initArray) {
			System.out.println(i);
		}
	}

	public static void swap(int[] array, int a, int b) {
		int temp = array[b];
		array[b] = array[a];
		array[a] = temp;
	}

	public static void isort(int[] array, int begin, int end) {
		for (int i = begin; i < end; i++) {
			int temp = array[i];
			for (int m = i - 1; m >= 0; m--) {
				if (temp < array[m]) {
					array[m + 1] = array[m];
					array[m] = temp;
				} else {
					break;
				}
			}
		}
	}
}

一番いいのは、順番が並んでいるので、n-1回の比較をすればいいということです.最悪の場合、順番はちょうど逆順で、1+2+...+を比較します.n-1回.
平均時間の複雑さもO(n^2)である.