摘录自：java数据结构和算法。

毫无疑问，快速排序是最流行的排序，在大多数的情况下，快速排序都是最快的，时间为O(nlgn)。

快速排序本质上是通过把一个数组划分为两个子数组，然后递归的调用自身，为每一个子数组进行快速排序来实现的。

我们先通过划分来了解快速排序。划分是讨论快速排序的根本机制。划分数据就是通过特定项把数据分成两组，使所有的关键字大于特定项的在一组，使所有的关键字小于特定项的在一组。比如通过学生的成绩来划分，低于60分的为一组，高于60分的为一组，划分完后，两组里面的数据还是没有排序的，只是单纯的按照60分划分成了两组。

划分的算法由两个指针来进行工作的，两个指针分别指向数组的两头，左边的指针leftPtr往又移动，右边的指针rightPtr往左移动。当左边的指针leftPtr遇到比关键字大的数据时，停止移动；当右边的指针rightPtr遇到比关键字小的数据时，停止移动，然后交换这两个数据，当leftPtr>=rightPtr时候，表明执行结束，划分完成。

public class ArrayPar {
	private long[] theArray;
	private int nElems;

	public ArrayPar(int max) {
		theArray = new long[max];
		nElems = 0;

	}

	public void insert(long value) {
		theArray[nElems] = value;
		nElems++;
	}

	public int size() {
		return nElems;
	}

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

	public int partitionIt(int left, int right, long pivot) {
		int leftPtr = left;<span style="white-space:pre">	</span>
		int rightPtr = right ;
		while (true) {
			while (leftPtr < right && theArray[leftPtr] < pivot) //find bigger item
				leftPtr++;
			while (rightPtr > left && theArray[rightPtr] > pivot) // find smaller item
				rightPtr--;
			if (leftPtr >= rightPtr) {  //if point cross ,partition done
				break;
			} else {
				swap(leftPtr, rightPtr); 
			}
		}

		return leftPtr;    
	}

	/**
	 * @param leftPtr
	 * @param rightPtr
	 */
	private void swap(int leftPtr, int rightPtr) {
		long temp;
		temp = theArray[leftPtr];
		theArray[leftPtr] = theArray[rightPtr];
		theArray[rightPtr] = temp;
	}

}

划分的测试代码及结果：

public static void main(String[] args) {
		
		int max =16;
		ArrayPar a =new ArrayPar(max);
		
		for( int i =0 ; i <max; i++){
			long lo =(int) (Math.random()*199) ;
			a.insert(lo);
		}
		
		a.display();
		long pivot =99;     //以99进行划分
		int size = a.size();
		int partPtx =a .partitionIt(0, size-1, pivot);
		System.out.println("");
		a.display();
	}

打印结果：

A=  146 155 58 84 12 51 154 64 95 63 195 131 113 95 50 43         //原数组

A=  43 50 58 84 12 51 95 64 95 63
195 131 113 154 155 146      //按99进行划分后的数组

接下来，我们来了解快速排序

快速排序的三个基本步骤如下：

• 把数组或者子数组划分成左边（较小关键字）一组，和右边（较大关键字）一组
• 调用自身对左边一组进行排序
• 调用自身对右边一组进行排序

那么如何把枢纽移动到它的正确位置上呢， 我们可以把右边子数组的所有数据项往右移动一个位置，以腾出枢纽的位置，但是，这样不仅效率低而且没有必要。记住：尽管右边的子数组的全部数据均大于枢纽，但是子数组是无序的，所以可以在子数组内移动而对最终排序没有影响。因此，为了简化操作，只要交换右边子数组的最左端的数据项（目前是63）和枢纽 就可以了。如下图所示

代码中，我们用一个明显的语句为枢纽赋值，并把枢纽值传递给划分函数partitionIt中

快速排序的代码如下：

public void reQuickSort(int left , int right){
		if(right<= left ){
			return ;
		}else{
			long pivot =theArray[right];  //枢纽值，为最右侧的数据项
			int partition = partitionIt(left,right, pivot);  //划分
			reQuickSort(left,partition-1);   //sort left side
			reQuickSort(partition+1,right);  //sort right side
		}
	
	}

下面为快排的全部代码：

public class ArrayIns {
	private long[] theArray;
	private int nElems;

	public ArrayIns(int max) {
		theArray = new long[max];
		nElems = 0;

	}

	public void insert(long value) {
		theArray[nElems] = value;
		nElems++;
	}

	public int size() {
		return nElems;
	}

	public void display() {
		System.out.print("A= ");
		for (int i = 0; i < theArray.length; i++) {
			System.out.print(" " + theArray[i]);
		}
		System.out.println("");
	}
	
	public int partitionIt(int left, int right, long pivot) {
		int leftPtr = left-1;
		int rightPtr = right ;   //指向数组的最后一个位置，孤立出来
		while (true) {
			while (leftPtr < right && theArray[++leftPtr] < pivot) //find bigger item
				;
			while (rightPtr > left && theArray[--rightPtr] > pivot) // find smaller item
				;
			if (leftPtr >= rightPtr) {  //if point cross ,partition done
				break;
			} else {
				swap(leftPtr, rightPtr); 
			}
		}
		swap(leftPtr ,right );   //交换枢纽和右侧第一个的位置
		return leftPtr;    
	}
	
	private void swap(int leftPtr, int rightPtr) {
		long temp;
		temp = theArray[leftPtr];
		theArray[leftPtr] = theArray[rightPtr];
		theArray[rightPtr] = temp;
	}
	
	
	public void reQuickSort(int left , int right){
		if(right<= left ){
			return ;
		}else{
			long pivot =theArray[right];
			int partition = partitionIt(left,right, pivot);
			reQuickSort(left,partition-1);
			reQuickSort(partition+1,right);
		}
	
	}
	
	public static void main(String[] args) {
		int max =16;
		ArrayIns a =new ArrayIns(max);
		for( int i =0 ; i <max; i++){
			long lo =(int) (Math.random()*199) ;
			a.insert(lo);
		}
		a.display();
		a.reQuickSort(0,a.size()-1);
		a.display();
	}
	
}

测试结果：

A=  49 73 172 151 61 1 176 145 87 95 118 188 54 86 43 121
A=  1 43 49 54 61 73 86 87 95 118 121 145 151 172 176 188