算法——分而治之及快速排序

系统管理员 2021-12-14 07:43 205阅读 0赞

# 分而治之及快速排序 #

算法——快速排序
    
    分而治之(divide and conquer, D&C)：重要的递归式问题解决方法，包括两个步骤
        1）找出基线条件，要尽可能简单
        2）不断将问题分解（缩小规模），直到符合基线条件
    
    快速排序(quick sort)：第一个重要的D&C算法，算法复杂性为O(nlog n)
    
    要点：
    　　D&C将问题逐步分解。使用D&G处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
    　　实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(nlog n)。

# divide_and_conquer.py 分而治之
    def sum(li):  # 递归方法求和
        if len(li) == 1:  # base case
            return li[0]
        else:  # recursive case
            return li[0] + sum(li[1:])
    
    
    def items(li):  # 递归方法求元素数
        if len(li) == 1:
            return 1
        else:
            return 1 + items(li[1:])
    
    
    def max(li, num=0):
        if len(li) == 0:  # base case
            return num
        else:  # recurvise case 
            if num < li[0]:
                num = li[0]
            return max(li[1:], num)
    
    
    if __name__ == '__main__':
        li = [1, 4, 6, 8, 9]
        print(sum(li))
        print(items(li))
        print(max(li))

# quick_sort.py 快速排序
    
    
    def quick_sort(arr):
        if len(arr) < 2:  # 如果数组小于两个值，返回（已经无需排序）
            return arr
        else:
            pivot = arr[0]  # pivot 基准值
            less = [i for i in arr[1:] if i <= pivot]
            greater = [i for i in arr[1:] if i > pivot]
            return quick_sort(less) + [pivot] + quick_sort(greater)
    
    
    if __name__ == '__main__':
        li = [10, 5, 2, 3]
        print(quick_sort(li))

# quick_sort.py 快速排序
    import random
    def quick_sort(arr):
        if len(arr) < 2:  # 如果数组小于两个值，返回（已经无需排序）
            return arr
        else:
            index = int(len(arr)/2)  # 取中间值作为基准值
            pivot = arr[index]  # pivot 基准值
            new_arr = arr[:]  # 去掉pivot值后的数组
            new_arr.pop(index)
            less = [i for i in new_arr if i <= pivot]
            greater = [i for i in new_arr if i > pivot]
            return quick_sort(less) + [pivot] + quick_sort(greater)
    
    
    if __name__ == '__main__'：
    　　li = [random.choice(range(100)) for i in range(5)]
    　　print(li)
    　　print(quick_sort(li))

转载于:https://www.cnblogs.com/noonjuan/p/10922390.html