上代码：
/** 快速排序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);elsebreak;}//把枢纽元和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]位置赋值 完成插入}}}
，美文、不要轻易用过去来衡量生活的幸与不幸！
