泛型实现的快速排序算法
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* 泛型实现的快速排序算法
*
* @version 1.0 2011-07-13 09:53
* @author 鬼辅神攻
*
*/
public class QuickSort {
public static void main(String[] args) {
Random rand = new Random();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 50; i++) {
list.add(rand.nextInt(100 + 1));
}
System.out.println(list.toString());
long begin = System.currentTimeMillis();
sort(list, 0, list.size() - 1);
long end = System.currentTimeMillis();
System.out.println("[cost time]:" + (end - begin));
for (int i = 0; i < list.size() - 1; i++) {
System.out.println(list.toString());
}
}
/**
* 分组算法
*
* @param <T>
* 实现了Comparable接口的类型
* @param list
* 输入的排序列表
* @param start
* 输入的排序列表中需要分组的下限
* @param end
* 输入的排序列表中需要分组的上限
* @return 分组的索引
*/
protected static <T extends Comparable<T>> int partition(List<T> list,
int start, int end) {
T keyValue = list.get(start);
while (true) {
int startOrg = start;
int endOrg = end;
// 左右各寻找不符合分组规则的数字，并交换位置。
while (!(list.get(end).compareTo(keyValue) < 0) && end > startOrg) {
end--;
}
while (!(list.get(start).compareTo(keyValue) >= 0)
&& start < endOrg) {
start++;
}
if (start < end) {
swap(list, start, end);
} else {
return end;
}
}
}
/**
* 交换两个位置的值
*
* @param <T>
* @param list
* 列表
* @param i
* @param j
*/
private static <T> void swap(List<T> list, int i, int j) {
T tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
}
/**
* 快速排序递归算法
*
* @param <T>
* 实现了Comparable接口
* @param list
* 待排序列表
* @param start
* 下标下限
* @param end
* 下标上限
*/
protected static <T extends Comparable<T>> void sort(List<T> list,
int start, int end) {
int splitKey = partition(list, start, end);
if (splitKey > start)
sort(list, start, splitKey);
if (splitKey + 1 < end)
sort(list, splitKey + 1, end);
}
/**
* 对用户友好的接口
*
* @param list
* 待排序列表
*/
public static void sort(List<Integer> list) {
sort(list, 0, list.size() - 1);
}
}
