请选择 进入手机版 | 继续访问电脑版

好程序员-千锋教育旗下高端IT职业教育品牌

400-811-9990
我的账户
好程序员

专注高端IT职业培训

亲爱的猿猿,欢迎!

已有账号,请

如尚未注册?

[Python] 好程序员Python培训学习路线分享实现快速排序算法

[复制链接]
  好程序员Python培训学习路线分享实现快速排序算法快速排序算法是一种基于交换的高效的排序算法,由C.R.A.Hoare1962年提出,是一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide and conquer algorithm)
分治法的基本思想
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的基本思想
- 先找到一个基准点(一般指数组的中部),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边。
- 左右分别用一个空数组去存储比较后的数据。
- 最后递归执行上述操作,直到数组长度 <= 1;
代码实现
```python
def quick_sort(lists, left, right):
    '''快速排序'''
    # 跳出递归判断
    if left >= right:
        return lists
    # 选择参考点,该调整范围的第1个值
    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[left] = key
    # 递归,并返回结果
    quick_sort(lists, low, left - 1)    # 递归左边部分
    quick_sort(lists, left + 1, high)   # 递归右边部分
    return lists
numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5]
quick_sort(numbers0len(numbers)-1)
assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
好程序员Python培训官网:http://www.goodprogrammer.org/python_class.shtml

精彩内容,一键分享给更多人!
回复

使用道具 举报

您需要登录后才可以回帖

本版积分规则

关注我们
好程序员
千锋好程序员

北京校区(总部):北京市海淀区宝盛北里西区28号中关村智诚科创大厦

深圳西部硅谷校区:深圳市宝安区宝安大道5010号深圳西部硅谷B座A区605-619

杭州龙驰智慧谷校区:浙江省杭州市下沙经济技术开发区元成路199号龙驰智慧谷B座7层

郑州校区:郑州市二七区航海中路60号海为科技园C区10层、12层

Copyright 2007-2019 北京千锋互联科技有限公司 .All Right

京ICP备12003911号-5 京公安网11010802011455号

请您保持通讯畅通1对1咨询马上开启