搜 索

排序算法丨快速排序

  • 448阅读
  • 2021年03月16日
  • 0评论
首页 / 默认分类 / 正文

前言

快速排序(QuickSort),由 C.A.R.Hoare(东尼霍尔,Charles Antony Richard Hoare) 在 1960 年提出。
它是对冒泡排序算法的一种改进,比冒泡排序高效得多,所以叫做快速排序。
之所以快,是因为它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

排序思路

它的基本思想:

  1. 从数组中取出一个数,称之为基数(pivot);
  2. 遍历数组,将大于或等于基数的数字放到它的右边,比基数小的数字放到它的左边。遍历完成后,数组被分成了左右两个区域;
  3. 将左右两个区域视为两个数组,重复前两个步骤,直到排序完成。(递归)
    分组比较

分治法

分治法,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

在快速排序中,就用到了这种方法:将一个待排序的数组,分成两个待排序的小数组,排序后再分成小数组......

基准的选择

基数的选择没有固定标准,随意选择区间内任何一个数字做基数都可以。通常来讲有三种选择方式:

  1. 选择第一个元素作为基数;
  2. 选择最后一个元素作为基数;
  3. 选择区间内一个随机元素作为基数。

选择的基数不同,算法的实现也不同。实际上第 3 种选择方式的平均时间复杂度是最优的。

如果选择第 1 种方案,那么在排列完全逆序的数组时,整个数组都没有分成两半,每一轮都只确定了基准元素的位置。
这种极端情况下,快速排序无法发挥分治法的优势,时间复杂度退化成了 O(n2)
所以,为了避免这种情况,一般都是选择第 3 种方案——随机选择也有一定的概率选到最大值或最小值。

元素的交换移动

确定了基准元素后,比较其他元素与基准元素的大小,将其他元素移动到适合的位置。

挖坑法
指针交换法

private static int partition1(int[] arr, int startIndex, int endIndex) {
    // 取第一个位置的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    // 坑的位置,初始等于pivot的位置
    int index = startIndex;
    // 大循环在左右指针重合或者交错时结束
    while (right >= left) {
        // right指针从右向左进行比较
        while (right >= left) {
            if (arr[right] < pivot) {
                arr[left] = arr[right];
                index = right;
                left++;
                break;
            }
            right--;
        }
        //left指针从左向右进行比较
        while (right >= left) {
            if (arr[left] > pivot) {
                arr[right] = arr[left];
                index = left;
                right--;
                break;
            }
            left++;
        }
    }
    arr[index] = pivot;
    return index;
}

private static int partition2(int[] arr, int startIndex, int endIndex) {
    // 取第一个位置的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    while (left != right) {
        // 控制right指针比较并左移
        while (left < right && arr[right] > pivot) {
            right--;
        }
        // 控制right指针比较并右移
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换left和right指向的元素
        if (left < right) {
            int p = arr[left];
            arr[left] = arr[right];
            arr[right] = p;
        }
    }
    // pivot和指针重合点交换
    int p = arr[left];
    arr[left] = arr[startIndex];
    arr[startIndex] = p;
    return left;
}

代码实现

从 left 开始,遇到比基数大的数,记录其下标;再从 right 往前遍历,找到第一个比基准元素小的数,记录其下标;然后交换这两个数。继续遍历,直到 left 和 right 相遇。然后就交换基数和中间值,并返回中间值的下标。

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int start, int end) {
    // 如果区域内的数字少于 2 个,退出递归
    if (start >= end) {
        return;
    }
    // 将数组分区,并获得中间值的下标
    int middle = partition(arr, start, end);
    // 对左边区域快速排序
    quickSort(arr, start, middle - 1);
    // 对右边区域快速排序
    quickSort(arr, middle + 1, end);
}

// 将 arr 从 start 到 end 分区,左边区域比基数小,右边区域比基数大,然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {
    // 取第一个数为基数;应该随机挑选一个更好
    int pivot = arr[start];
    // 从第二个数开始分区
    int left = start + 1;
    // 右边界
    int right = end;
    // left、right 相遇时退出循环
    while (left < right) {
        // 找到第一个大于基数的位置
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换这两个数,使得左边分区都小于或等于基数,右边分区大于或等于基数
        if (left != right) {
            exchange(arr, left, right);
            right--;
        }
    }
    // 如果 left 和 right 相等,单独比较 arr[right] 和 pivot
    if (left == right && arr[right] > pivot) {
        right--;
    }
    // 将基数和中间数交换
    if (right != start) {
        exchange(arr, start, right);
    }
    // 返回中间值的下标
    return right;
}

// 交换两个数字
private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

动画演示

演示动画来源于Visualgo

快速排序

复杂度分析

平均时间复杂度为 O(nlogn),最坏的时间复杂度为 O(n2),空间复杂度与递归的层数有关,每层递归会生成一些临时变量,所以空间复杂度为 O(logn) ~ O(n),平均空间复杂度为 O(logn)。

快速排序的优化

第一种就是每轮选择基数时,从剩余的数组中随机选择一个数字作为基数。这样每轮都选到最大或最小值的概率就会变得很低了(但依然存在概率)。用这种方式选择基数,其平均时间复杂度是最优的。

第二种是在排序之前,先用洗牌算法将数组的原有顺序打乱,以防止原数组正序或逆序。Java 已经将洗牌算法封装到了集合类中,即 Collections.shuffle() 函数。洗牌算法由 Ronald A.Fisher 和 Frank Yates 于 1938 年发明,思路是每次从未处理的数据中随机取出一个数字,然后把该数字放在数组中所有未处理数据的尾部。

第三种是在快速排序之前先对数组做个判断,如果已经有序则直接返回,如果是逆序则直接倒序即可。在 Java 内部封装的 Arrays.sort() 的源码中就采用了此解决方案。

参考

LeetCode
程序员小灰
Github
打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
暂无评论
avatar