几种常见的排序算法

这里是以前写的算法总结了。照搬过来而已。

package SortSet;

import java.math.*;

public class SortSetTest {
	// 插入排序
	public static float[] InsertSort(float x[]) {
		float temp;
		int tag;
		for (int i = 0; i < x.length; i++) {
			temp = x[i];
			tag = i;
			while (tag > 0 && x[tag - 1] >= temp) {
				x[tag] = x[tag - 1];
				tag--;
			}
			x[tag] = temp;
		}
		return x;
	}

	// 冒泡排序
	public static float[] BubbleSort(float x[]) {
		for (int i = x.length - 1; i > 1; i--) {
			for (int j = 0; j < i; j++)
				if (x[j] > x[j + 1]) {
					float temp = x[j];
					x[j] = x[j + 1];
					x[j + 1] = temp;
				}
		}
		return x;
	}

	// 快速排序
	public static void QuickSort(float x[], int left, int right) {
		int i = left, j = right;
		float pivot, temp;

		pivot = x[(left + right) / 2];
		if (i < j) {
			do {
				while (x[i] <= pivot && i < right) {
					i++;
				}
				while (x[j] >= pivot && j > left) {
					j--;
				}
				if (i <= j) {
					temp = x[i];
					x[i] = x[j];
					x[j] = temp;
					i++;
					j--;
				}
			} while (i <= j);
		}

		if (j > left)
			QuickSort(x, left, j);
		if (i < right)
			QuickSort(x, i, right);
	}

	// shell排序
	public static void ShellSort(float[] x) {

		for (int i = x.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++)
				insertSort(x, j, i);
		}
		insertSort(x, 0, 1);
	}

	public static void insertSort(float[] x, int start, int incr) {
		float temp;
		for (int i = start + incr; i < x.length; i += incr) {
			for (int j = i; (j >= incr) && (x[j] < x[j - incr]); j -= incr) {
				temp = x[j];
				x[j] = x[j - incr];
				x[j - incr] = temp;
			}
		}
	}

	// 合并排序
	public static void mergeSort(float[] x, float[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;

		mergeSort(x, temp, l, mid);
		mergeSort(x, temp, mid + 1, r);
		for (int i = l; i < r + 1; i++) {
			temp[i] = x[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				x[cur] = temp[i2++];
			else if (i2 > r)
				x[cur] = temp[i1++];
			else if (temp[i1] <= temp[i2])
				x[cur] = temp[i1++];
			else
				x[cur] = temp[i2++];
		}
	}

	// 桶排序
	public static float[] BucketSort(float[] x) {
		float t;
		float temp[][] = new float[10][100000];
		for (int i = 0; i < 10; i++)
			for (int fx = 0; fx < 100000; fx++) {
				temp[i][fx] = -1;
			}
		int j[] = new int[10];
		int k;
		for (int p = 0; p < 10; p++)
			j[p] = 0;
		for (int i = 0; i < x.length; i++) { // 划分桶

			k = (int) Math.floor(x[i] * 10);
			temp[k][j[k]] = x[i];
			j[k]++;

		}

		for (int m = 0; m < 10; m++) { // 桶内插入排序
			for (int f = 0; f < temp[m].length; f++) {
				if (temp[m][f] == -1)
					break;
				t = temp[m][f];
				int tag = f;
				while (tag > 0 && temp[m][tag - 1] > t) {
					temp[m][tag] = temp[m][tag - 1];
					tag--;
				}
				temp[m][f] = t;
			}
		}

		int s = 0;
		for (int m = 0; m < 10; m++) { // 写回原数组
			for (int f = 0;; f++) {
				if (temp[m][f] == -1)
					break;
				x[s] = temp[m][f];
				s++;
			}
		}
		return x;
	}

	public static void main(String args[]) {
		float a[] = new float[100000];
		for (int i = 0; i < 100000; i++) {
			a[i] = (float) Math.random();

		}

		float a1[][] = new float[6][10], a2[][] = new float[6][1000], a3[][] = new float[6][10000], a4[][] = new float[6][100000];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 10; i++)
				a1[j][i] = a[i];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 1000; i++)
				a2[j][i] = a[i];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 10000; i++)
				a3[j][i] = a[i];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 100000; i++)
				a4[j][i] = a[i];

		// N=10;
		System.out.println("测试数值为10时，各个排序的结果如下（对同一数组）：");

		System.out.println("原数组，插入排序：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		InsertSort(a1[0]);
		System.out.println("排序后数组：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();

		System.out.println("原数组，冒泡排序：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		BubbleSort(a1[1]);
		System.out.println("排序后数组：");
		for (int pp = 0; pp < a1[1].length; pp++)
			System.out.print(a1[1][pp] + "  ");
		System.out.println();

		System.out.println("原数组，快速排序：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		QuickSort(a1[2], 0, a1[2].length - 1);
		System.out.println("排序后数组：");
		for (int pp = 0; pp < a1[2].length; pp++)
			System.out.print(a1[2][pp] + "  ");
		System.out.println();

		System.out.println("原数组，希尔排序：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		ShellSort(a1[3]);
		System.out.println("排序后数组：");
		for (int pp = 0; pp < a1[3].length; pp++)
			System.out.print(a1[3][pp] + "  ");
		System.out.println();

		System.out.println("原数组，合并排序：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		float[] temp1 = new float[10];
		mergeSort(a1[4], temp1, 0, a1[4].length - 1);
		System.out.println("排序后数组：");
		for (int pp = 0; pp < a1[4].length; pp++)
			System.out.print(a1[4][pp] + "  ");
		System.out.println();

		System.out.println("原数组，桶排序：");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		BucketSort(a1[5]);
		System.out.println("排序后数组：");
		for (int pp = 0; pp < a1[5].length; pp++)
			System.out.print(a1[5][pp] + "  ");
		System.out.println();

		// N=1000;
		long c = System.currentTimeMillis();
		InsertSort(a2[0]);
		long b1 = System.currentTimeMillis();
		System.out.println("N=1000插入排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		BubbleSort(a2[1]);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时冒泡排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		QuickSort(a2[2], 0, a2[2].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时快速排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		ShellSort(a2[3]);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时希尔排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		float[] temp2 = new float[1000];
		mergeSort(a2[4], temp2, 0, a2[4].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时合并排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		BucketSort(a2[5]);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时桶排序时间为：" + (b1 - c));

		// N=10000;
		c = System.currentTimeMillis();
		InsertSort(a3[0]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000插入排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		BubbleSort(a3[1]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时冒泡排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		QuickSort(a3[2], 0, a3[2].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时快速排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		ShellSort(a3[3]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时希尔排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		float[] temp3 = new float[10000];
		mergeSort(a3[4], temp3, 0, a3[4].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时合并排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		BucketSort(a3[5]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时桶排序时间为：" + (b1 - c));

		// N=100000;

		c = System.currentTimeMillis();
		InsertSort(a4[0]);
		b1 = System.currentTimeMillis();

		System.out.println("N=100000插入排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		BubbleSort(a4[1]);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时冒泡排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		QuickSort(a4[2], 0, a4[2].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时快速排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		ShellSort(a4[3]);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时希尔排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		float[] temp4 = new float[100000];
		mergeSort(a4[4], temp4, 0, a4[4].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时合并排序时间为：" + (b1 - c));

		c = System.currentTimeMillis();
		BucketSort(a4[5]);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时桶排序时间为：" + (b1 - c));

	}
}