quicksortimp.java

用JAVA实现排序等简单算法的演示

package algorithmImp;

public class QuickSortImp extends SortAlgorithmImp {

	public void sorting() {
		quickSort(0, data.length);
	}

	/**
	 * 对从 startIndex（包括） 到 endIndex（不包括）的数组元素进行排序
	 * @param startIndex 起始下标（排序时也排该下标的元素）
	 * @param endIndex 终止下标（排序时不排该下标的元素）
	 */
	protected void quickSort(int startIndex, int endIndex) {
		int nElement = endIndex - startIndex;
		// 只有一个元素时不用排序了
		if (nElement <= 1) return;
		if (nElement == 2) {
			// 两个元素直接进行排序
			// 如果 data[startIndex] > data[startIndex+1] 则交换这两个元素
			if (compare(startIndex, startIndex+1)) swap(startIndex, startIndex+1);
			return;
		}
		
		// 对要排序的部分进行划分，返回划分点的下标
		int index = partition(startIndex, endIndex);
		// 对划分的两部分进行排序
		quickSort(startIndex, index);
		quickSort(index+1, endIndex);
	}
	
	/**
	 * 以 startIndex 处的元素对 startIndex（包括） 到 endIndex（不包括）的数组元素进行划分，
	 * 使得找到的划分点（返回值 index）之前的元素都小于 startIndex 处元素，而划分点之后的元素
	 * 都大于它，并最后交换startIndex 处与划分点处的元素
	 * @param partIndex 
	 * @param startIndex 起始下标（排序时也排该下标的元素）
	 * @param endIndex 终止下标（排序时不排该下标的元素）
	 */
	protected int partition(int startIndex, int endIndex) {
		// 选中 startIndex 处的元素
		select(startIndex);
		int forward = startIndex + 1;
		int backward = endIndex - 1;
		while (forward < backward) {
			// 当选中的元素(原startIndex处元素）大于 forward 处元素时推进 forward
			while (forward < endIndex) {
				if (!compareSelectedWith(forward)) break;
				forward = forward + 1;
			}
			// 当选中的元素（原startIndex处元素）小于等于 backward 处元素时减少 backward
			while (startIndex < backward) {
				if (compareSelectedWith(backward)) break;
				backward = backward - 1;
			}
			
			if (forward < backward) {
				// 交换这两个位置的元素
				swap(forward, backward);
			}
		}
		
		// 如果选中的划分点不是选中的点 ，则进行交换
		if (getSelectedIndex() != backward) swapSelectedWith(backward);
		return backward;
	}

}