5.8.选择排序 - Python 数据结构

返回介绍

5.8.选择排序

发布于 2019-08-07 字数 1392 浏览 876 评论 0

5.8.选择排序

选择排序改进了冒泡排序,每次遍历列表只做一次交换。为了做到这一点,一个选择排序在他遍历时寻找最大的值,并在完成遍历后,将其放置在正确的位置。与冒泡排序一样,在第一次遍历后,最大的项在正确的地方。 第二遍后,下一个最大的就位。遍历 n-1 次排序 n 个项,因为最终项必须在第(n-1)次遍历之后。

Figure 3 展示了整个排序过程。在每次遍历时,选择最大的剩余项,然后放置在其适当位置。第一遍放置 93,第二遍放置 77,第三遍放置 55 等。 该函数展示在 ActiveCode 1 中。

5.8.选择排序.activecode1

Activecode 1

def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

你可能会看到选择排序与冒泡排序有相同数量的比较,因此也是 $$O(n^2)$$。 然而,由于交换数量的减少,选择排序通常在基准研究中执行得更快。 事实上,对于我们的列表,冒泡排序有 20 次交换,而选择排序只有 8 次。

上一篇:5.7.冒泡排序

下一篇:5.9.插入排序

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

目前还没有任何评论,快来抢沙发吧!