快速排序
快速排序与归并排序一样，也是一种分治的排序算法。与归并排序不同的是，归并排序是先使得局部有序从而整体有序，快速排序首先是整体（切分元素的位置已经确定）有序再去关心局部有序。 快速排序的主要工作都在切分这一过程中。确定一个切分元素，然后从左往右遍历找到一个比切分元素大的元素，同时从右向左遍历找到一个比切分元素小的元素，将两个数进行交换。一旦从左向右移动的坐标与从右向左移动的坐标相遇，就把切分元素放到两组数中间从而使得切分元素左边的元素不大于切分元素，切分元素右边的元素不小于切分元素。然后在切分元素左右分别递归调用切分的过程，就是整个快速排序的过程。
public class Quick {
public static int temp;
public static void sort(int[] array){
sort(array,0,array.length-1);
}
public static void sort(int[] array,int lo,int hi){
if (lo>=hi)return;
int k = partition(array,lo,hi);
sort(array,lo,k-1);
sort(array,k+1,hi);
}
public static int partition(int[] array,int lo,int hi){
int i = lo;
int j = hi+1;
while (true){
while (array[++i]<array[lo])if (i==hi)break;//从左开始找比切分元素大的元素，找到就往下进行
while (array[--j]>array[lo])if (j==lo)break;//从右开始找比切分元素小的元素，找到就往下进行
if (i>=j)break;//退出while(true)的条件
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
temp = array[lo];
array[lo] = array[j];
array[j]=temp;
return j;
}
}partition函数完成的就是切分的过程，返回值就是切分元素的下标，它左边的元素不大于他，右边的元素不小于它。while(true)里边前两个while一个是从左寻找大于切分元素的元素，另一个是从右寻找小于切分元素的元素，找到之后，就进行交换。退出这个while(true)的条件就是那三个break前面的语句。向右找到了最右边，向左找到了最左边或者两个指针相遇和错过都预示着这次查找结束，然后退出循环。 快速排序最大的特点就是它是原地排序的，并且长度为N的数组进行排序所需的时间和NlogN成正比。缺点是它是一个不稳定的排序算法，如果对稳定性要求颇高快速排序就不适用了。 其实，快速排序的性能跟数据的输入也有很大的关系，设想一下，如果切分元素总是落在了剩下元素中最大或最小元素的身上（比如序列已经完全有序），那么快速排序的时间复杂度将成为n方；而且如果其中重复元素特别多的情况下，对元素就会进行许多次无谓的交换。于是我们还需要对基础的快速排序算法进行一个改进。 我们上边代码中对切分元素的选择比较简单，就是选择需要排序数组的第一个元素，为了使得这个元素不是最大元素也不是最小元素，足够随机，我们可以采用一些方法，比如随机取三个数，取三个数的中位数等等，主要就是为了使得切分元素切分出的两个子序列长短不要太过失衡，减小对性能的影响。再有就是重复元素这个问题，我们刚才的算法，在排序的过程中其实把需要排序的数组分成了三个部分，小于切分元素的部分，大于切分元素的部分，两个部分中间夹着的部分就是未与切分元素进行比较的部分。如下图所示
如果存在较多与切分元素相等的元素，我们就会进行一些无谓的比较交换，于是我们可以在这下点功夫。我们可以将数组分为四个部分，小于切分元素的部分，等于切分元素的部分，未排序的部分，大于切分元素的部分，这种改进之后的算法被称为——三项切分的快速排序。如下图以及代码所示
public class Quick3way {
public static int temp;
public static void sort(int[] array){
sort(array,0,array.length-1);
}
private static void sort(int[] array, int lo, int hi) {
if (lo>=hi)return;
int lt=lo,i=lo+1,gt=hi;
int lonum = array[lo];//array[Lo]会发生变化，需要记录下来,对比时候用
while (i<=gt){
if (array[i]<lonum){
temp = array[i];
array[i] = array[lt];
array[lt]=temp;
i++;lt++;
}else if(array[i]>lonum){
temp = array[i];
array[i] = array[gt];
array[gt] = temp;
gt--;
}else {
i++;
}
}
sort(array,lo,lt-1);
sort(array,gt+1,hi);
}
}while循环最终确定了lt和gt两个数，其实lt就是与等于切分元素这个区域的其实下标，gt就是这个区域的结束下标。lt之前的元素不大于切分元素，gt后边的元素不小于切分元素。在重复元素特别多的数组中，三向切分排序可以将他的运行时间从线性对数级别降低到线性级别。这真是个巨大的突破，虽然对于我们来说从打开文章到发现这个解决方案只花了几分钟甚至几十秒，但重复元素对性能的影响曾经被忽略了数十年，发现并改良这个算法是激动人心的。