package Sort;
public class QuickSort {
/*
* 快排思路:找到1个基准值，然后进行一次(左右指针的判断)最后保证基准值左边都比基础值小，
* 基准值右边都比基准值大，然后在对左右两边继续递归重复这个过程
*/
public void display(int[] array){
for(int i=0;i<array.length;i++){
System.out.print(array[i]+"\t");
}
System.out.println();
}
public void quicksort(int[] array){
diguiSort(0,array.length-1,array);
}
public void diguiSort(int low,int high,int[] array){
if(low>=high){
return;
}else{
//标准值
int model = array[low];
int index = partion(model,low,high,array);
display(array);
//这里的index位置的数值已经是合适的位置，所以一下递归的方法上下限都相应-1或者+1
diguiSort(low,index-1,array);
diguiSort(index+1, high, array);
}
}
private int partion(int model, int low, int high,int[] array) {
//这里的边界条件是重点
while(low<high){
/* 注意注意！！！！这里array[high]>=model和下面的array[low]<=model的等号必须存在,为什么呢
* 因为最外面的while循环跳出的条件是low==high,如下例所示,有2个46，当最后递归，这个分区只有46两个元素,
* 这个时候high得不到--，low得不到++，low永远不等于high,我们在这里处于死循环
*/
while(low<high&&array[high]>=model){
high--;
}
swap(low,high,array);
while(low<high&&array[low]<=model){
low++;
}
swap(high,low,array);
}
return low;
}
private void swap(int high, int low, int[] array) {
int temp = array[high];
array[high] = array[low];
array[low] = temp;
}
public static void main(String[] args) {
QuickSort sort = new QuickSort();
int[] array = new int[]{456,784,49,2,37,46,123,53
,126,465,656,7689,45,23,89,46,237};
System.out.println("原始数组数据为");
sort.display(array);
sort.quicksort(array);
}
}
测试数据如下：
原始数组数据为
456 784 49 2 37 46 123 53 126 465 656 7689 45 23 89 46 237
237 46 49 2 37 46 123 53 126 89 23 45 456 7689 656 465 784
45 46 49 2 37 46 123 53 126 89 23 237 456 7689 656 465 784
23 37 2 45 49 46 123 53 126 89 46 237 456 7689 656 465 784
2 23 37 45 49 46 123 53 126 89 46 237 456 7689 656 465 784
2 23 37 45 46 46 49 53 126 89 123 237 456 7689 656 465 784
2 23 37 45 46 46 49 53 126 89 123 237 456 7689 656 465 784
2 23 37 45 46 46 49 53 126 89 123 237 456 7689 656 465 784
2 23 37 45 46 46 49 53 123 89 126 237 456 7689 656 465 784
2 23 37 45 46 46 49 53 89 123 126 237 456 7689 656 465 784
2 23 37 45 46 46 49 53 89 123 126 237 456 784 656 465 7689
2 23 37 45 46 46 49 53 89 123 126 237 456 465 656 784 7689
2 23 37 45 46 46 49 53 89 123 126 237 456 465 656 784 7689
