数组排序

1、选择排序

• 首先在未排序数组中找到最小(大)元素，存放在数组的起始位置。
• 再从剩余数组元素中继续寻找最小(大)元素，返回放在已排序数组的末尾

function sort1(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = i + 1; j < arr.length; j++) {
      //如果第一个比第二个大，就交换他们两个位置
      if (arr[i] > arr[j]) {
        ;[arr[j], arr[i]] = [arr[i], arr[j]]
      }
    }
  }
  return arr
}

2、冒泡排序

• 依次比较两个相邻的数，如果不符合规则互换位置，一次比较就能够将最大或最小的值放在数组最后一位
• 继续对除【最后一位】之外的所有元素重复上述过程

function sort2(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    //每一轮比较要比多少次
    for (var j = 0; j < arr.length - 1 - i; j++) {
      //如果第一个比第二个大，就交换他们两个位置
      if (arr[j] > arr[j + 1]) {
        ;[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
      }
    }
  }
  return arr
}

3、插入排序

• 将数组第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
• 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

function sort3() {
  var preIndex, current
  for (var i = 1; i < arr.length; i++) {
    preIndex = i - 1
    current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}

4、快速排序

• 在已知数据集合中随便去一个基准(pivot)
• 将其余数据以基准为中心，大于分放右边，小于的放左边
• 将左右两个子集重复以上两个步骤

function quickSort(arr) {
  //递归终止条件
  if (arr.length <= 1) {
    return arr
  }
  //取基准
  var midIndex = Math.floor(arr.length / 2)
  var mid = arr.splice(midIndex, 1)[0]
  //分左右
  var leftArr = []
  var rightArr = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] > mid) {
      rightArr.push(arr[i])
    } else {
      leftArr.push(arr[i])
    }
  }
  return [...quickSort(leftArr), mid, ...quickSort(rightArr)]
}