1、快排思想

快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。

2、快排流程

1、选定一个基准元素

2、通过基准将数组分成左右两部分:将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。

2、重复步骤1、2,采用递归的方法:分别将左侧部分、右侧部分,按照步骤1、2排序,直至将无序序列排列成有序序列。

3、快排实现

def quick_sort(arr, left, right):
    if left >= right:
        return
    i, j = left, right    # 首尾指针
    while i < j:            
        while i < j and arr[j] >= arr[left]: # 以最左边第一个数为基准,先用尾指针往前扫描
            j -= 1
        while i < j and arr[i] <= arr[left]:
            i += 1
        if i < j:            # 交换2个数的位置
            arr[i], arr[j] = arr[j], arr[i]
    arr[left], arr[i] = arr[i], arr[left]   # 基准归位
    quick_sort(arr, left, i-1)   # 递归左半部分
    quick_sort(arr, i+1, right)  # 递归右半部分
    return arr

if __name__ == '__main__':
    # a = [10, 1, 5, 2, 4, 3, 2, 1]
    a = [5, 8, 7, 6, 3, 2, 1]
    left, right = 0, len(a)-1
    quick_sort(a, left, right)
    print(a)

4、复杂度分析

(1)时间复杂度分析

平均时间复杂度O(nlog_2n);

待排序列越接近无序,排序效率越高,最好时间复杂度O(nlog_2n)

待排序列越接近有序,排序效率越低,最坏时间复杂度O(n^2)

(2)空间复杂度分析

空间复杂度为O(log_2n),快排是递归进行的,递归需要栈的辅助。

PS:快排是一种不稳定的排序算法。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部