排序算法

• 冒泡排序
  • 当前项和后一项进行比较，每一轮比较，当前最大的可以放到末尾
  • 一轮轮比较，每一轮都从第一项开始，拿出当前项a和后一项b比较，如果a>b那么两者交换位置

var array = [12,8,24,16,1]
function bubble(array){
    var temp = null;
    for(let i = 0;i < array.length-1; i++){
        for(let j = 0;j< array.length-1-i;j++){
            if(array[j] > array[j+1]){
                temp = array[j+1]
                array[j+1] = array[j]
                array[j] = temp
            }
        }
    }
    return array;
}

//或者用ES6中解构赋值进行变量交换也可以,即：[array[j],array[j+1]] = [array[j+1],array[j]]

• 插入排序
  • 类似于玩扑克:新抓的牌比大小，大放到后面
  • 依次取出，依次从后往前比，插入
    • 新取的比后面大，那么就放到后面
    • 如果比到第一个那么就unshift放到开头

var array = [12,8,24,16,1];
function insert(array){
    let handle = [];    
    handle.push(array[0])
    for(let i = 0;i < array.length;i++){
        for(let j = handle.length-1;j < handle.length;j--){
            let A = array[i]
            let B = handle[j]
            if(A>B){
                handle.splice(j+1,0,A)    
                break;
            }
            if(j === 0){
        handle.unshift(A)    //比到最前面一项，直接放到最前面
            }
        }
    }
}

注意：splice() 方法向/从数组中添加/删除项目，然后返回被删除的项目。语法arrayObject.splice(index,howmany,item1,.....,itemX)。index必需。整数，规定添加/删除项目的位置，使用负数可从数组结尾处规定位置。howmany：必需。要删除的项目数量。如果设置为 0，则不会删除项目。item1, ..., itemX可选。向数组添加的新项目。

• 快速排序
  • 拿出数组中中间项，然后和剩下的比较，小的放左边，大的放右边。没有则不再处理

var array = [12,8,24,16,1];
function quick(array){
    if (array.length <= 1)return array;
    //1、找到数组的中间项，并且在原数组中把它移除
    let middleIndex = Math.floor(array.lenght/2)    //选择中间元素的index
    let middleValue = array.splice(middleIndex,1)[0]        //得到中间元素的值并且在原数组中删除中间元素

    //2、创建两个数组分别存储左边的和右边的数组
    let leftArr,rightArr = [];
    for(let i = 0;i < array.length;i++){
        array[i]<middleValue?leftArr.push(array[i]):rightArr.push(array[i])

        //3、递归方式让左右两边持续这样处理，一直到左右两边处理完成没有为止
        return quick(leftArr).concat(quick(rightArr))
    }
}

快排性能最好