快速排序模板及优化

快速排序模板及优化 快速排序模板及优化 算法特性

时间复杂度：O(N*logN)~O(N^2)

最好情况：哨兵划分 *** 作为线性时间复杂度 O(N)；递归轮数共 O(logN)最坏情况：若每轮哨兵划分 *** 作都将长度为 N 的数组划分为长度为 1 和 N - 1的两个子数组，此时递归轮数达到 N轮 。 空间复杂度：O(N)非稳定： 哨兵划分 *** 作可能改变相等元素的相对顺序。

常规：哨兵+递归

将数据组中最左/右侧的数据作为基准数，将它作为哨兵元素，值小于哨兵的放在其左侧，大于的放在其右侧。

一轮划分结束后，转换成两个较短数据组内的排序问题。

对每个短的数据组内递归进行哨兵划分，直到划分得到的子数组长度为1。

这里的swap函数我们没有使用位运算，因为这种思路的快速排序是非稳定排序，所以无法使用位运算。

    static void quickSort(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分 *** 作
        int i = partition(nums, l, r);
        // 递归左（右）子数组执行哨兵划分
        quickSort(nums, l, i - 1);
        quickSort(nums, i + 1, r);
    }

    static int partition(int[] nums, int l, int r) {
        // 以 nums[l] 作为基准数
        int i = l, j = r;
        while (i < j) {
            //从左向右找到第一个大于等于哨兵值的元素
            while (i < j && nums[j] >= nums[l]) j--;
            //从右向左找到第一个小于等于哨兵值的元素
            while (i < j && nums[i] <= nums[l]) i++;
            //分别满足两个条件的元素交换位置
            swap(nums, i, j);
        }
        //完成一次哨兵划分后，将哨兵元素放到中间隔开两个短数组
        swap(nums, i, l);
        return i;
    }





static void swap(int[] nums, int i, int j) {
    // 交换 nums[i] 和 nums[j]
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

算法优化 Tail Call：空间复杂度优化策略

对于快排的空间复杂度分析，我们可以知道，最坏情况下，整个数组完全按照倒序排列，那么此时划分的递归深度为N。

如果我们首先完成一次划分后，其余每次只选择两个数组中较短的一个进行递归划分，就能保证最差的递归深度为O(logN)，也就是深度最大为N/2级别

   static void quickSort(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        while (l < r) {
            // 哨兵划分,得到两个数组
            int mid = partition(nums, l, r);
            // 比较两个数组大小，选择长度短的进行递归
            if (mid - l < r - mid) {
                quickSort(nums, l, mid - 1);
                //每次结束后变化边界，防止溢出
                l = mid + 1;
            } else {
                quickSort(nums, mid + 1, r);
                r = mid - 1;
            }
        }
    }

随机基准：时间复杂度优化策略

分析影响快排时间复杂度的因素可知，我们默认选择最左侧元素作为基准时，如果整个数组恰好按照倒序排序，那么每轮划分我们能完成N-1与1这种最差情况的划分。

为了大概率上避免最差情况，我们每轮划分时都可以选择随机的数据作为哨兵元素。

int partition(int[] nums, int l, int r) {
   
    int ra = (int)(l + Math.random() * (r - l + 1));
    //找到随机基准后，再将其与最左侧元素位置互换，继续按照之前的策略就可以了
    swap(nums, l, ra);
   
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums, i, j);
    }
    swap(nums, i, l);
    return i;
}

快排是O(nlogn)级排序算法中效率最高的算法吗？

最差情况稀疏性： 虽然快速排序的最差时间复杂度为 O(N^2)，差于归并排序和堆排序，但统计意义上看，这种情况出现的机率很低。大部分情况下，快速排序以 O(NlogN) 复杂度运行。缓存使用效率高： 哨兵划分 *** 作时，将整个子数组加载入缓存中，访问元素效率很高；堆排序需要跳跃式访问元素，因此不具有此特性。常数系数低： 在提及的三种算法中，快速排序的 比较、赋值、交换 三种 *** 作的综合耗时最低（类似于插入排序快于冒泡排序的原理）。

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/p57uhr/