博客

def quick_sort(arr):
    """
    快速排序（二分法递归排序）
    原理：取数组第一个数作为标志，小于它的所有数放在一个列表，大于等于它的放在另一个列表，然后递归处理这两个数组。
        递归过程中会把列表越分越小，最小的列表中只包含一个数（二分法思想），小列表排好序后组合成一个列表即可。
    时间复杂度：O(nlogn)
    :param arr:
    :return:
    """
    if len(arr) > 1:
        left, right = [], []
        # 确定一个数，把所有小于它的数放在一个数组，把大于等于它的数放在一个数组
        for i in arr[1:]:
            if i < arr[0]:
                left.append(i)
            else:
                right.append(i)
        return quick_sort(left) + [arr[0]] + quick_sort(right) # 递归
    else:
        return arr
    


if __name__ == '__main__':
    import numpy
    array = list(numpy.random.randint(0, 50, 20))
    print(array)
    # [0, 20, 0, 45, 36, 10, 20, 27, 33, 32, 47, 40, 16, 11, 3, 37, 19, 49, 41, 3]

    print(quick_sort(array))
    # [0, 0, 3, 3, 10, 11, 16, 19, 20, 20, 27, 32, 33, 36, 37, 40, 41, 45, 47, 49]

Mr.bai