数据结构与算法（下）

3.1.17 快速排序

def quick_sort(lists, left, right):
    '''
    快速排序（升序）【不稳定】
    原理：
    分治递归，给定一组序列，把序列分为两部分，前部分的所有元素比后部分的所有元素小，然后再对前后两部分进行快速排序，递归该过程，直到所有记录
    均有序为止。分三步走：
    (1)分解，array[m,...,n] 划分成 array1[m,..,k] 和 array2[k+1,...,n], 其中 array1 所有元素 < array2 所有元素
    (2)递归求解，递归array1, array2
    (3)合并，array[m,...,n] 自动排好序

    :param lists:
    :param left:
    :param right:
    :return lists:
    '''
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

if __name__ == '__main__':
    # 测试代码
    lst = [5, 4, 3, 2, 1]
    # 调用归并排序
    sorted_list = quick_sort(lst, 0, len(lst) - 1)
    print(sorted_list)
    # 输出：[1, 2, 3, 4, 5]

3.1.18 斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、…… 基于python用多种方式，找到前n项斐波那契数列或找到第n项斐波那契数列的值。

# （1）递归法 返回 idx 位的数值，缺点：只能返回最终返回值
def fib_recursion(idx):
    if idx <= 2:
        return 1
    else:
        return fib_recursion(idx-1) + fib_recursion(idx-2)

# （2）迭代法 返回 idx 位之前的fib数列
def fib_iteration(idx):
    lst = []
    n,a,b = 0,0,1
    while n < idx:
        lst.append(b)
        a,b = b, a+b
        n += 1
    return lst

# （3）生成器法
def fib_generator(idx):
    n,a,b = 0,0,1
    while n < idx:
        yield b
        a,b = b, a+b
        n += 1

if __name__ == '__main__':
    idx = 6 
    # 递归法调用
    numb = fib_recursion(idx)
    print(numb)
    # 输出： 8
    
    # 迭代法调用
    lst = fib_iteration(idx)
    print(lst)
    # 输出： [1, 1, 2, 3, 5, 8]
    
    # 生成器法
    lst1 = fib_generator(idx)
    print(list(lst1))
    # 输出： [1, 1, 2, 3, 5, 8]

3.1.18 丑数

只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。一般地，认为1是第一个丑数，1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18是最前面的13个丑数

def ugly_num(n):
    # 边界值判