选择排序

Question

本章内容：

学习两种最基本的数据结构——数组和链表。
学习第一种排序算法。本章将介绍选择排序。

内存的工作原理

需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。

链表的优势在插入元素方面。数组的优势在于读取元素方面。

数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它支持随机访问。

你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢？一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。
要找出播放次数最多的乐队，必须检查列表中的每个元素。正如你刚才看到的，这需要的时间为 O(n)。因此对于这种时间为 O(n) 的操作，你需要执行 n 次。

需要的总时间为 O(n × n) ，即 O(n^2) 。

选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为 O(n log n)，这将在下一章介绍。

小结

• 计算机内存犹如一大堆抽屉。
• 需要存储多个元素时，可使用数组或链表。
• 数组的元素都在一起。
• 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
• 数组的读取速度很快。
• 链表的插入和删除速度很快。
• 在同一个数组中，所有元素的类型都必须相同（都为 int、double 等）。

选择排序示例代码（Python 2 版本）

# Finds the smallest value in an array
def findSmallest(arr):
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest = arr[i]
      smallest_index = i
  return smallest_index

# Sort array
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # Finds the smallest element in the array and adds it to the new array
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

print selectionSort([5, 3, 6, 2, 10])