常用数组排序

本文主要汇总一维数组排序相关的方法，以升序为例。

一、冒泡排序

步骤： 1、两个for遍历，使用两个指针，外循环i指针，内循环j指针 2、对比两个指针指向的元素大小，如果i>j,则进行值交换

代码如下：

let bubbleSort = function (arr) { 

    //双指针
  for(let i = 0; i<arr.length; i++) {
    for(let j = i+1 ; j<arr.length;j++)
    if(arr[i] > arr[j]){
      let t = arr[i]
      arr[i] = arr[j]
      arr[j] = t
    }
  }

  return arr
}

二、快速排序

步骤： 1、如果数组长度小于等于0则返回该数组 2、先提取中间值，把小于中间值的元素放在左数组，其他的放在右数组 3、递归重复第二步，用Array.prototype.concat合并数组

代码如下：

let quickSort = function (arr) { 
    if(arr.length <= 0 ) {
        return arr
    }
    let midIdx = Math.floor(arr.length / 2)
    let mid = arr.splice(midIdx, 1)[0]
    let left = []
    let right = []

    for(let i = 0; i<arr.length; i++) {
        if(arr[i] <mid){
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }

    return quickSort(left).concat([mid],quickSort(right))
}

三、插入排序

步骤： 1、遍历数组 2、保存当前i指针指向的元素，用prev指针来遍历当前对象之前的元素 3、前一元素大于当前元素时，把较大值后移一个，与再前一项去对比，找到比当前元素小的元素时停止 4、将prev指针指向当前元素

代码如下：

let insertSort = function (arr) {
  let current , prev

  for(let i = 1; i<arr.length ; i++) {
    current = arr[i]
    prev = i -1
    while(prev >= 0 && current<arr[prev]) {
      arr[prev+1] = arr[prev]
      //prev指针前移
      prev--
    }

    arr[prev+1] = current
  }
  return arr;
}

四、es6方法

sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。

要比较数字而非字符串，比较函数可以简单的以 a 减 b，如下的代码将会将数组升序排列

function sort(arr) {
    if(arr.length <= 0){
        return arr
    }

    return arr.sort((a,b)=>a-b)
}