java数据结构之简单排序

列出三个最简单的排序方法：
1，冒泡排序；2，选择排序；3，插入排序
这里的排序针对都是简单类型的数组进行排序，他们的比较次数都为O(n^2)，但是相对来说，插入排序的交换次数是最少的，大概为冒泡排序的一半，其选择排序所用的交换次数也要少。这三个排序都是稳定的排序算法。

1，冒泡排序：
执行该程序，对于1000000个元素的数组排序，其算法所需时间大概为212ms

package pku.ss.datastructure.Sort;

public class BubbleSort {
	public static void main(String[] args) {
		int max = 1000000;
		ArrayBubble arr = new ArrayBubble(max);

		long startTime = System.currentTimeMillis();
		for (int j = 0; j < max; j++) {
			double element = (double) (java.lang.Math.random() * (max - 1));
			arr.insert(element);
		}
		long endTime = System.currentTimeMillis();

		System.out.println("Sort time: " + (endTime - startTime) + " ms");

	}
}

class ArrayBubble {
	private int nElement;
	private double[] array;

	ArrayBubble(int max) {
		array = new double[max];
		nElement = 0;
	}

	public void insert(double x) {
		// if (array.length == 10) {
		// System.out.println("[ERROR]Out of memory!");
		// System.out.println("[INFO]Atempt to insert into a full array");
		// System.exit(0);
		// } else {
		array[nElement] = x;
		nElement++;
		// }
	}

	public void display() {
		for (int i = 0; i < nElement; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
		System.out.println();
	}

	public void bubbleSort() {
		int outer;
		for (outer = nElement - 1; outer > 0; outer--)
			for (int j = 0; j < outer; j++) {
				if (array[j] > array[j + 1]) {
					swap(j, j + 1);
				}
			}
	}

	private void swap(int x, int y) {
		double temp;
		temp = array[x];
		array[x] = array[y];
		array[y] = temp;
	}
}

2，选择排序
执行该程序，对于1000000个元素的数组排序，其算法所需时间大概为216ms

package pku.ss.datastructure.Sort;

public class SelectSort {
	public static void main(String[] args) {
		int max = 1000000;
		ArraySel arr = new ArraySel(max);

		long startTime = System.currentTimeMillis();
		for (int j = 0; j < max; j++) {
			double element = (double) (java.lang.Math.random() * (max - 1));
			arr.insert(element);
		}
		long endTime = System.currentTimeMillis();

		System.out.println("Sort time: " + (endTime - startTime) + " ms");
	}
}

/** ***************************************** */
class ArraySel {
	private double[] a;
	private int nElement;
	//--------------------------------------------------------
	public ArraySel(int max) {
		a = new double[max];
		nElement = 0;
	}
	//--------------------------------------------------------
	public void insert(double element) {
		a[nElement] = element;
		nElement++;
	}
	//--------------------------------------------------------
	public void display() {
		for (int i = 0; i < nElement; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	//--------------------------------------------------------
	public void selectSort() {
		int out, in, min;
		for (out = 0; out < nElement - 1; out++) {
			min = out;
			for (in = out + 1; in < nElement; in++) {
				if (a[in] < a[min]) {
					min = in;
				}
			}
			if(min!=out)
				swap(min, out);
		}
	}
	//--------------------------------------------------------
	private void swap(int x, int y) {
		double temp;
		temp = a[x];
		a[x] = a[y];
		a[y] = temp;
	}
}

3，插入排序
执行该程序，对于1000000个元素的数组排序，其算法所需时间大概为214ms

package pku.ss.datastructure.Sort;

public class InsertionSort {
	public static void main(String[] args) {
		int max = 1000000;
		ArrayIns arr = new ArrayIns(max);

		long startTime = System.currentTimeMillis();
		for (int j = 0; j < max; j++) {
			double element = (double) (java.lang.Math.random() * (max - 1));
			arr.insert(element);
		}
		long endTime = System.currentTimeMillis();

		System.out.println("Sort time: " + (endTime - startTime) + " ms");
	}
}

class ArrayIns {
	private double[] a;
	private int nElement;

	// --------------------------------------------------------
	public ArrayIns(int max) {
		a = new double[max];
		nElement = 0;
	}

	// --------------------------------------------------------
	public void insert(double element) {
		a[nElement] = element;
		nElement++;
	}

	// --------------------------------------------------------
	public void display() {
		for (int i = 0; i < nElement; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}

	// --------------------------------------------------------
	public void insertionSort() {
		int out, in;
		for (out = 1; out < nElement; out++) {
			double temp = a[out];
			in = out;
			while (in > 0 && a[in - 1] >= temp) {
				a[in] = a[in - 1];
				in--;
			}
			a[in] = temp;
		}
	}
	// --------------------------------------------------------

}

评论

1 楼 Emy 2008-05-05  

数据结构很有用。。学习了~~~