排序算法

2008-03-14

/**
	 * 选择排序 总比较次数：n*(n-1)/2 不稳定排序
	 * 
	 * @param e
	 */
	public void chooseSort(int[] e) {
		int t;
		for (int i = 0; i < e.length - 1; i++) {
			for (int j = i + 1; j < e.length; j++) {
				if (e[i] > e[j]) {
					t = e[i];
					e[i] = e[j];
					e[j] = t;
				}
			}
		}
	}

	/**
	 * 直接插入排序 最少比较次数：n-1 ，最多比较次数：n*(n-1)/2 特点：原表顺序好排序效率高 稳定排序
	 * 
	 * @param e
	 */
	public void insertSort(int[] e) {
		int j, t;
		for (int i = 1; i < e.length; i++) {
			for (t = e[i], j = i - 1; j >= 0 && t < e[j]; j--)// 依次后移
			{
				e[j + 1] = e[j];
			}
			e[j + 1] = t;// 插入
		}
	}

	/**
	 * 冒泡排序 最多比较次数：n*(n-1)/2 稳定排序
	 * 
	 * @param e
	 */
	public void bubbleSort(int[] e) {
		int t;
		for (int i = 0; i < e.length - 1; i++) {
			for (int j = 0; j < e.length - i - 1; j++) {
				if (e[j] > e[j + 1]) {
					t = e[j];
					e[j] = e[j + 1];
					e[j + 1] = t;
				}
			}
		}
	}

	/**
	 * 希尔排序 对直接插入排序的改进
	 * 
	 * @param e
	 */
	public void shellSort(int[] e) {
		int j, y;
		for (int h = e.length / 2; h > 0; h = h / 2) {
			for (int i = h; i < e.length; i++) {
				y = e[i];
				for (j = i - h; j >= 0 && y < e[j]; j -= h) {
					e[j + h] = e[j];
				}
				e[j + h] = y;
			}
		}
	}

	/**
	 * 快速排序 对冒泡排序的改进
	 * 
	 * @param e
	 * @param low
	 * @param high
	 */
	public void quickSort(int[] e, int low, int high) {
		if (low < high) {
			int i = low, j = high, t = e[low];
			while (i < j) {
				// 在右子序列中找到比中间结点键值小或相等的结点，记录该结点下标于j
				while (i < j && e[j] > t) {
					j--;
				}
				// 将该结点复制到左子序列
				if (i < j) {
					e[i++] = e[j];
				}
				// 在左子序列中找到比中间结点键值大的结点，记录该结点下标于i
				while (i < j && e[i] <= t) {
					i++;
				}
				// 将该结点复制到右子序列
				if (i < j) {
					e[j--] = e[i];
				}
			}
			e[i] = t;// 设置中间结点
			quickSort(e, low, i - 1);// 划分左子序列
			quickSort(e, i + 1, high);// 划分右子序列
		}
	}