5.8.选择排序

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

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

5.8.选择排序.activecode1

Activecode 1

  1. def selectionSort(alist):
  2. for fillslot in range(len(alist)-1,0,-1):
  3. positionOfMax=0
  4. for location in range(1,fillslot+1):
  5. if alist[location]>alist[positionOfMax]:
  6. positionOfMax = location
  7. temp = alist[fillslot]
  8. alist[fillslot] = alist[positionOfMax]
  9. alist[positionOfMax] = temp
  10. alist = [54,26,93,17,77,31,44,55,20]
  11. selectionSort(alist)
  12. print(alist)

你可能会看到选择排序与冒泡排序有相同数量的比较,因此也是

 5.8.选择排序  - 图2。 然而,由于交换数量的减少,选择排序通常在基准研究中执行得更快。 事实上,对于我们的列表,冒泡排序有 20 次交换,而选择排序只有 8 次。