《图解算法》第2章 选择排序

第2章 选择排序

数组是个重要的主题，一定要高度重视！很多算法仅在数据经过排序后才管用

内存工作原理

• 需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。但它们并非都适用于所有的情形，因此知道它们的差别很重要

数组和链表

有时候，需要在内存中存储一系列元素。假设你要编写一个管理待办事项的应用程序，为此需要将这些待办事项存储在内存中 使用数组意味着所有待办事项在内存中都是相连的。现在假设你要添加第四个待办事项，但后面的那个抽屉放着别人的东西！你需要重新请求计算机重新分配一块可容纳4个待办事项的内存，再将所有待办事项都移到那里

• 一种解决之道是“预留座位”：即使当前只有3个待办事项，也请计算机提供10个位置，以防需要添加待办事项。它存在两个缺点

1. 你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不了
2. 待办事项超过10个后，你还得转移

链表

• 链表中的元素可存储在内存的任何地方

• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起

• 只要有足够的内存空间，就能为链表分配内存

数组

• 需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低
• 需要阳春面地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素

术语

元素的位置称为索引 数组和链表操作的运行时间

在中间插入

• 使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址
• 使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素时，链表是更好的选择

删除

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

• 数组用得很多，因为它支持随机访问。有两种访问方式

1. 随机访问：
2. 顺序访问：从第一个元素开始逐个读取元素；链表只能顺序访问，要读取链表第十个元素，得先读取前九个元素，并沿链接找到第十个元素

假设Facebook使用的是一种混合数据：链表数组。这个数组包含26个元素，每个元素都指向一个链表。这种新数据结构的查找和插入速度更快还是更慢？

选择排序

• 选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为O（n log n）

class SelectionSort
{

    public static function sort($array) {
        $length = count($array);
        foreach ($array as $outerIndex => $item) {
            $minIndex = $outerIndex;
            for ($innerIndex = $outerIndex + 1; $innerIndex < $length; $innerIndex ++) {
                if ($array[ $minIndex ] > $array[ $innerIndex ]) {
                    $minIndex = $innerIndex;
                }
            }
            $temp = $array[ $outerIndex ];
            $array[ $outerIndex ] = $array[ $minIndex ];
            $array[ $minIndex ] = $temp;
        }

        return $array;
    }

}

$array = [5, 3, 6, 2, 10];
echo join(SelectionSort::sort($array), ',') . PHP_EOL;

// 输出：2,3,5,6,10