双向扫描的思路是:头尾指针往中间扫描,从左找到大于主元的元素,从右找到小于等于主元的元素二者交换,继续扫描,直到左侧无大元素,右侧无小元素。
import java.util.Arrays;
import lanqiao.Swap;
public class 快排双向指针 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = new int[5];
Swap.ArryRandom(arr, 5);
System.out.println(Arrays.toString(arr));
quicksort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quicksort(int[] arr, int start, int end) {
if(start<end) {
int q = patitiion(arr,start,end);//找到主元数组下标
quicksort(arr,start,q-1);//对左边进行快排,
quicksort(arr,q+1,end);//对右边进行快排
}
}
//找主元
public static int patitiion(int[] arr,int start,int end) {
//主元初始化
int zhuyuan = arr[start];
//左指针
int left = start+1;
int right = end;//右指针
while(left<=right) {
//左侧大于主元就停下,特殊情况会越界
while(left<=right&&arr[left]<=zhuyuan) {
left++;
}
//右侧小于等于主元就停下
while(left<=right&&arr[right]>zhuyuan) {
right--;
}
if(left<right)
Swap.swap(arr, left, right);//停下后元素交换
}
Swap.swap(arr, start, right);
return right;
}
}