快速排序
快速排序的python实现
快速排序
快速排序是利用了分治的思想，将数组分为两个部分，分别进行排序，然后合并。
在学习快速排序之前，需要先了解一道题：荷兰国旗问题
荷兰国旗问题
给定一个数组arr,和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
思路
- 定义三个指针，分别指向小于num的数less(初始为left-1)，当前指向的数cur( 初始为left)，大于num的数more(初始为right+1)
- 循环判断，如果cur小于num，则less++，cur++
- 循环判断，如果cur大于num，则more--
- 循环判断，如果cur等于num，则cur++
- 当left >= right时，结束循环
快速排序
- 随机选择一个数，作为基准数
- 以基准数作为荷兰国旗问题的num，将数组分为三个部分
- 递归调用，对小于基准数的部分进行快速排序
- 递归调用，对大于基准数的部分进行快速排序
- 直到子数组的长度为1，结束递归
代码实现
Python
def quick_sort(arr: List) -> None:
def partition(arr: List, left: int, right: int, num: int) -> int:
less = left - 1
more = right + 1
while left < more:
if arr[left] < num:
arr[less + 1], arr[left] = arr[left], arr[less + 1]
less += 1
left += 1
elif arr[left] > num:
arr[more - 1], arr[left] = arr[left], arr[more - 1]
more -= 1
else:
left += 1
return less + 1, more - 1
def recursion(left: int, right: int) -> None:
if left >= right:
return
pivot_index = random.randint(left, right)
pivot = arr[pivot_index]
arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
less, more = partition(arr, left, right, pivot)
recursion(left, less - 1)
recursion(more + 1, right)
recursion(0, len(arr) - 1)Java
public class QuickSort {
private static final Random random = new Random();
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
recursion(arr, 0, arr.length - 1);
}
private static void recursion(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = left + random.nextInt(right - left + 1);
int pivot = arr[pivotIndex];
swap(arr, pivotIndex, right);
Range range = partition(arr, left, right, pivot);
recursion(arr, left, range.less - 1);
recursion(arr, range.more + 1, right);
}
private static Range partition(int[] arr, int left, int right, int pivot) {
int less = left - 1;
int more = right + 1;
while (left < more) {
if (arr[left] < pivot) {
swap(arr, ++less, left++);
} else if (arr[left] > pivot) {
swap(arr, --more, left);
} else {
left++;
}
}
return new Range(less + 1, more - 1);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static class Range {
int less;
int more;
Range(int less, int more) {
this.less = less;
this.more = more;
}
}
}复杂度分析
快速排序的时间复杂度最差为O(N^2)，但由于快速排序使用了随机数，通过计算数学期望，时间复杂度为O(NlogN)