学步园

• 空间复杂度

由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量与递归调用的最大深度一致。最好情况是O(log2(n+1))；最坏情况是O(n)；平均情况是O(log2n)。

• 时间复杂度

快速排序的运行时间与划分是否对称有关。最坏的情况是划分为0和n-1，时间复杂度是O(n^2)。最好的情况是均分，时间复杂度是O(n*log2n)。平均情况与最好情况的运行时间很接近。

快速排序是内排序中平均性能最优的排序算法。

这里对快速排序的原理就不详细叙述了，这篇博客讲的非常好，点击打开链接。

• 代码实现

/**
 * 源码名称：QuickSort.java 
 * 日期：2014-08-12 
 * 程序功能：快速排序 
 * 版权：CopyRight@A2BGeek 
 * 作者：A2BGeek
 */
public class QuickSort {
	public void quickSort(int[] in, int head, int tail) {
		if (head >= tail) {
			return;
		} else {
			int povit = quickPass(in, head, tail);
			quickSort(in, head, povit - 1);
			quickSort(in, povit + 1, tail);
		}
	}
	/**
	 * 函 数 名：quickPass 
	 * 功能描述：单趟快速排序 
	 * 输入参数：
	 * @param in 待排序数组 
	 * @param head 起点索引
	 * @param tail 终点索引 
	 */
	public int quickPass(int[] in, int head, int tail) {
		int left = head;
		int right = tail;
		int tmp = in[left];
		while (left < right) {
			while (left < right && in[right] >= tmp) {
				right--;
			}
			if (left < right) {

				in[left] = in[right];
				left++;
			}
			while (left < right && in[left] <= tmp) {
				left++;
			}
			if (left < right) {
				in[right] = in[left];
				right--;
			}
		}
		in[left] = tmp;
		return left;
	}

	public static void main(String[] args) {
		int[] caseOne = { 6, 5, 4, 3, 2, 1, 10, 2 };
		int[] caseTwo = { 1, 6, 5, 2, 4, 3 };
		QuickSort mQuickSort = new QuickSort();
		mQuickSort.quickSort(caseOne, 0, caseOne.length - 1);
		for (int i : caseOne) {
			System.out.print(i + " ");
		}
		System.out.println();
		mQuickSort.quickSort(caseTwo, 0, caseTwo.length - 1);
		for (int i : caseTwo) {
			System.out.print(i + " ");
		}
	}
}