快速排序是一种常用的排序算法,比选择排序快得多。例如,C语言标准库中的函数qsort 实现的就是快速排序。快速排序也使用了D&C。(分而治之)
(1) 找出简单的基线条件;
(2) 确定如何缩小问题的规模,使其符合基线条件。 D&C并非可用于解决问题的算法,而是一种解决问题的思路。我们再来看一个例子。 给定一个数字数组。

Python3 实现快速排序-新乡seo|网站优化,网站建设—昊天博客

# -*- coding: utf-8 -*-
""" 
@author:songhao 
@file: c3.py 
@time: 2017/12/26 
"""
import random


def quiksort(arr):
    """
    实现快速排序
    :param arr:
    :return:
    """
    if len(arr) < 2:
        return arr # 基线条件:为空或只包含一个元素的数组是“有序”的
    else:
        pivot = arr[0] # 递归条件
        less = [x for x in arr[1:] if x <= pivot] # 由所有小于基准值的元素组成的子数组

        large = [z for z in arr[1:] if z > pivot] #由所有大于基准值的元素组成的子数组

        print('less', arr, less)
        print('large', arr, large)
        print('分割线'.center(30, '#'))
        return quiksort(large) + [pivot] + quiksort(less) # 递归调用


if __name__ == '__main__':
    new = [random.choice(range(10)) for x in range(10)]
    print(new)
    # new = [1, 3, 5]
    print(quiksort(new))

返回结果是:

Python3 实现快速排序-新乡seo|网站优化,网站建设—昊天博客

快速排序 速度很快

递归调用算法:

Python3 中的递归算法

先看程序: 返回的结果: Python3 默认的递归深度是1000 Python3 的递归调用栈的深度有限制, 可以通过…