Java排序算法之 —— 快速排序

package algorithm.sort;

/**
 * 快速排序：基于分治模式 分解： 划分为两个子数组（可能为空），A[left..mid-1]和A[mid+1..right]. 其中，前一个数组都小于等于A[mid],后一个数组都大于等于A[mid].mid下标在过程中划分得出。
 * 解决：递归调用快速排序，对两个子数组排序 合并：因为子数组已经是排好序，所以合并不需要操作即可得到排好序的数组
 * 
 * @author Administrator
 * 
 */
public class QuickSort {
	//对数组指定元素进行排序
	public void quickSort(int[] a, int from, int end) {
		if (from < end) {
			int mid = partition(a, from, end);
			quickSort(a, from, mid - 1);
			quickSort(a, mid + 1, end);
		}
	}
	
	//整个数组排序
	public void quickSort(int[] a) {
		quickSort(a, 0, a.length-1);
	}
	
	//快速排序的关键过程是对partition过程，对子数组重排
	public int partition(int[] a, int from, int end) {
		int i = from - 1;
		for (int j = from; j < end; j++) {
			if (a[j] <= a[end]) {	// 首先以最后一个元素作为中间分隔元素
				i++;
				exchange(a, i, j);
			}
		}
		i++;
		exchange(a, i, end);
		return i;
	}

	// 交换元素
	public void exchange(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// 打印数组
	public void printArr(String str, int[] a) {
		System.out.print(str + "\t");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}

	//测试数据
	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		int[] a = {2,5,78,56,43,9,23};
		qs.printArr("原始数组为：", a);
		qs.quickSort(a);
		qs.printArr("快速排序后：", a);
	}
}

//output~:
原始数组为： 2 5 78 56 43 9 23
快速排序后： 2 5 9 23 43 56 78