算法第二章：选择排序

第二章：选择排序

• 本章学习数组与链表两种基础数据结构，以及排序算法。
• 了解它们的优缺点，可针对不同算法选择合适的数据结构。
• 选择排序是快速排序的基石，理解选择排序有助于理解快速排序。

知识储备

• 需要理解大O表示法和对数，相关知识在第一章。

2.1 内存的工作原理

• 计算机内存类似于有很多抽屉的柜子，每个抽屉都有地址。
• 存储数据时，计算机会提供一个存储地址。

2.2 数组和链表

• 数组和链表是存储多项数据的两种基本方式。
• 数组：
  • 数组内的元素在内存中是相连的。
  • 数组添加新元素很慢，因为可能需要移动到其他内存。
  • 一种解决办法是“预留座位”，但存在浪费内存，以及预留座位不够用的缺点。
• 链表：
  • 链表中的元素可存储在内存的任何地方。
  • 链表的每个元素都存储了下一个元素的地址。
  • 不需要移动元素，但是要从头开始查找。

2.2.2 数组

• 链表的优势在插入元素方面，数组的优势是可以跳跃读取，速度快。知道其中每个元素的地址，例如，假设有一个数组，它包含五个元素，起始地址为00，那么元素#5的地址是04。只需执行简单的数学运算就知道：04。

2.2.3 术语

• 数组元素带编号，从0开始，元素的位置称为索引。
• 数组读取速度快，链表插入/删除速度快。

2.2.4 在中间插入

• 链表插入元素很简单，只需修改它前面的那个元素指向的地址，而使用数组时，则必须将后面的元素都向后移。

2.2.5 删除

• 删除元素：链表只需修改前一个元素指向的地址。数组则必须将后边的元素都向前移。

2.3 选择排序

• 选择排序：遍历列表，找出最大（或最小）的元素，将其添加到新列表中。
• 简单排序使用了n次，每次都检查列表中的每个元素，所需时间为O(n)。
• 找出最大或最小的元素的时间为O(n)。
• 选择排序的总时间为O(n*n)，即O(n²)。

需要检查的元素数越来越少

• 每次需要检查的元素数逐渐减少，平均每次检查的元素数为 1/2 * n。
• 运行时间实际上是 O(n × 1/2 × n)，但大O表示法省略常数，因此还是 O(n²)。
• 更快的排序算法是快速排序，运行时间为O(n log n)。

2.4 小结

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