选择排序

数组与链表，第一种排序算法

数组和链表

内存在计算机中就像是一组抽屉，每一个抽屉都有一个唯一的标识----内存地址。当需要存储多项数据时，有两种基本方式----数组和链表。

数组

使用数组意味着所有的元素在内存中的存储是相连的，如果新增一个元素时，没有足够的连续空间，那么必须整体转移到一块更大的连续空间。这样的开销是巨大的，一种权宜之计是提前声明一块较大的空间。比如，即便当前只有三个元素，也向计算机申请10个内存单元。这样，只要元素不超过10个，那么就无需转移。但你要明白，这样做有两个缺点：

数组中额外申请的空间可能根本连用不上，造成内存浪费；
当元素超过初始申请数量时，还是不可避免的需要转移。

链表

链表中的元素可以存储在内存中的任何地方。链表的每个元素都存储了下个元素的地址，从而使一系列随机的内存地址串在一起，不存在像数组那样需要转移的情况。

同样链表也有自己的缺点，当需要同时读取所有数据时，可以从链表的第一个元素，按图索骥，不断的获取下一个元素的位置，直到最后一个。但如果需要随机的访问某个元素时，链表的弊端便显露无疑，它需要挨个访问以获取内存地址信息，性能低下。反之，如果需要随机地读取元素，数组的效率很高，因为数组在内存中的存储是连续的，所以根据第一个元素的内存地址和目标元素的索引，可以迅速推算出要读取的内存地址。

插入与删除

如果在中间插入元素，数组和链表哪个更好呢？对于链表，插入元素很简单，只需要修改它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，还需要将整个数组复制到其他地方。所以对于插入来讲，链表更优。

对于删除元素，链表也是更好的选择，因为只需要修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。不同于插入，删除元素总能成功。因为如果内存中没有足够空间，插入操作可能失败。

小结

以上，数组读取速度很快，链表的插入、删除很快。需要指出的是，仅当能够立即访问要删除的元素时，链表删除操作的运行时间才为O(1)。通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素的运行时间是O(1)。

实质上，数组和链表在使用上的最大不同，就是数组支持随机访问，链表只支持顺序访问。在实际应用中，我们很多情况需要数据结构具有随机访问的能力，所以，事实上数组更常用些。

选择排序

现在我们要对一个播放列表，按照播放次数进行排序。遍历这个列表，找出播放次数最多的乐队，并将该乐队添加到一个新的列表中。然后继续遍历剩下的列表，并找出最大项作为结果序列的第二名。

如果我们将每次查看列表中的一个元素看做是一次操作。那么将会每次遍历n个元素，找出相对大值，一共遍历n次，才能为所有的元素在新的有序列表中找到正确的位置。这样，需要总的运行时间应该是 $O(n \times n)$ ，即 $O(n^2)$ 。

根据上图可以看到，需要遍历的元素越来越少，第一次需要遍历n个元素，随后需要遍历n-1，n-2，·····，2，1。平均每次遍历的元素数是 $\frac{1}{2} \times n$ ，因此运行时间应该为 $O(n \times \frac{1}{2} \times n)$ 。但大O表示法省略诸如 $\frac{1}{2}$ 这样的常数。

Python示例代码

选择排序

# 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_index = i
      smallest = arr[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]))

上一页算法简介

最后更新于5年前