推荐学习书目
› 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
这是一个创建于 2654 天前的主题，其中的信息可能已经有所发展或是发生改变。
#-*- 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
 |
1
iEverX 2017-02-01 18:56:16 +08:00
i+1 -> i + 2
|
 |
2
Newyorkcity OP @iEverX 这样改了之后不会出现不出结果的错误。。但是输出的结果并没有对较大组进行整理。。
|
 |
3
z657386160z 2017-02-01 19:20:28 +08:00
 |
 |
5
czheo 2017-02-01 19:35:46 +08:00
|
|
6
Newyorkcity OP @czheo 也就是说 quick_sort(numbers,i+1,right)这个思路是对的没毛病，真正的错误在函数的具体过程里？
可是为什么对于较小组都能正常排序对于较大组就不能呢。。 |
 |
8
hxndg 2017-02-01 23:00:23 +08:00
讲道理这个问题你只要把数组打出来就可以发现了。
这是第一次遍历，也就是你要处理 3,9 时候的数组 2,1,3,5,8,7,11,5,4 恩，你模拟一下就知道问题出在哪里了 ps 你这个要改的话，，，大概只需要 1s ？ |
|
9
hxndg 2017-02-01 23:01:02 +08:00
我虽然也写 python ，但是我把序号什么的改了一下，不过应该影响不大
|
|
10
hxndg 2017-02-01 23:03:07 +08:00
@z657386160z 表示。。。你虽然图贴的确实能够解决楼主的问题。。。但是一般不一定能看明白到底问题是哪里。。。因为 lz 大方向没错啊。。。
|
 |
12
srlp 2017-02-02 04:31:57 +08:00  1
和数组大小没有联系，和数组结构有联系。
最简单的例子：[1, 2, 1] ，第一个 while 永远无法跳出。 讲道理，你这个代码很少见。。。按照维基或者 5 楼的实现一个呗。 |
|
13
srlp 2017-02-02 04:53:59 +08:00 1
|
 |
14
ototsuyume 2017-02-02 05:42:18 +08:00
要说思路嘛倒是没错，就是过于繁琐不容易写对，就比如 numbers[i] = numbers[j]这句直接把 numbers[i]的值给写没了，下面那句也是一样
|
|
15
hxndg 2017-02-02 09:33:29 +08:00
@ototsuyume 。。。话说写没了应该是没问题的。。。最开始的 numbers[i]是那个临时的值，后面每次替换实际上都是有一个临时位置来顶替的
|
 |
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 |
 |
17
hosiet 2017-02-02 14:02:56 +08:00 via Android
稍微偏个题：建议 UTF-8 编码不要加 BOM 。用处不是很大，也容易造成问题。
|
Select Language