基于Python的SelectionSort算法
基于Python的SelectionSort算法
提问于 2020-07-02 13:07:32
我是一个新手，我需要帮助优化这个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)回答 1
Code Review用户
回答已采纳
发布于 2020-07-02 13:34:37
在StackOverflow上的时候，您似乎已经采纳了一些建议，例如将内部循环更改为max。但是，这样做的效率很低：
- 创建列表的一部分，O(n)时间和空间
- 得到切片的
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。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/244877
复制相关文章
相似问题
腾讯云开发者
