快速排序分治算法解析

FrancisSoung 发布于2019-08-16 10:34 / 2699人阅读

摘要：快速排序分治算法解析声明文章均为本人技术笔记，转载请注明出处快速排序分治算法思路复杂度分析由于切分算法性能不稳定，快排最差时间复杂度为，平均时间复杂度为，空间复杂度为快速排序划分算法需要升序排序条件下，对于一个轴点，一次切分操作完成后保

快速排序分治算法解析 声明

文章均为本人技术笔记，转载请注明出处：https://segmentfault.com/u/yzwall

1.快速排序-分治算法思路

复杂度分析：由于切分算法性能不稳定，快排最差时间复杂度为$O(n ^ 2)$，平均时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$；

2. 快速排序-划分算法(Partition)

需要升序排序条件下，对于一个轴点$pivot$，一次切分操作完成后保证：

$<= pivot$的都在$pivot$左边，$>= pivot$的都在$pivot$右边

反之，在降序排序条件下，保证

$>= pivot的都在$pivot$左边, $<= pivot$的都在$pivot$右边

2.1 快速排序不稳定性

快速排序的不稳定性在于轴点$pivot$的选择上，如果$pivot$选择数组一边，排序退化为冒泡排序($O(n^2)$)，因此$pivot$尽量选择均匀，通常进行二者取中：
$$
pivot = nums[start + (end - start) / 2]
$$

2.2 leftIndex <= rightIndex辨析

while (leftIndex <= rightIndex) {
    // 在左侧寻找不合法数， A[leftIndex] < pivot，保证切分均匀
    while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
        ...
    }
    
    // 在右侧寻找不合法数， A[rightIndex] > pivot，保证切分均匀
    while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
        ...
    }
    
    // 找到不合法数，将不合法数放入对应区间内
    if (leftIndex <= rightIndex) {
        ...
    }
    quickSort(A, start, rightIndex);
    quickSort(A, leftIndex, end);
}

leftIndex <= rightIndex操作保证分治快排时，分治子数组没有重叠部分，因此如果将
leftIndex <= rightIndex改成leftIndex < rightIndex，递归找不到出口，造成StackOverFlow
当划分操作完成后，必然有：
$$
rightIndex < leftIndexnums
$$

$$
nums[rightIndex] <= nums[leftIndex]
$$

2.3 保证$pivot$切分均匀

// 在左侧寻找不合法数， A[leftIndex] < pivot，保证切分均匀
while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
     leftIndex++;
}

// 在右侧寻找不合法数， A[rightIndex] > pivot，保证切分均匀
while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
    rightIndex--;
}

$=pivot$的数在切分过程中可以放在$pivot$左右两边：为了防止当$=pivot$在数组中大量出现时，如果严格保证$=pivot$的数在$pivot$某一侧，会造成$pivot$选择不均匀，因此必须保证$=pivot$的数字尽量在$pivot$两侧均匀分布，因此整体有序的判断条件为A[leftIndex] < pivot和A[rightIndex] > pivot；

2. 快速排序-分治法递归实现代码

/**
 * http://www.lintcode.com/en/problem/sort-integers-ii/
 * 快速排序一个数组（升序）
 * @author yzwall
 */
class Solution {
    
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[]A, int start, int end) {
        //　递归出口　单元素不做排序
        if (start >= end) {
            return;
        }
        
        // 切分操作时间复杂度O(n)，空间复杂度O(1)
        int leftIndex = start;
        int rightIndex = end;
        int pivot = A[start + (end - start) / 2];
        
        // leftIndex <= rightIndex, < 导致栈溢出
        while (leftIndex <= rightIndex) {
            // 在左侧寻找不合法数， A[leftIndex] < pivot，保证切分均匀
            while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
                leftIndex++;
            }
            
            // 在右侧寻找不合法数， A[rightIndex] > pivot，保证切分均匀
            while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
                rightIndex--;
            }
            
            // 找到不合法数，将不合法数放入对应区间内
            if (leftIndex <= rightIndex) {
                int temp = A[leftIndex];
                A[leftIndex] = A[rightIndex];
                A[rightIndex] = temp;
                // 继续查找不合法数
                leftIndex++;
                rightIndex--;
            }
        }
        
        /**
         * 跳出循环，leftIndex与rightIndex已互换位置
         * 分治时间复杂度O(logn), 空间复杂度O(1)
         */
        quickSort(A, start, rightIndex);
        quickSort(A, leftIndex, end);
    }
}

云服务器 GPU云服务器快速排序算法最好的快速排序算法最快速的排序算法 java实现分治排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70047.html

算法学习笔记：排序算法(二)

摘要：上一篇中已经介绍了几个简单的排序算法，这一篇文章我将继续向大家介绍排序算法相关的内容，本篇的会介绍希尔排序快速排序归并排序以及分治算法的思想，希望通过本文章能够加深大家对排序算法的理解。上一篇中已经介绍了几个简单的排序算法，这一篇文章我将继续向大家介绍排序算法相关的内容，本篇的会介绍希尔排序、快速排序、归并排序以及分治算法的思想，希望通过本文章能够加深大家对排序算法的理解。希尔排序...

William_Sang 2019-08-23 14:40 评论0 收藏0
js 排序算法之快速排序

摘要：快速排序是一种划分交换排序。快速排序基于冒泡递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。...

Eidesen 2019-08-23 11:38 评论0 收藏0
直击架构本质：优秀架构师必须掌握的几种架构思维

摘要：由于文章内容较长，所以我把它分成两篇小文章，在第一篇优秀架构师必须掌握的架构思维中，我会先介绍抽象分层分治和演化这四种应对复杂性的基本思维。另外，上面的算法是两路归并，也可以采用多路归并，甚至是采用堆排序进行优化，但是总体分治思路没有变化。 showImg(https://segmentfault.com/img/bVbeYpP?w=642&h=400); 介绍架构的本质是管理复杂性...

lijy91 2019-06-24 18:06 评论0 收藏0
直击架构本质：优秀架构师必须掌握的几种架构思维

摘要：由于文章内容较长，所以我把它分成两篇小文章，在第一篇优秀架构师必须掌握的架构思维中，我会先介绍抽象分层分治和演化这四种应对复杂性的基本思维。另外，上面的算法是两路归并，也可以采用多路归并，甚至是采用堆排序进行优化，但是总体分治思路没有变化。 showImg(https://segmentfault.com/img/bVbeYpP?w=642&h=400); 介绍架构的本质是管理复杂性...

fjcgreat 2019-08-19 10:54 评论0 收藏0