算法入门之sort排序算法

要实现排序算法，首先我们需要一些前置条件。比如求出一个数组的最小值。

求出数组的最小值

minOf2的实现

//两个数找出比较小的那个
let minOf2 = (numbers) => {
    if (numbers[0] < numbers[1]) {
        return numbers[0]
    } else {
        return numbers[1]
    }
}

可以用析构赋值来进行优化

let minOf2 = ([a, b]) => a < b ? a : b//析构赋值

求任意长度的数组的最小值min

我们已经知道了如何求两个数的最小值，那么求三个数呢？

let minOf3 = ([a,b,c])=>{
    return minOf2([a,minOf2([b,c])])
}

由此我们可以推理，求任意长度的数组的最小值，我们都可以通过minOf2解决
现在我们来尝试求任意长度数组的最小值
我们运用到一个递归的思想

let min = (numbers)=>{
    if(numbers.length>2){
        return min([numbers[0],min(numbers.slice(1))])//把第一项单独和后面几项的最小值去做min()
    }else {
        return Math.min.apply(null,numbers)
    }
}

或者使用JS内置的APIMath.min

//JS内部有现成的API Math.min
Math.min(1,2)
Math.min.call(null,1,2)
Math.min.apply(null,[1,2])

sort排序算法实现正整数从小到大排列

实现思路：

• 递归实现
• 循环实现

我们还是按照求最小值的方法，先从两个数排序开始
let sort2 = ([a,b])=>a<b? [a,b]:[b,a]
如果是长度为三的数组进行排序

//长度为3的数组排序
let minIndex= (numbers)=>{
    numbers.indexOf(min(numbers))
}//求出最小数字的下标
let sort3 = (numbers)=>{
    let index = minIndex(numbers)
    let min = numbers[index]
    numbers.splice(index,1)//从index出删除一个
    return [min].concat(sort2(numbers))
}

所以我们推导对任意长度的数组的排序算法

let minIndex = (numbers) =>
    numbers.indexOf(min(numbers))

为了方便起见，我们对最小值进行一个标记

//任意长度的数组
let min = (numbers)=>{
    if(numbers.length>2){
        return min([numbers[0],min(numbers.slice(1))])//把第一项单独和后面几项的最小值去做min()
    }else {
        return Math.min.apply(null,numbers)
    }
}
let minIndex = (numbers) =>
    numbers.indexOf(min(numbers))
let sort = (numbers)=>{
    if(numbers.length>2){
        let index = minIndex(numbers)
        let min = numbers[index]
        numbers.splice(index,1)
        return [min].concat(sort(numbers))
    }else{
        return numbers[0]<numbers[1]? numbers :numbers.reverse()
    }
}

即可实现对于任意长度的正整数数组进行排序