快速排序详解-java实现

一、快速排序

整体过程：
1.先从数组中找一个数作为基准数，
2 进行分区，分区时大于这个数得全部放到右边，小于这个数得全部放到左边，等于这个数得全部放到中间（核心过程）
3再通过递归再更小得范围执行2步骤，直到递归到只有一个数

思路解析
比如针对 3 4 2 1 5 6 0 3
它的一个思路是首先有一个左边区域和右边区域，

左边区域的最靠右的起始下标为-1，右边区域的最靠左的起始下标为length-1

然后以数组最后一个数3为界限，大于这个数的都在右边，小于这个数的都在左边

首先排的时候index 为0，然后判断下标为0的数3 ==3，所以左右边界不动，index继续++
当index为1，判断下标为1的数4 4>3 ,所以右边界往右移动一位到length-2 值为0 将值为0与值为4调换位置 ======> 3 0 2 1 5 6 4 3
然后继续判断index为1 此时值为 0 0<3 所以左边界加1到0，值为3，将3与0调换位置，然后index+1 到2 ======> 0 3 2 1 5 6 4 3

当index为2时，判断下标为2的数 2<3, 所以左边界加1到1, 值为3 将 3与2
调换位置，然后index+1 到3 ======> 0 2 3 1 5 6 4 3
当index为3时，判断下标为3的数 1<3, 所以左边界加1到2 值为3 将3与1调换位置 然后index+1 到4 ======> 0 2 1 3 5 6 4 3

当index为4时，判断下标为4的数 5>3, 所以右边界往右移动一位到length-3 值为6，将值为6与值5调换位置 ======> 0 2 1 3 6 5 4 3
当index为4时，判断下标为4的数 6>3, 所以右边界往后移动一位到length-4----即下标为4，但是此这样就不满足index<右边界 所以跳出来
跳出来后将index为4的值和数组的最后一个值做交换 ===》 0 2 1 3 3 5 4 6
即结束

代码实现

public static void quickSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int[] equalE = partition(arr, L, R);
    process(arr, L, equalE[0] - 1);
    process(arr, equalE[1] + 1, R);
}

// arr[L...R]范围上，拿arr[R]做划分值，
// L....R < = >
public static int[] partition(int[] arr, int L, int R) {
    int lessR = L - 1;
    int moreL = R;
    int index = L;
    while (index < moreL) {
        if (arr[index] < arr[R]) {
            lessR++;
            swap(arr, lessR, index);
            index++;
        } else if (arr[index] > arr[R]) {
            moreL--;
            swap(arr, moreL, index);
        } else {
            index++;
        }
    }
    swap(arr, moreL, R);
    //比如342555578 //返回3，6
    return new int[] { lessR + 1, moreL };  
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

但是我们现在实现的代码整体时间复杂度为O（n^2); ->因为当数据为[0,1,2,3,4,5]==>这种情况时间复杂度是O(N^2)
所以其实是可以进行优化处理的
如何优化呢？即随机选择了一个划分值放到了最右边
整体的代码量比上面多出一行
因为是随机选择得划分值，那么打到任意一个位置，选取作为划分值得权重是一样得
这样一来根据数学推算，最后收敛于O(NlogN)

public static void quickSort3(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process3(arr, 0, arr.length - 1);
	}

	public static void process3(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
		int[] equalArea = partition(arr, L, R);
		process3(arr, L, equalArea[0] - 1);
		process3(arr, equalArea[1] + 1, R);
	}
// arr[L...R]范围上，拿arr[R]做划分值，
// L....R < = >
public static int[] partition(int[] arr, int L, int R) {
    int lessR = L - 1;
    int moreL = R;
    int index = L;
    while (index < moreL) {
        if (arr[index] < arr[R]) {
            lessR++;
            swap(arr, lessR, index);
            index++;
        } else if (arr[index] > arr[R]) {
            moreL--;
            swap(arr, moreL, index);
        } else {
            index++;
        }
    }
    swap(arr, moreL, R);
    //比如342555578 //返回3，6
    return new int[] { lessR + 1, moreL };  
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

关键点：
把核心过程定义出来，然后左右边界求出来，之后通过递归不断的遍历下去，
就是再更小的范围上求出划分值对应得左右边界