上代码：
/*
* 快速排序O(NlogN) 对C++和Java的基本类型特别有用 适用于大量输入 对少量比如20个输入时插入排序比较好
* 包含 找出枢纽元（也就是分割的关键字），分割数组，再递归的进行 这几个部分 注意虽然是递归但这都是在一个数组上直接操作
* 不断进行正向的调用
*/
//快速排序的驱动程序
public static <T extends Comparable<? super T>> void quickSort(T[] t)
{
quickSort(t,0,t.length-1);
}
/*
* 在进行正式的分割（分成比枢纽元大的部分和比枢纽元小的部分）之前 需要做一些准备工作就是找出枢纽元 并放在正确的位置（用三数中值分割法）
* 三数中值分割法中选取枢纽元最容易的方法是是t[left],t[right],t[center]三个数进行排序。这种方法有外的好处，三者最小的放在t[left]处，而这也是分割阶段应该放的位置。
* 三者最大的放在t[right]处，也是分割阶段应该放的位置，因为它大于枢纽元，因此我们可以把枢纽元放在t[right-1]处，并在分割阶段把i和j分别初始化为left+1和right-2因为他们不需要被进行分割检查
* 还有一个巨大的好处是，对于i j 因为走得太多而可能产生的数组越界的问题，因为他t[left]<枢纽元 所以如果j走到了left位置处 此时i一定>j 此时在quickSort排序判别中会因此而break,结束分割 所以起到一个警戒作用
* 同理对i也是 t[right]比枢纽元大，i碰到大的就要跳出while循环来尝试进行交换，而此时i一定>j 会直接进行下一步
*/
//因此这个函数的作用就是比较三者的大小 并防止在正确的位置上
private static <T extends Comparable<? super T>> T median3(T[] t,int left,int right)
{
int center=(left+right)/2;
if(t[center].compareTo(t[left])<0)//如果center位置数小 则交换把小的放到Left上
swapReferences(t,left,center);//注意swapReferences是final方法 可以明显提高运算速度
if(t[right].compareTo(t[left])<0)//如果right位置数小 则交换把小的放到Left上 此时left位置上的树是最小的
swapReferences(t,left,right);
if(t[right].compareTo(t[center])<0)//如果right位置数第二小 则交换把第二小的放到center上 不然center位置上数就是最小的
swapReferences(t,center,right);
swapReferences(t,center,right-1);
//返回枢纽元用于后面分割时进行比较
return t[right-1];
}
static final int CUTOFF=10;//CUTOFF用于区分要分割的数组的长度 长度比较小的用插入排序比较快 对于长度大的使用快速排序
//分割过程图见数据结构书P198 分割完之后 比i小的位置 都是小于枢纽元 反之都是大于枢纽元
private static <T extends Comparable<? super T>> void quickSort(T[] t,int left,int right)
{
if(left+CUTOFF<=right)
{
int i=left;
int j=right-1;
T pivot=median3(t,left,right);
for(;;)
{
while(t[++i].compareTo(pivot)<0){};//遇到比枢纽元更大的 i先跳出来 让j再走
while(t[--j].compareTo(pivot)>0){};//遇到比枢纽元更小的 j先跳出来 和i进行比较 如果i>j 也就是错位了 那么结束分割 否则交换之后继续各自+1 -1往前走
if(i<j)
swapReferences(t,i,j);
else
break;
}
//把枢纽元和i停下来的值交换 这个i停下来的值肯定是大于等于枢纽元的
swapReferences(t,right-1,i);
quickSort(t,left,i-1);
quickSort(t,i+1,right);
}
else
{
insertSort(t,left,right);
}
}
//重载插入排序
private static<T extends Comparable<? super T>> void insertSort(T[] t,int left,int right)
{
//因为最后插入值时候 需要在内部for循环的外面 所以j要在外部定义
int j;
for(int p=left+1;p<=right;p++)
{
T temp=t[p];
for(j=p;j>left && temp.compareTo(t[j-1])<0;j--)
t[j]=t[j-1];
t[j]=temp;//检测到j--之后j==0 或者t[j]>=t[j-1] 直接给t[j]位置赋值 完成插入
}
}
}原文：http://blog.csdn.net/u012411414/article/details/44651109