快速排序是一种交换排序，他是稳定的排序,时间复杂度是nlogn,因为每次partition需要n个时间,共分为logn次.所以整体时间复杂度是nlogn.
它的核心是：找到一个索引，把小于它的数值放在它的左边，大于它的放在右边.然后依次将左边的数组和右边的数组进行递归.
这个索引最好是一个中位值,保证左右两遍的长度差值不大,否则会导致整体时间复杂度变高.
Ps:左右两边进行交换的时候不能使用swap,这样会把mid值弄丢.因为为了避免出现相等情况的死循环,在遇到相等数值的情况下,会继续跳跃不能进行交换.
所以采用直接赋值的方案,这种方法可以实现解决这个问题.
至于为什么可以解决这个问题,可以用数学方法证明出来.(我还没有领会!!)
package Sort;
/**
* Created by Hammy on 2018/3/1.
*/
public class QuickSort
{
public QuickSort(){};
public static void sort(int[] array){
quickSort(array,0,array.length-1);
}
private static void quickSort(int[] array,int left,int right){
if(left >= right)
return;
int index = partition(array,left,right);
quickSort(array,left,index-1);
quickSort(array,index+1,right);
}
private static int partition(int[] array, int left, int right){
int mid = getMid(array, left, right);
int temp = array[mid];
while(left<right){
while(right>left&&array[right]>=temp)
right--;
array[left]=array[right];
while(left<right&&array[left]<=temp)
left++;
array[right]=array[left];
}
array[left]=temp;
return left;
}
public static int getMid(int[] array,int left,int right){
int mid = (left+right)>>1;
if(array[left]>array[right]){
Util.swap(array,left,right);
}
if(array[mid]>array[right]){
Util.swap(array,mid,right);
}
if(array[mid]>array[left]){
Util.swap(array,left,mid);
}
return left;
}
}
