带有负数的 Python 排序列表 [英] Python sorting list with negative number
问题描述
为了通过实践学习python,我正在尝试使用python实现和测试快速排序算法.
In attempt to learn python by practicing, I am trying to implement and test out quick sort algorithm using python.
实现本身并不难,但是排序的结果有点令人费解:
The implementation itself was not difficult, however the result of the sort is somewhat puzzling:
当我对列表进行排序时
['35', '-1', '-2', '-7', '-8', '-3', '-4', '20', '-6', '53']
['35', '-1', '-2', '-7', '-8', '-3', '-4', '20', '-6', '53']
结果给了我
['-1', '-2', '-3', '-4', '-6', '-7', '-8', '20', '35', '53']
['-1', '-2', '-3', '-4', '-6', '-7', '-8', '20', '35', '53']
因此列表已排序,但负整数以相反的顺序排序.
So the list is sorted however the negative integers are sorted in reverse order.
我怀疑这可能是我正在对从文件中读取的整数列表进行排序这一事实的问题,而 int 的类型实际上不是 int 而是其他东西(也许是字符串).我能怎么办?怎么解决这个问题?
I suspect this may be the problem with the fact that I am sorting a list of ints read in from a file, and the type of the int is actually not int but something else (string, perhaps.) What could I possibly do to fix this problem?
这里是快速排序的实现代码
here is the code for the quicksort implementation
#quicksort -> the conquer part of the algorithm
def quicksort(input_list, start_index, end_index):
if start_index < end_index:
#partition the list of integers.
pivot = partition(input_list, start_index, end_index)
#recursive call on both sides of the pivot, that is excluding the pivot itself
quicksort(input_list, start_index, pivot-1)
quicksort(input_list, pivot+1, end_index)
return input_list
#divide part of the algorithm
def partition(input_list, start_index, end_index):
#declare variables required for sorting
pivot = input_list[start_index]
left = start_index + 1
right = end_index
sorted = False
while not sorted:
#break condition so that left index is crossed with right index
#or if the value of left crosses the pivot value
while left <= right and input_list[left] <= pivot:
#increment left index
left = left + 1
#break the loop when right and left indexes cross
#or if the right value crosses the pivot value
while right >= left and input_list[right] >= pivot:
right = right-1
if right < left:
sorted = True
else:
#swap places for left value and the right value cause they are not in order
temp = input_list[left]
input_list[left] = input_list[right]
input_list[right] = temp
#swap the value at start index with what's now at the right half. Then return right for the new pivot
temp = input_list[start_index]
input_list[start_index] = input_list[right]
input_list[right] = temp
return right
感谢任何帮助.感谢大家的时间和帮助.
Any help is appreciated. Thank you all for your time and help.
推荐答案
您的代码运行正常,因为字符串按字典顺序排序(按第一个字符排序,如果第一个匹配则按第二个字符,如果第二个匹配则按第三个字符排序,等等).如果您想按数字排序,最简单的方法是修复您的 list
使其实际上是 int
值:
Your code is behaving correctly, since strings sort lexicographically (by first character, then second if first matches, then third if second matches, etc.). If you want to sort numerically, the easiest way is to fix up your list
so it's actually int
values:
# Possibly read from file as list of string
strlist = ['35', '-1', '-2', '-7', '-8', '-3', '-4', '20', '-6', '53']
intlist = map(int, strlist) # list(map(int, strlist)) on Python 3
quicksort(intlist)
如果需要,您可以在之后转换回 str
.否则,您的替代方案是实现对 key
函数的支持(允许您根据计算值对值进行排序),例如 list.sort
/sorted
,但这可能比您现在要处理的更复杂.
You could convert back to str
afterwards if needed. Otherwise, your alternative is to implement support for a key
function (that lets you sort values on a computed value) like list.sort
/sorted
, but that's probably more complex that you want to deal with right now.
这篇关于带有负数的 Python 排序列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!