选择排序

在此之前先简述两个概念：数组与链表

数组

数组的数据在内存中都是连着的。

假设现在你需要放置4个数据，然而前面三个空着的你放不下，只能往后请求分配一块可容纳4个数据的内存。如果往后不够则需要继续转移。
假设我需要在中间增设一个数据，则需要把该位置后的所有数据向后挪。删除同理。

有一种解决方法，就是提前预留位置，比如，我只有3个数据，但我开辟一个10个位置的空间给你，你只要少于10个都放得下，但有两个缺点：如果超过了还是需要转移；额外的位置用不上，浪费内存。

注意：java 这些强类型语言中，要求数组内所有数据都是同种类型，而 Javascript 没有这限制，但最好还是存放同种类型的数据。

提示

Javascript 不存在数组长度限制，因为Javascript 数组长度是可变的。而 java 在 new 一个数组的时候就已经固定了。

链表

链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列的随机内存地址串在一起。

比如你访问第一个地址时，那里有一张纸条写着“下一个元素的地址为123”。因此，你前往地址123，那里又有一张纸条，写着“下一个元素的地址为847”，以此类推。

而且添加元素时，并不需要移动元素，只需将其放入内存，并将其地址存储到前一个元素中。

两者的区别：

数组——顺序存储，支持顺序访问、随机访问（因为我只需要知道第10个数据的索引即可读取）

链表——随机存储，只支持顺序访问（因为只要访问前一个才知道后一个的地址，比如你要访问第10个数据，你必须先访问前9个）

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

数组的读取速度很快，而链表的插入和删除速度很快。

思考：

假设你要编写一个记账的应用程序。你每天都将所有的支出记录下来，并在月底统计支出，算算当月花了多少钱。因此，你执行的插入操作很多，但读取操作很少。该使用数组还是链表呢？
我们来做一个思考实验。假设Facebook记录一系列用户名，每当有用户试图登录Facebook时，都查找其用户名，如果找到就允许用户登录。由于经常有用户登录Facebook，因此需要执行大量的用户名查找操作。假设Facebook使用二分查找算法，而这种算法要求能够随机访问——立即获取中间的用户名。考虑到这一点，应使用数组还是链表来存储用户名呢？

附：Facebook 实际使用的是链表数组。

选择排序

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到所有排序完成。时间复杂度：O(n ^2)

代码演示：

javascript

// 演示只是实现该算法，并非最优方法，比如 javascript 更好的办法是可以直接使用 sort 来进行排序。
const arr = [6, 10, 2, 5, 3, 1]

// 找出最小的数
function smallest(arr) {
  let smallestCount = arr[0]
  let smallestIndex = 0
  for (let i = 1; i < arr.length; i++) {
    if(smallestCount > arr[i]) {
      smallestCount = arr[i]
      smallestIndex = i
    }
  }
  return smallestIndex
}

// 排序
function sort(arr) {
  const result = []
  let smallestIndex;
  while(arr.length) {
    smallestIndex = smallest(arr)
    result.push(arr[smallestIndex])
    arr.splice(smallestIndex, 1)
  }
  return result
}

console.log(sort(arr));
// 输出：[ 1, 2, 3, 5, 6, 10 ]

选择排序 ​

选择排序 ​

选择排序

选择排序