算法图解第2章——选择排序

数组和链表

数组：数组的元素带编号，并从0开始；同一个数组中所有元素的类型必须相同；

链表：每一个元素记录了下一个元素的地址，将一系列随机的内存地址串在一起；

• 插入：

链表：具有优势，只需要将新元素放入内存，再将其地址存储到前一个元素中；

数组：插入时需要将后面的元素都向后移；

• 删除

链表：更好的选择，只需要修改前一个元素指向的地址；

数组：还需要将后面的元素都向前移；

• 读取

读取所有元素时，链表的效率很高；

随机读取时，数组的效率高。

选择排序

function findSmall(arr) {
  var smallA = arr[0],
  smallI = 0;

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < smallA) {
      smallA = arr[i]
      smallI = i
    }
  }
  return smallI;
}

function selectionSort(arr) {
  var newArr = [];
  var len = arr.length;
  while (len > 0) {
    var smallI = findSmall(arr);
    var smallA = arr.splice(smallI, 1);
    len -= 1;
    newArr = newArr.concat(smallA)
}
  return newArr;
}

console.log(selectionSort([0, 9, 3, 6, 2]));
//[ 0, 2, 3, 6, 9 ]

单纯的数字排序可以这样做：

function sortNum(a, b) {
  return a - b;
}
console.log([0, 9, 3, 6, 2].sort(sortNum));
//[ 0, 2, 3, 6, 9 ]