各種ソートアルゴリズムの実現


package com.arithmetic;

import java.util.Random;

public class SortAlgorithm {
	public static void bubbleSort(int[] list) {
		long startTime = System.currentTimeMillis();
		int temp;
		for (int i = 0; i < list.length - 1; i++) {
			for (int j = 0; j < list.length - 1 - i; j++) {
				if (list[j] > list[j + 1]) {
					temp = list[j];
					list[j] = list[j + 1];
					list[j + 1] = temp;
				}
			}
		}
		System.out.println("bubbleSort total cost time: "
				+ (System.currentTimeMillis() - startTime));
	}

	public static void selectionSort(int[] list) {
		long startTime = System.currentTimeMillis();
		int temp;
		for (int i = 0; i < list.length - 1; i++) {
			for (int j = i; j < list.length; j++) {
				if (list[i] > list[j]) {
					temp = list[i];
					list[i] = list[j];
					list[j] = temp;
				}
			}
		}

		System.out.println("selectionSort total cost time: "
				+ (System.currentTimeMillis() - startTime));
	}

	public static void insertSort(int[] list) {
		long startTime = System.currentTimeMillis();
		int temp, j;
		for (int i = 1; i < list.length; i++) {
			j = i;
			while (j >= 1 && list[j] < list[j - 1]) {
				temp = list[j];
				list[j] = list[j - 1];
				list[j - 1] = temp;
				j--;
			}
		}
		System.out.println("insertSort total cost time: "
				+ (System.currentTimeMillis() - startTime));
	}

	public static void quickSort(int[] list) {
		long startTime = System.currentTimeMillis();

		qSort(list, 0, list.length - 1);

		System.out.println("quickSort total cost time: "
				+ (System.currentTimeMillis() - startTime));
	}

	private static void qSort(int[] list, int low, int high) {
		if (low < high) {
			int pivotloc = partition(list, low, high);
			qSort(list, low, pivotloc - 1);
			qSort(list, pivotloc + 1, high);
		}
	}

	private static int partition(int[] list, int low, int high) {
		int key = list[low];
		while (low < high) {
			while (low < high && list[high] >= key)
				high--;
			list[low] = list[high];
			while (high > low && list[low] <= key)
				low++;
			list[high] = list[low];
		}
		list[low] = key;
		return low;
	}

	public static void heapSort(int[] list) {
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < list.length; i++) {
			int key = chooseMinAt(list, i);
			int temp = list[i];
			list[i] = list[key];
			list[key] = temp;
		}

		System.out.println("heapSort total cost time: "
				+ (System.currentTimeMillis() - startTime));
	}

	private static int chooseMinAt(int[] list, int beginAt) {
		int temp = list[beginAt];
		int key = beginAt;
		for (int i = beginAt; i < list.length; i++) {
			if (temp > list[i]) {
				key = i;
			}
		}
		return key;
	}

	public static int[] randomList(int length) {
		if (length < 0) {
			return null;
		}
		int[] list = new int[length];
		Random ran = new Random();
		for (int i = 0; i < length; i++) {
			list[i] = ran.nextInt(length);
		}

		return list;
	}

	public static void print(int[] list) {
		System.out.println("~~~~~~~~~~start~~~~~~~~~~~~");
		for (int i : list) {
			System.out.println(i);
		}
		System.out.println("~~~~~~~~~~end~~~~~~~~~~~~");
	}

	public static void main(String[] args) {
		int[] ran = randomList(7245);//quickSort's high-point
		int[] bubbleSort = ran;
		int[] selectionSort = ran;
		int[] insertSort = ran;
		int[] quickSort = ran;
		int[] heapSort = ran;
		// print(ran);
		bubbleSort(bubbleSort);
		// print(dimidiationSort);

		selectionSort(selectionSort);
		// print(selectionSort);

		insertSort(insertSort);
		// print(insertSort);

		quickSort(quickSort);
		// print(quickSort);

		heapSort(heapSort);
		// print(heapSort);

	}

}