插入算法

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具有n个元素时它需要经过n-1趟排序。对于p = 1到p = n-1趟，插入排序保证从位置0到位置p上的元素为已排序状态。它就是基于这个事实来排序的。

function insertionSort(arr){
  //如果数组的长度小于等于1，直接返回数组
  if (arr.length <= 1) return arr;
  //遍历数组
  for (var i = 0; i < arr.length; i++){
    //取到当前数值，往前查找，看时候有比该数值大的数
    for(var j = i-1; j >=0; j--){
      //如果存在下标小的数大于下标大的数
      if (arr[i] < arr[j]){
        //交换两个数字的位置
        var temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
      }
    }
  }
  return arr;
}

最好的情况只需要 n-1 次操作完成，最坏则需要 n(n-1)/2 次。插入算法的时间复杂度为 O(n^2) 。因而插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，插入排序还是一个不错的选择。

冒泡排序

冒泡排序与插入排序拥有相等的运行时间。但是两种算法在需要的交换次数却有很大的不同。在最好的情况，冒泡排序需要 O(n^2) 次，而插入排序只要最多 O(n) 次。冒泡排序如果能在内部循环第一次运行时，使用一个 flag 来表示有无交换的可能，也可以把最好的复杂度降低到 O(n) 。在这个情况下，已经排好的数列就无交换的必要了。

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

function bubleSort(arr) {
  //如果数组的长度小于等于1，直接返回数组
  if (arr.length <= 1) return arr;
  var flag = false; //设置 flag 记录是否已经排序完成，降低复杂度
  //从第一个数开始遍历数组
  for (var i = 0; i < arr.length; i++){
    //每完成一次外循环，内循环遍历次数就少一次
    for (var j = 0; j < arr.length - i; j++){
      //如果前一个数大于后一个数就进行位置交换
      if (arr[j] > arr[j+1]){
        var temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
        flag = true; //有交换时 flag 就为true
      }
    }
  //判断是否进行了位置交换，如果没有则排序完成
  if (！flag) return arr;
  }
}

选择排序

选择排序是一中简单直观的排序算法。它的工作原理如下：
首先在未排序序列中找到最小（大）元素，存放到序列的起始位置，然后，再从剩余未排序的元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直至完成排序。
选择排序的主要有点与数据移动有关。如果某个元素位于正确的最终位置上，那么它将不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终的位置上，一次对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

复杂度分析
选择排序的交换操作介于 0 和 n-1 次之间。比较操作为 n(n-1)/2 次。赋值操作介于 0 和 3(n-1) 次之间。比较次数时间复杂度为 O(n^2)，标胶次数与关键字的初始状态无关，总次数为 n(n-1)/2 。交换次数 O(n)，最好的情况是已经有序，交换0次，最坏的情况是逆序，交换 n-1 次。
交换次数比冒泡排序次数少，由于交换所需 CPU 时间比比较操作所需 CPU 时间多，n 值较小时，选择排序比冒泡排序快。
原地操作几乎是选择排序的唯一有点，当空间复杂度要求较高时，可以考虑选择排序，实际适用的场合非常罕见。

function selectionSort(arr) {
  //如果数组的长度小于等于1，直接返回数组
  if (arr.length <= 1) return arr;
  //遍历数组
  for (var i = 0; i < arr.length; i++){
    var min = i; //设置已排列序列末尾的下标
    //遍历未排列的序列并找出最小值
    for (var j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j]){
        var temp = arr[min]
        arr[min] = arr[j];
        arr[j] = temp;
        min = j; //更新已排列序列末尾值的下标
      }
    }
  }
  return arr;
}

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

从数列中挑出一个元素，称为“基准”(pivot)
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准值后面（相同的数可以在任意一边）。在这个分区结束后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排列。
递归的最底部情形，就是这个数列的长度小于等于1，也就是已经被排好了。虽然一直会递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它的最终位置上。

正如它的名字，快速排序是在时间中最快的已知排序算法，它的时间复杂度为 O(nlogn)。

由于对枢纽元的处理会导致第三步中的分割不为已，因此，我们希望把等于枢纽元的大约一半的关键字分到左边，另外一半分到右边。我们可以采用 Math.floor(arr.length /2) 来得到数组大约一半的这个数值的索引。

function quickSort(arr) {
  //如果数组的长度小于等于1，直接返回数组
  if (arr.length <= 1) return arr;
  //获取基准的索引
  var pivotIndex = Math.florr(arr.length/2);
  //将基准数从数组中单独提取出来
  var pivot = arr.splice(pivotIndex, 1)[0];
  //定义左边和右边两个子序列
  var left = [];
  var right = [];
  //遍历当前序列
  for (var i = 0; i < arr.length; i++){
    //如果数值比基准小，放在左边的子序列
    if (arr[i] <= pivot){
      left.push(arr[i]);
    }
    //如果数值比基准大，放在右边的子序列
    else{
      right.push(arr[i]); 
    }
  }
  //递归排序
  return quickSort(left).concat([pivot], quickSort(right))
}