<>内部並べ替えのJava実装

1.並べ替えの挿入
アルゴリズムの説明:
左から列を大きくして、右の数字を左の列の数字の中に挿入します.左より大きくて、右の列より小さいです.
安定性:
安定している
比較回数:
n(n-1)/2
適用の場合:
ノードの個数が少ない場合に適用します.
 

package com.sam;

public class InsertionSort {

	public static void insertSort(int[] a, int n) {
		int i, j;
		int t;
		for (i = 1; i < n; i++) {
			printArray(a);
			t = a[i];
			for (j = i - 1; j >= 0 && t < a[j]; j--)
				a[j + 1] = a[j];
			a[j + 1] = t;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 46, 26, 22, 68, 48, 42, 36, 84, 66 };
		int n = 9;
		insertSort(a, n);
		printArray(a);
	}

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

 
2.並べ替えの選択
アルゴリズムの説明:
列を右に縮小し、すべての数の中で一番小さいのを探して一番左に並べます.
安定性:
不安定です
比較回数:
n(n-1)/2
適用の場合:
ノードの個数が少ない場合に適用します.

package com.sam;

public class SelectionSort {

	public static void selectionSort(int[] a, int n) {
		int i, j, k;
		int t;
		for (i = 0; i < n - 1; i++) {
			printArray(a);			
			k = i;
			for (j = i + 1; j < n; j++)
				if (a[k] > a[j])
					k = j;
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 46, 26, 22, 68, 48, 42, 36, 84, 66 };
		int n = 9;
		selectionSort(a, n);
		printArray(a);
	}

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

 
3.発泡体の並べ替え
アルゴリズムの説明:
上から下へ、大きな数は下へ沈んで、小数は上へ上がって、一回並んで、最大数は一番下に沈む.
安定性:
安定している
比較回数:
n(n-1)/2
適用の場合:

package com.sam;

public class BubbleSort {

	public static void bubbleSort(int[] a, int n) {
		int i, j, k;
		n--;
		while (n > 0) {
			j = 0;

			for (i = 0; i < n; i++) {
				if (a[i] > a[i + 1]) {
					k = a[i + 1];
					a[i + 1] = a[i];
					a[i] = k;
					j = i;
				}

			}
			printArray(a);
			n = j;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 46, 26, 22, 68, 48, 42, 36, 84, 66 };
		int n = a.length;
		bubbleSort(a, n);

	}

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

 
4.快速並べ替え
アルゴリズムの説明:
最初と最後の比は、それより小さい数を見つけて、忙しくないです.左から大きな数を見つけて、小さい時から大きい時まで、三つのノードを並べ替えて、また再帰します.
安定性:
不安定です
比較回数:
1.4 nlog 2 n
適用の場合:
撮影順序のノードに対して実行効率が最悪です.

package com.sam;

public class QuickSort {

	public static void quick(int[] a, int low, int up) {
		int i, j, t;
		if (low < up) {
			i = low;
			j = up;
			t = a[low];
			while (i != j) {
				while (i < j && a[j] > t)
					j--;
				if (i < j)
					a[i++] = a[j];
				while (i < j && a[i] <= t)
					i++;
				if (i < j)
					a[j--] = a[i];
			}
			a[i] = t;
			printArray(a);
			quick(a, low, i - 1);
			quick(a, i + 1, up);
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 46, 26, 22, 68, 48, 42, 36, 84, 66 };
		int n = a.length;
		quick(a, 0, 8);

	}

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

 
 
行を保持