1. 普通快速排序( O(N2) )
思路规则
最坏情况(复杂度)：[1,2,3,4,5,6,7]， 这样的有序数组，每一次选择最后一个数作为比较值，需要比较所有其他N - 1个数，然后进入下一次递归，比较剩下的有序数组。比较的次数就是 n + n-1 + n-2 … + 2 + 1 等差数列，即为 O(N2)
代码实现(java)
public static void swap(int[] arr, int L, int R) {
int temp = arr[L];
arr[L] = arr[R];
arr[R] = temp;
}
public static int[] quicksort(int[] arr, int L, int R) {
if (L > R) return new int[] {-1, -1};
if (L == R) return new int[] {L, R};
// 左边界
int less = L - 1;
// 右边界
int more = R;
// 当前下标位置
int index = L;
// 结束条件就是 下标位置与右边界相撞
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, ++less, index++);
} else if (arr[index] > arr[R]) {
swap(arr, index, --more);
}
}
swap(arr, more, R);
// 返回相等范围中的左右两边界
return new int[] { less + 1, more };
}
public static void process(int[] arr, int L, int R) {
if (L >= R) return;
int[] equalNum = quicksort(arr, L, R);
process(arr, L,equalNum[0] - 1);
process(arr, equalNum[1] + 1, R);
}
public static void main(String[] args) {
int[] arr = new int[]{2,4,5,1,6,8,2,4,6};
process(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i); // 122445668
}
}
相关题目(75. 颜色分类 荷兰国旗问题)
class Solution {
public static void sortColors(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
// 快排解决
quicksort(nums, 0, nums.length);
}
public static void swap(int[] arr, int L, int R) {
int temp = arr[L];
arr[L] = arr[R];
arr[R] = temp;
}
// 普通快排
public static void quicksort(int[] arr, int L, int R) {
// 左边界
int less = L - 1;
// 右边界
int more = R;
// 当前下标位置
int index = L;
// 结束条件就是 下标位置与右边界相撞
while (index < more) {
if (arr[index] == 1) {
index++;
} else if (arr[index] < 1) {
swap(arr, ++less, index++);
} else if (arr[index] > 1) {
swap(arr, index, --more);
}
}
}
2. 随机快排(重点) ( O(N) * O(logN) )
在普通快排的基础上，在每个范围要快排之前，选出范围上的随机一个数作为比较值，放在最后；这种随机的概率事件，最好情况为O(logN)，最坏情况O(N2)，每种情况概率为 1 / N；所以最终在数学期望中证明中复杂度接近O(N) * O(logN);
代码实现(java)
public static void swap(int[] arr, int L, int R) {
int temp = arr[L];
arr[L] = arr[R];
arr[R] = temp;
}
public static int[] quicksort(int[] arr, int L, int R) {
if (L > R) return new int[] {-1, -1};
if (L == R) return new int[] {L, R};
// 左边界
int less = L - 1;
// 右边界
int more = R;
// 当前下标位置
int index = L;
// 结束条件就是 下标位置与右边界相撞
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, ++less, index++);
} else if (arr[index] > arr[R]) {
swap(arr, index, --more);
}
}
swap(arr, more, R);
// 返回相等范围中的左右两边界
return new int[] { less + 1, more };
}
/*随机快排*/
public static void randomProcess(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = quicksort(arr, L, R);
randomProcess(arr, L, equalArea[0] - 1);
randomProcess(arr, equalArea[1] + 1, R);
}
