Java排序方法之：快速排序

package com.liany.demo.sort;

import java.util.Random;

/**
 * 参考wiki源码写了一遍，并加了注释和自己的理解。
 * 
 * 步骤：
 * 1、取一随机位置的元素作为基准（pivot,或叫枢纽）
 * 2、将基准移到最后位置(方便数组的其它元素与之比较)，将小于此基准的元素放到数组的前面，
         然后将基准移到所有比它小的元素的最大序号的下一个位置。
 * 3、将这个基准的新位置返回，并作为迭代的分割点。
 * 4、迭代比基准的前面、后面两个部分。
 * 
 * @author modiliany
 * @date: 2012-04-05
 */
public class MyQuickSort {

	private Random random = new Random();
	
	/**
	 * 交换
	 * @param array
	 */
	public void swap(int[] array, int i, int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	/**
	 * 查找枢纽的索引号
	 */
	public int getPivotIndex(int[] array, int begin, int end){
		int index = begin + random.nextInt(end-begin+1);
		int pivot = array[index];
		
		//把pivot换到最后
		swap(array, index, end);
		for(int i=index=begin; i < end; i++){
			if(array[i] < pivot){
				//index从0开始计算了，记录小于pivot的值
				//将小于pivot的值的元素移动到index位置
				swap(array, index++, i);
			}
		}
		swap(array, index, end);//将pivot放到所有比它小的元素的下一个位置(即此时的index位置)。
		
		return index;
	}
	
	/**
	 * 快速排序法（Divide and conquer）
	 * @param array 待排序的数据
	 * @param begin 开始序号
	 * @param end	最后一个元素的序号
	 */
	public void quickSort(int[] array, int begin, int end){
		if(end > begin){
			int index = getPivotIndex(array, begin, end);
			
			quickSort(array, begin, index-1);
			quickSort(array, index+1, end);
		}
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int [] array = {3, 1, 7, 5, 2, 9, 10, 4, 8, 6};
		
		MyQuickSort sort = new MyQuickSort();
		sort.quickSort(array, 0, array.length-1);
		
		//输出
		for(int val : array){
			System.out.println(val);
		}
		
	}

}

wiki:

http://zh.wikipedia.org/zh-cn/快速排序

这里为了简单和方便理解排序的原理，只用了int数组。对象要比较的话，可以自己实现Comparator接口。