SYSTEM
快速排序
src/content/notes/system/快速排序.md 快速排序
快速排序(Quick Sort):通过分治思想对冒泡排序的改进,基本过程是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,以此达到整个数据变成有序序列
实现思路:
- 从数列中挑出一个元素,称为基准(pivot)
- 重新排序数列,所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边),在这个分区退出之后,该基准就处于数列的中间位置,这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
public class QuickSort {
public static void main(String[] args) {
int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
// 递归结束的条件
if (low >= high) {
return;
}
int left = low;
int right = high;
// 基准数
int temp = arr[left];
while (left < right) {
// 用 >= 可以防止多余的交换
while (arr[right] >= temp && right > left) {
right--;
}
// 做判断防止相等
if (right > left) {
// 到这里说明 arr[right] < temp
arr[left] = arr[right];// 此时把arr[right]元素视为空
left++;
}
while (arr[left] <= temp && left < right) {
left++;
}
if (right > left) {
arr[right] = arr[left];
right--;
}
}
// left == right
arr[left] = temp;
quickSort(arr, low, left-1);
quickSort(arr, right + 1, high);
}
}
快速排序和归并排序的区别:
- 快速排序是另外一种分治的排序算法,将一个数组分成两个子数组,将两部分独立的排序
- 归并排序的处理过程是由下到上的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题
- 快速排序和归并排序是互补的:归并排序将数组分成两个子数组分别排序,并将有序的子数组归并从而将整个数组排序,而快速排序的方式则是当两个数组都有序时,整个数组自然就有序了
- 在归并排序中,一个数组被等分为两半,归并调用发生在处理整个数组之前,在快速排序中,切分数组的位置取决于数组的内容,递归调用发生在处理整个数组之后
时间复杂度:
-
最优情况:每一次切分选择的基准数字刚好将当前序列等分。把数组的切分看做是一个树,共切分了 logn 次,所以,最优情况下快速排序的时间复杂度为 O(nlogn)
-
最坏情况:每一次切分选择的基准数字是当前序列中最大数或者最小数,这使得每次切分都会有一个子组,那么总共就得切分n次,所以最坏情况下,快速排序的时间复杂度为 O(n^2)
-
平均情况:每一次切分选择的基准数字不是最大值和最小值,也不是中值,这种情况用数学归纳法证明,快速排序的时间复杂度为 O(nlogn)
推荐视频:https://www.bilibili.com/video/BV1b7411N798?t=1001&p=81
参考文章:https://blog.csdn.net/nrsc272420199/article/details/82587933