public class QuickSort {
/**
* 场景1
* 给定一个数组,确定一个数字N,小于N的数组放最左边,大于N的放最右边
*/
public static void splitNum(int[] array){
int cur = 0;
int lessIndex = 0;
int len = array.length;
while (cur < len) {
if(array[cur] <= array[len-1]) {
swap(array,cur,lessIndex++);
}
cur++;
}
}
/**
* 场景2
* 给定一个数组,确定一个数字N,小于N的数组放最左边,大于N的放最右边,等于的放中间
*/
public static void splitNum2(int[] array){
int cur = 0;
int lessIndex = -1;
int len = array.length;
int bigIndex = len - 1;
while (cur < bigIndex) {
if(array[cur] < array[len-1]) {
swap(array,cur++,++lessIndex);
} else if(array[cur] > array[len-1]){
swap(array,cur,--bigIndex); //这个不能交换后不能自增,因为交换过来的value还没进行判断
} else {
cur++;
}
}
swap(array,bigIndex,len-1);
}
/**
* 场景3
* 快速排序
* ans:递归实现
*/
public static void quickSort(int[] array){
if(array == null || array.length < 2) {
return;
}
process(array,0,array.length-1);
}
public static void process(int[] array,int left,int right){
if(left >= right) {
return;
}
//取最后一个数,遍历数组,如果数比这个值小,放区域最左边,比这个数大,放区域最右边
//相等的放中间,执行完成后返回相等值的左右边界坐标 (其实就相当于mid)
//然后划分左右两片分区 进行递归
int[] partition = partition(array, left, right);
//左边
process(array,left,partition[0]-1);
//右边
process(array,partition[1]+1,right);
}
public static int[] partition(int[] array,int left,int right){
int lessIndex = left - 1;
int bigIndex = right;
while (left < bigIndex) {
if(array[left] < array[right]) {
swap(array,left++,++lessIndex);
} else if(array[left] > array[right]){
swap(array,left,--bigIndex); //这个不能交换后不能自增,因为交换过来的value还没进行判断
} else {
left++;
}
}
swap(array,bigIndex,right);
return new int[]{lessIndex+1,bigIndex};
}
public static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 场景4
* 快速排序
* ans2:非递归实现
*/
public static void quickSortByStack(int[] array){
if(array == null || array.length < 2) {
return;
}
//把整个大数组的排序看成一个job
Job job = new Job(0,array.length-1);
Stack<Job> stack = new Stack<>();
stack.push(job);
while (!stack.isEmpty()) {
Job exeuteJob = stack.pop();
int[] partition = partition(array, exeuteJob.left, exeuteJob.right); //分区
if(partition[0] > exeuteJob.left) { //说明左边有值
stack.push(new Job(exeuteJob.left,partition[0]-1));
}
if(partition[1] < exeuteJob.right) { //右边有值
stack.push(new Job(partition[0]+1,exeuteJob.right));
}
}
}
public static class Job{
int left;
int right;
public Job(int left,int right){
this.left = left;
this.right = right;
}
}
public static void main(String[] args) {
//ArrayUtil.testArraySorted(100000,50,50,QuickSort.class,"quickSort");
ArrayUtil.testArraySorted(1000000,50,50,QuickSort.class,"quickSortByStack");
}
}
标签:right,int,partition,array,排序,快速,public,left
From: https://www.cnblogs.com/xinay/p/16848863.html