首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >基于Python的SelectionSort算法

基于Python的SelectionSort算法
EN

Code Review用户
提问于 2020-07-02 13:07:32
回答 1查看 41关注 0票数 3

我是一个新手,我需要帮助优化这个SelectionSort()算法,我已经尝试了使用Python。

代码语言:javascript
运行
复制
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)
EN

回答 1

Code Review用户

回答已采纳

发布于 2020-07-02 13:34:37

在StackOverflow上的时候,您似乎已经采纳了一些建议,例如将内部循环更改为max。但是,这样做的效率很低:

  • 创建列表的一部分,O(n)时间和空间
  • 得到切片的max,O(n)时间
  • 得到该元素的index,O(n)时间

相反,您可以获得索引的max,使用key函数比较这些索引的实际值:

代码语言:javascript
运行
复制
largest = max(range(0, lastUnsortedInteger+1), key=arr.__getitem__)

这样,这个步骤只有O(n)时间(对于Python 3)。

其他几点:

  • 不需要an参数(数组/列表的长度),可以使用len
  • 在我看来,从第一个索引到最后一个索引的循环比较简单,因此使用min而不是max
  • 由于交换现在是单行,并且只使用过一次,所以我们可以直接将其内联到排序函数中。
  • 该函数就地修改列表,因此不需要return,可能会导致用户期望该函数不会修改列表,而是创建排序的副本。
  • 从技术上讲,arr不是一个数组,而是一个list,您可能更喜欢snake_case而不是camelCase (毕竟它是"Python“)

我的版本:

代码语言:javascript
运行
复制
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]

不用说,出于所有实际目的,您应该只使用sortedsort

票数 4
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/244877

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档