哎 边界有点绕呢
package 算法;
public class 快速排序 {
public static void quickSort(int[] arr) {
if (arr == null||arr.length==1) {
return;
}
proscss(arr,0,arr.length-1);
}
/**
* 快速排序
* @param arr
* @param l
* @param r
*/
public static void proscss(int[] arr,int l ,int r){
//跳出机制
if (l >= r) {
return;
}
//排序当前 分为 小于 等于 大与 并返回对应下标志
int a[] = sort1(arr,l,r);
//递归继续排序小于
proscss(arr,l,a[0]);
//递归继续排序大与
proscss(arr,a[1],r);
}
/**
* 具体的拆分,实现 按照R为标杆,p1左边是小数 p1-p2中间是相等数 p2-r是大与的数
* @param arr
* @param l
* @param r
* @return
*/
private static int[] sort1(int[] arr, int l, int r) {
System.out.println("l="+l+"r="+r);
//跳出
if(l>=r){
return new int[]{l,r};
}
//如果是2个就直接排序
if(r-l==1){
if (arr[l] > arr[r]) {
swap(arr,l,r);
}
return new int[]{l,r};
}
int p1 = l;
int p2 = r-1;//这里从r-1开始算 r作为中间数
int i = l;
//i 是判断的,直到p2 p2 右边是大与R的数 是已经判断交换过的
while (i<=p2){
//如果i大与于r 就放到大与于堆里
if (arr[i]>arr[r] ){
//i与 p2 交换 p2 --
swap(arr,i,p2);
p2--;
continue;
}
//如果i小于r 放到小于的堆里
if (arr[i]<arr[r] ){
//交换第i个与p1 p1++
swap(arr,i,p1);
p1++;
i++;
continue;
}
//如果i等于r 就放到等于堆里
if (arr[i]==arr[r] ){
i++;
continue;
}
}
//将r放到中间
swap(arr,p2+1,r);
p2++;
int[] rt = new int[2];
rt[0]=p1-1;
rt[1]=p2+1;
return rt;
}
public static void swap(int[] arr,int i,int j){
if ( i== j) {
return;
}
System.out.println("i="+i+"j="+j);
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
public static void main(String[] args) {
int[] arr = new int[]{1,6,5,2,7,5,3,8,4,5};
quickSort(arr);
System.out.println(arr.toString());
}
}