选择排序

内存工作原理

这里涉及的数据类型为引用类型，计算机就像是很多抽屉的集合体，每个抽屉都有地址，当你往里面存储数据时，计算机会将每个数据存储到各自的“抽屉”去，然后用一个内存地址指向该抽屉，方便你根据内存地址去拿取你所需的值

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

数组和链表

这里只会简单阐述数组和链表的概念，更多会讲述这两种不同数据类型的区别

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

简单来说，链表中的元素可存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。所以，链表的优势在插入元素方面。

当你要往数组插入元素时，计算机要根据数组的长度去寻找一块连续的跟该数组长度相匹配的内存去进行存储，而链表只要存储下个元素的内存地址即可，所以即使链表中的各个数据是分开的不连续的，但还是能通过上一个数据去寻找下个数据的位置。所以在插入数据方面，链表无需考虑其他，直接往内存插入新值即可

这里举个例子，你和两个朋友去看电影，一般来说，你们三个如果关系太好了，好基友那种，分不开了，你们一般会买三张连续座位的票，从而可以坐在一起看，这便是数组，而当没有三张连续的电影票时，你们只能分开看，但可以根据电影票上的座位位置去找你的小伙伴，这便是链表。这里的座位编号便是内存地址，而你们就是一个又一个的数据。

在删除方面：链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移

数组

数组（Array）是有序的元素序列。 [1] 若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。 这些有序排列的同类数据元素的集合称为数组

数组的优势：需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素

两者总结

• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起
• 数组的元素都在一起
• 数组的读取速度比链表快
• 链表的插入和删除速度比数组快
• 在同一个数组中，所有元素的类型都必须相同

选择排序

简介

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

过程

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

具体实现过程

有没有思考过对一组数进行排序时的过程是怎样的

比如要对【1，3，9，5，2】数组进行排序

1. 我们首先在原数组内进行比较，找出最大值，结果是9，所以我们把他放到新建数组第一个位置【9】
2. 接着在剩下的数组遍历找出最大的值，是5，放到新数组第二个位置【9，5】
3. 继续对剩下的三个数字进行同样操作【1，3，2】，得出最终结果【9，5，3，2，1】

这便是选择排序的过程，一共需要几步呢上面，每次都对原数组进行比较排序，需要进行5趟比较，每趟比较又是和另外几个数的比较，也是5次，所以最终的所需的步数是25，也就是n²

随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一 个。既然如此，运行时间怎么还是O(n² )呢

确实，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素 数依次为n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。 但大O表示法省略诸如1/2这样的常数

选择排序实例代码

1. 数组内比较使用一个函数max进行最大值获取，对数组内每个值进行遍历，找出最大值的索引，具体思路如下

   使用变量存储最大值以及最大值索引，给其赋初始值，即为数组第一个数据，接着对数组内数据进行遍历，若遍历到的数据比当前数值大，即将当前变量赋值为它，不断执行该操作，直到遍历完返回该数值索引

2. 对数组进行排序sort的主函数，使用新数组进行存储排序后的值，接着对原数组进行遍历和最大值查找，找出一个便在原数组删除该数据，避免引起无限循环导致内存泄漏，重复执行，直到最终结果出来

优化版

function selectSort(arr) {
  function swap(index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
  }

  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      arr[minIndex] > arr[j] && (minIndex = j);
    }
    swap(minIndex, i);
  }
}