← 返回学习路线

SYSTEM

快速排序

Java基础快速排序system
src/content/notes/system/快速排序.md

快速排序

快速排序(Quick Sort):通过分治思想对冒泡排序的改进,基本过程是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,以此达到整个数据变成有序序列

实现思路:

  1. 从数列中挑出一个元素,称为基准(pivot)
  2. 重新排序数列,所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边),在这个分区退出之后,该基准就处于数列的中间位置,这个称为分区(partition)操作;
  3. 递归地(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