快速排序List的通用方法

导读：
　　
　　
　　
　　
　　
　　/** *//**
　　
　　* 快速排序列表中的元素，List中的元素必须实现了Comparable接口
　　
　　
　　*
　　
　　
　　* @param list
　　
　　
　　* 列表
　　
　　
　　* @param fromIndex
　　
　　
　　* 左索引（排序开始索引）
　　
　　
　　* @param toIndex
　　
　　
　　* 右索引（排序结束结束索引）
　　
　　
　　* @throws Exception
　　
　　
　　*/
　　
　　public static void quickSortList(List<comparable> list, int fromIndex, int toIndex)
　　
　　
　　
　　
　　throws Exception ...{
　　
　　
　　int tempFromIndex = fromIndex; // 左索引
　　
　　int tempToIndex = toIndex; // 右索引
　　
　　Comparable midElement; // 分割元素
　　
　　Comparable tempElement; // 临时变量，存储所取的列表中的元素
　　
　　
　　
　　
　　
　　if (toIndex > fromIndex) ...{
　　
　　
　　
　　
　　
　　
　　/**//*
　　
　　* 取列表中间索引的值的对象作为分割元素
　　
　　
　　*/
　　
　　midElement = (Comparable) list.get((fromIndex + toIndex) / 2);
　　
　　
　　
　　
　　// 循环列表直到索引交叉
　　
　　
　　
　　while (tempFromIndex <= tempToIndex) ...{
　　
　　
　　
　　
　　/**//*
　　
　　* 从左索引方向开始找到第一个大于或等于分割元素的元素
　　
　　
　　*/
　　
　　
　　
　　while (tempFromIndex < toIndex) ...{
　　
　　
　　tempElement = (Comparable) list.get(tempFromIndex);
　　
　　
　　if (tempElement.compareTo(midElement) < 0)
　　
　　
　　++tempFromIndex;
　　
　　
　　else
　　
　　break
　　
　　}
　　
　　
　　
　　
　　
　　/**//*
　　
　　* 从右索引方向开始找到第一个小于或等于分割元素的的元素
　　
　　
　　*/
　　
　　
　　
　　while (tempToIndex > fromIndex) ...{
　　
　　
　　tempElement = (Comparable) list.get(tempToIndex);
　　
　　
　　if (tempElement.compareTo(midElement) > 0)
　　
　　
　　--tempToIndex;
　　
　　
　　else
　　
　　break
　　
　　}
　　
　　
　　
　　// 如果索引没有交叉则交换两个对象位置
　　
　　
　　
　　if (tempFromIndex <= tempToIndex) ...{
　　
　　
　　swap(list, tempFromIndex, tempToIndex);
　　
　　
　　
　　
　　++tempFromIndex;
　　
　　
　　--tempToIndex;
　　
　　
　　}
　　
　　}
　　
　　
　　
　　
　　
　　/**//*
　　
　　* 如果右索引没有到达左索引，则排序左边区域
　　
　　
　　*/
　　
　　if (fromIndex < tempToIndex)
　　
　　
　　quickSortList(list, fromIndex, tempToIndex);
　　
　　
　　
　　
　　
　　
　　/**//*
　　
　　*
　　
　　
　　* 如果左索引没有到达右索引，则排序右边区域
　　
　　
　　*/
　　
　　if (tempFromIndex < toIndex)
　　
　　
　　quickSortList(list, tempFromIndex, toIndex);
　　
　　
　　
　　
　　}
　　
　　}
　　
　　
　　
　　
　　
　　/** *//**
　　
　　* 交换列表中的两个位置的对象
　　
　　
　　*
　　
　　
　　* @param list
　　
　　
　　* 列表
　　
　　
　　* @param i
　　
　　
　　* 索引
　　
　　
　　* @param j
　　
　　
　　* 索引
　　
　　
　　*/
　　
　　
　　
　　private static void swap(List list, int i, int j) ...{
　　
　　
　　Object io = list.get(i);
　　
　　
　　Object jo = list.get(j);
　　
　　
　　
　　
　　list.remove(i);
　　
　　
　　list.add(i, jo);
　　
　　
　　
　　
　　
　　list.remove(j);
　　
　　
　　list.add(j, io);
　　
　　
　　}
　　Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1896685

本文转自
http://blog.csdn.net/mrshan/archive/2007/11/21/1896685.aspx