V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Newyorkcity
V2EX  ›  Python

请轻喷。自己尝试写了一下快速排序,出了点问题,求指点

  •  
  •   Newyorkcity · 2017-02-01 18:44:04 +08:00 · 4107 次点击
    这是一个创建于 2850 天前的主题,其中的信息可能已经有所发展或是发生改变。
    
    #-*- coding:utf-8 with BOM -*-
    def quick_sort(numbers,left,right):
        #print("left,right 分别为%d,%d"%(left,right)) 
        if right - left <= 1:
            return numbers
        temp = numbers[left]
        i = left
        j = right - 1
        while i < j:
            while numbers[j] > temp and i < j:
                j = j - 1
            else:
                numbers[i] = numbers[j]
            
            while numbers[i] < temp and i < j:
                i = i + 1
            else:
                numbers[j] = numbers[i]
        
        numbers[i] = temp
        
        quick_sort(numbers,left,i)
        #quick_sort(numbers,i+1,right) #问题出在这一行
    
        return numbers
    
    test = [3,7,8,5,1,2,11,5,4]
    print(quick_sort(test,0,len(test)))                
    

    看了一些相关想自己写一下 XD
    问题出在倒数第四个语句,如果把倒数第四个语句注释掉,把 test 数组的第一个数不论给改改成什么数,小于这个数的那部分的顺序总是没毛病的。
    我的想法是第一次分组就用数组中的第一个数当做基准,分出比它小的和比它大的两组。然后比它小的那一组,是从坐标 0 到坐标( i-1 ),比它大的一组是坐标(i+1)到坐标(数组长度-1)
    因而就有了倒数第五个语句和倒数第四个语句分别对较小组和较大组的处理。但是不知道为什么,较大组的处理总是出错 QAQ
    求指点,谢谢
    补上报错

    
    D:\python\algorithm>python quick_sort.py
    left,right分别为0,9
    left,right分别为0,2
    left,right分别为0,1
    left,right分别为2,2
    left,right分别为3,9
    Traceback (most recent call last):
      File "quick_sort.py", line 28, in <module>
        print(quick_sort(test,0,len(test)))
      File "quick_sort.py", line 23, in quick_sort
        quick_sort(numbers,i+1,right) #问题出在这一行
      File "quick_sort.py", line 15, in quick_sort
        while numbers[i] < temp and i < j:
    KeyboardInterrupt
    

    left,right分别为3,9这一句之后程序应该是陷入死循环一样,但是什么输出都没有,最后被我强行暂停。
    我对于进入死循环但是什么输出都没有感到很奇怪,因为我在做这个测试的时候已经把函数块第一个语句的注释符号删掉了,按理来说只要调用了这个函数就一定会有输出。但问题在于,程序像是死循环一样,却始终没输出。。

    17 条回复    2017-02-02 14:02:56 +08:00
    iEverX
        1
    iEverX  
       2017-02-01 18:56:16 +08:00
    i+1 -> i + 2
    Newyorkcity
        2
    Newyorkcity  
    OP
       2017-02-01 19:13:38 +08:00
    @iEverX 这样改了之后不会出现不出结果的错误。。但是输出的结果并没有对较大组进行整理。。
    z657386160z
        3
    z657386160z  
       2017-02-01 19:20:28 +08:00
    caomu
        4
    caomu  
       2017-02-01 19:23:45 +08:00   ❤️ 1
    @livid 加上对微博图床的 https 地址的支持吧
    czheo
        5
    czheo  
       2017-02-01 19:35:46 +08:00
    你那里错我不知道,但根据你的代码改了改可以跑。

    https://gist.github.com/czheo/7421d305bb2e5d3049ce48545646d6f4
    Newyorkcity
        6
    Newyorkcity  
    OP
       2017-02-01 19:57:25 +08:00
    @czheo 也就是说 quick_sort(numbers,i+1,right)这个思路是对的没毛病,真正的错误在函数的具体过程里?
    可是为什么对于较小组都能正常排序对于较大组就不能呢。。
    Livid
        7
    Livid  
    MOD
       2017-02-01 21:00:49 +08:00   ❤️ 1
    @caomu 好的,正在做。
    hxndg
        8
    hxndg  
       2017-02-01 23:00:23 +08:00
    讲道理这个问题你只要把数组打出来就可以发现了。
    这是第一次遍历,也就是你要处理 3,9 时候的数组
    2,1,3,5,8,7,11,5,4 恩,你模拟一下就知道问题出在哪里了
    ps 你这个要改的话,,,大概只需要 1s ?
    hxndg
        9
    hxndg  
       2017-02-01 23:01:02 +08:00
    我虽然也写 python ,但是我把序号什么的改了一下,不过应该影响不大
    hxndg
        10
    hxndg  
       2017-02-01 23:03:07 +08:00
    @z657386160z 表示。。。你虽然图贴的确实能够解决楼主的问题。。。但是一般不一定能看明白到底问题是哪里。。。因为 lz 大方向没错啊。。。
    Livid
        11
    Livid  
    MOD
       2017-02-02 00:47:13 +08:00   ❤️ 2
    @caomu 已经可以支持。
    srlp
        12
    srlp  
       2017-02-02 04:31:57 +08:00   ❤️ 1
    和数组大小没有联系,和数组结构有联系。

    最简单的例子:[1, 2, 1] ,第一个 while 永远无法跳出。

    讲道理,你这个代码很少见。。。按照维基或者 5 楼的实现一个呗。
    srlp
        13
    srlp  
       2017-02-02 04:53:59 +08:00   ❤️ 1
    按照维基写了一个。楼主写完可以参考一下。

    https://gist.github.com/anonymous/4905e552e6462bee655d8b37aa0c6eaa
    ototsuyume
        14
    ototsuyume  
       2017-02-02 05:42:18 +08:00
    要说思路嘛倒是没错,就是过于繁琐不容易写对,就比如 numbers[i] = numbers[j]这句直接把 numbers[i]的值给写没了,下面那句也是一样
    hxndg
        15
    hxndg  
       2017-02-02 09:33:29 +08:00
    @ototsuyume 。。。话说写没了应该是没问题的。。。最开始的 numbers[i]是那个临时的值,后面每次替换实际上都是有一个临时位置来顶替的
    gejun123456
        16
    gejun123456  
       2017-02-02 11:04:26 +08:00   ❤️ 1
    改了下 可以跑了 楼主可以看下 加了几句

    第一个 else 里的 numbers[i] = numbers[j] 之后 i 要加 1 不然 number[i]总是等于 temp 第二个 while 完全跑不到。


    def quick_sort(numbers,left,right):
    if right-left<=1:
    return numbers
    temp = numbers[left]
    i = left
    j = right-1
    while i<j:
    while numbers[j]>temp and i<j:
    j = j-1
    else:
    if(i==j):
    break;
    numbers[i] = numbers[j];
    i=i+1;
    while numbers[i]<temp and i<j:
    i = i+1;
    else:
    if(i==j):
    break;
    numbers[j] =numbers[i];
    j=j-1;
    numbers[i] =temp;

    https://gist.github.com/gejun123456/7ff1c86e2ab64dc122f08c1ba6023322
    hosiet
        17
    hosiet  
       2017-02-02 14:02:56 +08:00 via Android
    稍微偏个题:建议 UTF-8 编码不要加 BOM 。用处不是很大,也容易造成问题。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4311 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 10:06 · PVG 18:06 · LAX 02:06 · JFK 05:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.