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接口。
?
?
?