Quick sorting

admin 2019-08-12 22:36:06 0 0 Algorithm 249 复制链接

image.png


Quick sorting is an enhancement of bubble sorting.


Solution 2:

def quick_sort_v2(arr):
    if len(arr) >= 2:
        mid = arr[len(arr) // 2]
        left, right = [], []
        arr.remove(mid)
        for x in arr:
            if x < mid:
                left.append(x)
            else:
                right.append(x)
        return quick_sort_v2(left) + [mid] + quick_sort_v2(right)
    else:
        return arr


基本思想

    分治思想,递归思想

快排演示:

具体思路:

    先从序列中选取一个数作为基数,可以是头元素,伪元素,中间元素

    然后以这个基数为基准,把序列分成两部分,其中一部分的数据比另一部分都要小

    递归重复第二步


时间复杂度:

    最好:O(nlogn)

    平均:O(nlogn)

    最坏:O(n**2)


评论(0)

    还没有评论,快来抢沙发吧!