各種ソートアルゴリズムの実現
4548 ワード
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);
}
}