import org.junit.Test;
import java.util.Arrays;
/**
* Created by wc on 2018/4/28.
*/
public class 快速排序 {
@Test
public void test(){
int[] array={31,21,59,68,12,40};
sort(array,0,array.length-1);
System.out.print(Arrays.toString(array));
}
/**
* 数据量大用快排
* 必需是数组,链式结构不要使用快排
* 重复元素多,影响性能
* @param array
* @param start
* @param end
*/
public void sort(int[] array,int start,int end){
//如果起始大于结尾就返回
if(end-start<=0) return ;
int x=array[start];
int low=start;
int high=end;
boolean direction=true;
L:
while(low<high){
//从右往左
if(direction){
for(int i=high;i>low;i--){
if(array[i]<=x){
array[low++]=array[i];
high=i;
//换方向
direction=!direction;
continue L;
}
}
high=low;
}else{
for(int i=low;i<high;i++){
if(array[i]>=x){
array[high--]=array[i];
low=i;
direction=!direction;
continue L;
}
}
low=high;
}
}
array[low]=x;
sort(array,start,low-1);
sort(array,low+1,end);
}
}
网友评论