选择排序、快速排序、计数排序、归并排序

选择排序

递归写法

let numbers = [2, 87, 4, 64, 73, 8, 92]
let min = (numbers) => {
    if (numbers.length > 2) {
        return min([numbers[0], min(numbers.slice(1))])
    } 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()
    }

}
sort(numbers)

循环写法

let minIndex = (numbers) => {
    let min = 0
    for (let i = 1; i < numbers.length; i++) {
        if (numbers[i] < numbers[min]) {
            min = i
        }
    }
    return min
}
let swap = (Array, index, i) => {
    let temp = Array[index]
    Array[index] = Array[i]
    Array[i] = temp
}
let sort = (numbers) => {
    for (let i = 0; i < numbers.length - 1; i++) {
        let index = minIndex(numbers.slice(i)) + i
        if (i != index) {
            swap(numbers, index, i)
        }
    }
    return numbers
}

tip

1.所有的递归都可以变为循环

2.swap中要传入参数Array（Array的地址），函数直接对Array进行操作，如果使用swap(numbers[i],numbers[j])只是传的两个值的简单复制，不会对原数组进行修改。

快速排序

let sort = (numbers) => {
    if (numbers.length <= 1) {
        return numbers
    }
    let flagIndex = Math.floor(numbers.length / 2)
    let flag = numbers.splice(flagIndex, 1)[0] //splice后的返回值是数组
    let left = []
    let right = []
    for (let i = 0; i < numbers.length; i++) {
        if (numbers[i] < flag) {
            left.push(numbers[i])
        } else {
            right.push(numbers[i])
        }
    }
    return sort(left).concat([flag], sort(right))
}

归并排序

let sort = (numbers) => {
    if (numbers.length === 1) return numbers
    let middle = Math.floor(numbers.length / 2)
    let left = numbers.slice(0, middle)
    let right = numbers.slice(middle)
    console.log(left, right);
    return merge(sort(left), sort(right))
}
let merge = (a, b) => {
    if (a.length === 0) return b
    if (b.length === 0) return a
    return a[0] > b[0] ? [b[0]].concat(merge(a, b.slice(1))) : [a[0]].concat(merge(a.slice(1), b))
}

计数排序

let sort = (numbers) => {
    let hashTable = {},
        max = 0,
        result = []
    for (let i = 0; i < numbers.length; i++) {
        if (numbers[i] in hashTable) {
            hashTable[numbers[i]] += 1
        } else {
            hashTable[numbers[i]] = 1
        }
        if (numbers[i] > max) max = numbers[i]
    }
    for (let j = 0; j < max; j++) {
        if (j in hashTable) {
            for (let i = 0; i < hashTable[j]; i++) {
                result.push(j)
            }
        }
    }
    return result
}