1.冒泡排序

• 冒泡排序思想就是从第一个元素开始往后逐个比较比谁大了，就和他换位置，每一轮都保证了最大的数在后面

function bubleSort(arr) {
  let len = arr.length;
  let temp;
  for(let i = 0;i<len;i++) {
    for(let j = i+1;j<len;j++){
      if(arr[i]>arr[j]){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp
      }
    }
  }
  return arr
}

temp是比较常用的交换变量，在ES6中有更简便的

function bubleSort(arr) {
  let len = arr.length;
  for(let i = 0;i<len;i++) {
    for(let j = i+1;j<len;j++){
      if(arr[i]>arr[j]){
        [arr[i],arr[j]] = [arr[j],arr[i]]
      }
    }
  }
  return arr
}

2.选择排序

• 从数组头部开始，第一个元素和其他元素比较，将最小的放第一个
• 接下来从第二个，直到最后一个
• 外层循环的i表示第几轮，arr[i]就表示当前轮次最靠前(小)的位置；
• 内层从i开始，依次往后数，找到比开头小的，互换位置即可

function chooseSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i; j < len; j++) {
      if (arr[j] < arr[i]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
  return arr
}

3.插入排序

• 首先将待排序的第一个记录作为一个有序段
• 从第二个开始，到最后一个，依次和前面的有序段进行比较，确定插入位置

4.快速排序（重点）

• 选择一个基准元素，将列表分割成两个子序列；
• 对列表重新排序，小于基准放前面，大于基准放后面
• 分别比较较小子元素序列和较大元素序列，重复上面操作

function quickSort(arr) {
  // 递归出口
  if(arr.length<=1){
    return arr
  }
  let left = [];
  let right = [];
  current = arr.splice(0,1)
  for(let i = 0;i<arr.length;i++) {
    if(arr[i]<current) {
      left.push(arr[i])
    }else {
      right.push(arr[i])
    }
  }

  return quickSort(left).concat(current,quickSort(right)); 
}

4.快速排序

• 从序列中选择一个轴点元素，一般从第0个开始。
• 利用轴点元素将序列分割成两个子序列，小的左边，大的放右边，等于的话，随意。
• 分割完有两个子序列，对他们进行同样的操作
• 每一个元素都转换成轴点元素，那么排序就完成了。

5.希尔排序

• 将数组分成若干列
• 一般是 n/2^k 列