算法图解/chap02-选择排序.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第2章 选择排序\n",
    "\n",
    "## 2.2 数组和链表\n",
    "\n",
    "使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。有时候，需要在内存中存储一系列元素。假设你要编写一个管理待办事项的应用程序，为此需要将这些待办事项存储在内存中。\n",
    "\n",
    "现在假设你要添加第四个待办事项，但后面的那个抽屉放着别人的东西！\n",
    "\n",
    "在这种情况下，你需要请求计算机重新分配一块可容纳4个待办事项的内存，再将所有待办事项都移到那里。\n",
    "\n",
    "如果又来了一位朋友，而当前坐的地方也没有空位，你们就得再次转移！真是太麻烦了。同\n",
    "样，在数组中添加新元素也可能很麻烦。如果没有了空间，就得移到内存的其他地方，因此添加\n",
    "新元素的速度会很慢。一种解决之道是“预留座位”：即便当前只有3个待办事项，也请计算机提\n",
    "供10个位置，以防需要添加待办事项。这样，只要待办事项不超过10个，就无需转移。这是一个\n",
    "不错的权变措施，但你应该明白，它存在如下两个缺点。\n",
    "\n",
    "- 你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不了。\n",
    "- 待办事项超过10个后，你还得转移。\n",
    "\n",
    "因此，这种权宜措施虽然不错，但绝非完美的解决方案。对于这种问题，可使用链表来解决。\n",
    "\n",
    "### 2.2.1 链表\n",
    "\n",
    "链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。\n",
    "\n",
    "使用链表时，根本就不需要移动元素。这还可避免另一个问题。假设你与五位朋友去看一部很火的电影。你们六人想坐在一起，但看电影的人较多，没有六个在一起的座位。使用数组时有时就会遇到这样的情况。假设你要为数组分配10 000个位置，内存中有10 000个位置，但不都靠在一起。在这种情况下，你将无法为该数组分配内存！链表相当于说“我们分开来坐”，因此，只要有足够的内存空间，就能为链表分配内存。链表的优势在插入元素方面，那数组的优势又是什么呢？\n",
    "\n",
    "**链表和数组对比：**\n",
    "\n",
    "在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。\n",
    "\n",
    "数组与此不同：你知道其中每个元素的地址。需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问第五个元素。\n",
    "\n",
    "|时间|数组|链表|\n",
    "|--|--|--|\n",
    "|读取|O(1)|O(n)|\n",
    "|插入|O(n)|O(1)|\n",
    "|删除|O(n)|O(1)|\n",
    "\n",
    "**在中间插入**\n",
    "\n",
    "使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。\n",
    "\n",
    "而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素时，链表是更好的选择。\n",
    "\n",
    "**删除**\n",
    "\n",
    "如果你要删除元素呢？链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而\n",
    "使用数组时，删除元素后，必须将后面的元素都向前移。\n",
    "不同于插入，删除元素总能成功。如果内存中没有足够的空间，插入操作可能失败，但在任\n",
    "何情况下都能够将元素删除。\n",
    "\n",
    "**仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1)。**\n",
    "\n",
    "## 2.3 选择排序\n",
    "\n",
    "对于每个乐队，你都记录了其作品被播放的次数。你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢？\n",
    "\n",
    "一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。\n",
    "\n",
    "再次这样做，找出播放次数第二多的乐队。\n",
    "\n",
    "不断重复，直到最后一个。\n",
    "\n",
    "**算法复杂度 $O(n^2)$**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 6, 10]\n"
     ]
    }
   ],
   "source": [
    "#查找数组中的最小数的索引\n",
    "def findMinIndex(array):\n",
    "    min_val = array[0]\n",
    "    min_index = 0\n",
    "    for i in range(1,len(array)):\n",
    "        if array[i] < min_val:\n",
    "            min_val = array[i]\n",
    "            min_index = i\n",
    "    return min_index\n",
    "\n",
    "# 选择排序\n",
    "def selectSort(array):\n",
    "    newArray = []\n",
    "    for i in range(len(array)):\n",
    "        min_val = findMinIndex(array)\n",
    "        newArray.append(array.pop(min_val))\n",
    "    return newArray\n",
    "\n",
    "print(selectSort([5,3,6,2,10]))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (system-wide)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}