详解Java中使用泛型实现快速排序算法的方法
快速排序算法概念
快速排序一般基于递归实现。其思路是这样的：
1.选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。
2.基于这个值，将数组分为两部分，较小的分在左边，较大的分在右边。
3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。
4.对两个子数组分别重复上述过程，直到每个数组只有一个元素。
5.排序完成。
基本实现方式：
publicstaticvoidquickSort(int[]arr){
qsort(arr,0,arr.length-1);
}
privatestaticvoidqsort(int[]arr,intlow,inthigh){
if(low<high){
intpivot=partition(arr,low,high);//将数组分为两部分
qsort(arr,low,pivot-1);//递归排序左子数组
qsort(arr,pivot+1,high);//递归排序右子数组
}
}
privatestaticintpartition(int[]arr,intlow,inthigh){
intpivot=arr[low];//枢轴记录
while(low<high){
while(low<high&&arr[high]>=pivot)--high;
arr[low]=arr[high];//交换比枢轴小的记录到左端
while(low<high&&arr[low]<=pivot)++low;
arr[high]=arr[low];//交换比枢轴小的记录到右端
}
//扫描完成，枢轴到位
arr[low]=pivot;
//返回的是枢轴的位置
returnlow;
}
使用泛型实现快排算法
下面设计一个QuickSort类，包含了静态函数sort()，可以对任意类型数组进行排序。如果为对象类型数组，则该对象类型必须实现Comparable接口，这样才能使用compareTo函数进行比较。
使用了最基本的快排算法，没有进行优化处理。
源代码如下：
importjava.util.LinkedList;
importjava.util.List;
importjava.util.ListIterator;
importjava.util.Random;
publicclassQuickSort{
@SuppressWarnings("unchecked")
//对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。
privatestaticvoidquickSort(Object[]in,intbegin,intend){
if(begin==end||begin==(end-1))return;
Objectp=in[begin];
inta=begin+1;
intb=a;
for(;b<end;b++){
//该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较
if(((Comparable<Object>)in[b]).compareTo(p)<0){
if(a==b){a++;continue;}
Objecttemp=in[a];
in[a]=in[b];
in[b]=temp;
a++;
}
}
in[begin]=in[a-1];
in[a-1]=p;
if(a-1>begin){
quickSort(in,begin,a);
}
if(end-1>a){
quickSort(in,a,end);
}
return;
}
//使用泛型，对任意对象数组排序，该对象类型数组必须实现Comparable接口
publicstatic<TextendsComparable<?superT>>voidsort(T[]input){
quickSort(input,0,input.length);
}
//添加对List对象进行排序的功能，参考了Java中的Java.util.Collections类的sort()函数
publicstatic<TextendsComparable<?superT>>voidsort(List<T>list){
Object[]t=list.toArray();//将列表转换为数组
quickSort(t,0,t.length);//对数组进行排序
//数组排序完成后再写回到列表中
ListIterator<T>i=list.listIterator();
for(intj=0;j<t.length;j++){
i.next();
i.set((T)t[j]);
}
}
//由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。
publicstaticvoidsort(int[]input){
Integer[]t=newInteger[input.length];
for(inti=0;i<input.length;i++){
t[i]=input[i];//封装
}
quickSort(t,0,t.length);//排序
for(inti=0;i<input.length;i++){
input[i]=t[i];//解封装
}
}
//double[]数组的重载函数
publicstaticvoidsort(double[]input){
Double[]t=newDouble[input.length];
for(inti=0;i<input.length;i++){
t[i]=input[i];
}
quickSort(t,0,t.length);
for(inti=0;i<input.length;i++){
input[i]=t[i];
}
}
//byte[]数组的重载函数
publicstaticvoidsort(byte[]input){
Byte[]t=newByte[input.length];
for(inti=0;i<input.length;i++){
t[i]=input[i];
}
quickSort(t,0,t.length);
for(inti=0;i<input.length;i++){
input[i]=t[i];
}
}
//short[]数组的重载函数
publicstaticvoidsort(short[]input){
Short[]t=newShort[input.length];
for(inti=0;i<input.length;i++){
t[i]=input[i];
}
quickSort(t,0,t.length);
for(inti=0;i<input.length;i++){
input[i]=t[i];
}
}
//char[]数组的重载函数
publicstaticvoidsort(char[]input){
Character[]t=newCharacter[input.length];
for(inti=0;i<input.length;i++){
t[i]=input[i];
}
quickSort(t,0,t.length);
for(inti=0;i<input.length;i++){
input[i]=t[i];
}
}
//float[]数组的重载函数
publicstaticvoidsort(float[]input){
Float[]t=newFloat[input.length];
for(inti=0;i<input.length;i++){
t[i]=input[i];
}
quickSort(t,0,t.length);
for(inti=0;i<input.length;i++){
input[i]=t[i];
}
}
//测试用的main函数
publicstaticvoidmain(String[]args){
//生产一个随机数组成的int[]数组，用来测试
intLEN=10;
int[]input=newint[LEN];
Randomr=newRandom();
System.out.print("int[]beforesorting:");
for(inti=0;i<input.length;i++){
input[i]=r.nextInt(10*LEN);
System.out.print(input[i]+"");
}
System.out.println();
System.out.print("int[]aftersorting:");
sort(input);
for(inti:input){
System.out.print(i+"");
}
System.out.println();
//生成一个字符串数组，用来测试
String[]s=newString[]{"b","a","e","d","f","c"};
System.out.print("String[]beforesorting:");
for(inti=0;i<s.length;i++){
System.out.print(s[i]+"");
}
System.out.println();
System.out.print("String[]aftersorting:");
sort(s);
for(inti=0;i<s.length;i++){
System.out.print(s[i]+"");
}
System.out.println();
//生成一个字符串列表，用来测试
List<String>l=newLinkedList<String>();
s=newString[]{"b","a","e","d","f","c"};
System.out.print("LinkedList<String>beforesorting:");
for(intj=0;j<s.length;j++){
l.add(s[j]);
System.out.print(s[j]+"");
}
System.out.println();
sort(l);
System.out.print("LinkedList<String>aftersorting:");
for(Stringts:l){
System.out.print(ts+"");
}
System.out.println();
}
}
运行main函数测试，从输出可以看出QuickSort类工作正常：
int[]beforesorting:654892263859211645 int[]aftersorting:381621264548596592 String[]beforesorting:baedfc String[]aftersorting:abcdef LinkedList<String>beforesorting:baedfc LinkedList<String>aftersorting:abcdef