我是一个新手,我需要帮助优化这个SelectionSort()
算法,我已经尝试了使用Python。
def selectionSort(arr,an):
for lastUnsortedInteger in range(an-1,0,-1):
largest = arr.index(max(arr[0:lastUnsortedInteger+1]))
swap(arr,largest,lastUnsortedInteger)
return arr
def swap(arr,ai,aj):
arr[ai],arr[aj] = arr[aj],arr[ai]
if __name__ == '__main__':
an = int(input())
arr = list(map(int,input().strip().split()))
selectionSort(arr,an)
print("Sorted using SelectionSort():\n")
for ai in arr:
print(arr)
发布于 2020-07-02 13:34:37
在StackOverflow上的时候,您似乎已经采纳了一些建议,例如将内部循环更改为max
。但是,这样做的效率很低:
max
,O(n)时间index
,O(n)时间相反,您可以获得索引的max
,使用key
函数比较这些索引的实际值:
largest = max(range(0, lastUnsortedInteger+1), key=arr.__getitem__)
这样,这个步骤只有O(n)时间(对于Python 3)。
其他几点:
an
参数(数组/列表的长度),可以使用len
min
而不是max
。return
,可能会导致用户期望该函数不会修改列表,而是创建排序的副本。arr
不是一个数组,而是一个list
,您可能更喜欢snake_case
而不是camelCase
(毕竟它是"Python“)我的版本:
def selection_sort(lst):
for i in range(len(lst) - 1):
k = min(range(i, len(lst)), key=lst.__getitem__)
lst[i], lst[k] = lst[k], lst[i]
不用说,出于所有实际目的,您应该只使用sorted
或sort
。
https://codereview.stackexchange.com/questions/244877
复制相似问题