环境

Ubuntu 16.04

Python 3.5.2

问题

现有一个生成1-5随机数的函数random_5（概率平均），如何将此转换为生成1-7随机数random_7的函数（概率平均）,不得使用random模块

思路一（False）

直接将random_5生成的随机数乘以7/5后再通过round函数进行四舍五入后输出

random_5输出	random_7输出
1	1
2	3
3	4
4	6
5	7

特别糟糕的想法…

思路二（False）

生成两次random_5，将两者的值相加后减一(random_5 + random_5 - 1)，得出随机数1-9，而后再做一次判断，将8和9剔除掉，只在返回1-7的时候输出

不过很快就发现，只有在两次random_5都返回1的时候，才会返回1，概率远小于返回其它六个数

又是一个糟糕的想法…

思路三（True）

* 通过之前的两种思路，可以总结出将random_5返回的数据经过各种处理后不筛选返回1-7是不可能实现的（不能说不可能，只是我个人能力有限，暂时还没想出方法），那必须采用思路二中的筛选方法。
* 确定要使用筛选方法之后，目标就变成了生成等概率的、值取值范围大于1-7的随机数。
* 相加和返回值乘系数的方法都尝试过了，那么是否可以将两者结合一下呢。
* 首先思考乘系数，random_5 * 2 - 1的返回结果是[1, 3, 5, 7, 9]，想要等概率生成1-10的话，比如再将此返回值加上随机生成的0和1，也就是random.randint(0,… 阅读全文 “将生成1-5随机数函数转换为1-7随机数函数的实现方法及其进阶”

环境

Python 3.5.2

原理

• 找出列表中最大和最小的元素
• 构建新列表，元素全为零，长度为最大值与最小值之间的差值加一
• 统计待排序列表中每个值i出现的次数，并将新列表中下标为i-min的值加一
• 将新列表中非零值的下标反转回原有元素i（即加上最小值），构建有序列表

源码

def count_sort(l):
    max = 0
    min = 1024

    for item in l:
        if item > max:
            max = item
        elif item < min:
            min = item

    count = [0]*(max-min+1)
    for index in l:
        count[index-min] += 1

    index = 0
    for i in range(max-min+1):
        for j in range(count[i]):
            l[index] = i+min
            index += 1

if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    count_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度：O(n+k)
• 最坏时间复杂度：O(n+k)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：稳定

环境

Python 3.5.2

原理

• 将列表构造成最大堆或最小堆
• 将堆的根节点，即最大值或最小值与堆的末尾对调
• 将末尾元素（即之前得到的堆的根节点）移除后，重构堆，如此循环

源码

def heap_sort(l):
    def max_heapify(root_index, end_index):
        """函数用于构造最大堆"""
        # 减一是因为堆的下标从１开始
        max_child_index = root_index*2-1

        # 在该二叉树有两个子节点的情况下，将两个子节点比较大小
        if max_child_index + 1 < end_index:
            if l[max_child_index+1] > l[max_child_index]:
                max_child_index += 1

        # 将最大的子节点与根节点做比较
        if l[max_child_index] > l[root_index-1]:
            l[max_child_index], l[root_index-1] = l[root_index-1], l[max_child_index]


    # 循环构造最大堆，而后将最大堆的根节点与末节点调换
    for end_index in range(len(l), 1, -1):
        # 每次要构造的最大堆大小与末节点有关
        max_root_index = end_index//2

        # 构造一个最大堆
        for root_index in range(max_root_index, 0, -1):
            max_heapify(root_index, end_index)

        # 将最大堆的根节点与末节点调换
        l[0], l[end_index-1] = l[end_index-1], l[0]


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    heap_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定

环境

Python 3.5.2

原理

• 将递归分解列表，直至最小（即每个列表仅有一个元素）
• 将列表分解最小之后，递归合并两个列表，即挨个比较两个列表中最前面的元素，谁较小就将谁加入新的列表，而后该列表的下标后移一位，继续比较，直至其中一个列表为空，而后将另一个列表中剩余的元素加入新列表
• 不断合并，直至完全排序完成

源码

def merge_sort(l):
    # 对列表进行二分分解
    n = len(l)
    if n <= 1:
        return l
    mid_posi = n//2
    # print(1)
    l_list = merge_sort(l[:mid_posi])
    # print(2)
    r_list = merge_sort(l[mid_posi:])
    # print(3)

    # 对列表进行合并
    sorted_list = []
    l_posi = 0
    r_posi = 0
    # print('l_list: %s' % l_list)
    # print('r_list: %s' % r_list)

    while l_posi < len(l_list) and r_posi < len(l_list):
        if l_list[l_posi] <= r_list[r_posi]:
            sorted_list.append(l_list[l_posi])
            l_posi += 1
        else:
            sorted_list.append(r_list[r_posi])
            r_posi += 1

    # 将列表剩余部分合并
    sorted_list += l_list[l_posi:]
    sorted_list += r_list[r_posi:]
    # print('sorted_list: %s' % sorted_list)

    return sorted_list


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    sorted_list = merge_sort(l)
    print(sorted_list)

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：稳定

环境

Python 3.5.2

原理

• 为插入排序的优化
• 对要排序的列表根据一定间隔（初始间隔一般设为列表长度的一半）进行分组
• 对各列表之间相同位置（下标）的元素进行插入排序
• 间隔减半，再次分组并对各列表之间相同位置（下标）的元素进行插入排序
• 如此循环，最终间隔为1，即为正常的插入排序

源码

def shell_sort(l):
    n = len(l)
    # 初始间隔
    gap = n//2

    while gap > 0:
        for i in range(gap, n):
            for j in range(i, gap-1, -gap):
                if l[j] < l[j-gap]:
                    l[j], l[j-gap] = l[j-gap], l[j]
                else:
                    break
        gap //= 2


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    shell_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度（初始间隔为列表长度一半时）：O(nlogn)
• 最坏时间复杂度：O(n²)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定

环境

Python 3.5.2

原理

• 在列表中挑选出一个基准值
• 将列表中的其它元素与基准值对比，比基准值大的放在基准值右侧，比基准值小的放在基准值左侧
• 以此类推

源码

def quick_sort(l, start, end):
    if start >= end:
        return

    low = start
    high = end
    mid_value = l[low]

    while low < high:
        # low<high这个条件必须在这里再次体现，避免出现循环过程中low>high的情况
        while low < high and l[high] >= mid_value:
            high -= 1
        # 当中间值右侧的值小于中间值时，将该值赋值于l[low](原来的值已保存至mid_value变量)
        l[low] = l[high]

        # low<high这个条件必须在这里再次体现，避免出现循环过程中low>high的情况
        while low < high and l[low] <= mid_value:
            low += 1
        # 当中间值左侧的值大于中间值时，将该值赋值于l[high](原来的值已保存至l[low])
        l[high] = l[low]

    # 退出循环时，说明low==high，则可以将mid_value的值赋予它
    l[low] = mid_value

    quick_sort(l, start, low-1)
    quick_sort(l, low+1, end)


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    quick_sort(l, 0, len(l)-1)
    print(l)

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n²)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定

环境

Python 3.5.2

原理

• 在列表左侧构建有序序列
• 一开始将第一个元素视为有序序列
• 对于未排序序列，则将未排序序列中的元素依次从右到左与已排序序列中的元素做比较
• 如果未排序元素小于当时比较的已排序元素，则将该已排序元素右移
• 如果未排序元素大于当时比较的已排序元素，则说明该元素已插入到合适位置，此轮循环结束
• 以此类推

源码

def insert_sort(l):
    n = len(l)
    # 要排序的元素
    for i in range(1, n):
        # 已排序的元素
        for j in range(i, 0, -1):
            if l[j] < l[j-1]:
                l[j], l[j-1] = l[j-1], l[j]
            else:
                break


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    insert_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n²)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：稳定

环境

Python 3.5.2

原理

• 默认最左侧的元素为最小，而后依次将右侧的每个元素与最左侧的元素比较，如果比最左测的元素小，则交换位置
• 第一遍遍历会将最小的元素放在最左边，而后继续遍历，依次得出第二小、第三小…第二大的元素

源码

def select_sort(l):
    n = len(l)
    for i in range(n-1):
        for j in range(i+1, n):
            # 一开始默认下标为i的值最小
            if l[j] < l[i]:
                l[j], l[i] = l[i], l[j]


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    select_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度：O(n²)
• 最坏时间复杂度：O(n²)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定

环境

Python 3.5.2

原理

• 从头开始比较列表中每两个相邻的元素，如果前者比后者大，则将这两个元素交换
• 第一遍遍历会将最大的元素放置在最右边，而后继续遍历，依次得出第二大、第三大…第二小的元素
• [优化]每次遍历时，判断各元素之间的位置是否发生了改变，如果没有改变，则直接结束排序

源码

def bubble_sort(l):
    n = len(l)
    for j in range(n-1):
        # 用于判断此轮遍历过程中各元素之间的位置是否发生了改变
        has_change = False
        for i in range(n-1-j):
            if l[i] > l[i+1]:
                l[i+1], l[i] = l[i], l[i+1]
                has_change = True
        if has_change == False:
            break


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    bubble_sort(l)
    print(l)

时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n²)
• 稳定性（多个元素等值的情况下是否会破坏原有顺序）：稳定