排序算法

如何找出两个数中较小的一个

必备知识

  • 数据结构
    • 用数组[a,b]表示两个数字
    • JS中没有二元组，用数组代替
  • 编程知识：A?B:C表达式

minOf2 的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

//思路
let minOf2_draft = (numbers) => {
    if(numbers[0] < numbers[1]){
        return number[0]
    }else{
        return number[1]
    }
}
//优化
let minOf2_draft2 = numbers => numbers[0]<numbers[1]? numbers[0]:numbers[1]
//继续简化
let minOf2 = ([a,b]) => a<b?a:b

let minOf2 = ([a,b]) => a<b?a:b的写法叫析构赋值，先把结构拆开，依次赋值

调用

1
2
3

let minOf2 = ([a,b]) => a<b?a:b
minOf2([1,2]) // 1 小白调用法
minOf2.call(null,[1,2]) // 熟手调用法

算法就是把你解决问题的思路用代码表示出来

现成的API

JS内置Math.min
1
2
3

Math.min(1,2)
Math.min.call(null,1,2)
Math.min.apply(null,[1,2])
关于Math
  • 看起来Math像Object一样是构造函数，但不是，没有函数的共用属性
  • 实际上Math只是一个普通的内置对象
  • 这是目前（2020）唯一的特例：首字母大写是构造函数

minOf3 的实现

把两个数升级为三个数之间的比较，从三个数找出最小的那个

1
2
3
4
5
6
7
8
9

// 思路
let minOf2 = ([a,b]) => a<b?a:b
let minOf3_draft = ([a,b,c]) => {
    return minOf2([minOf2([a,b]),c])
}
// 先把较小的放在前面
let minOf3 = ([a,b,c]) => {
    return minOf2([a,minOf2([b,c])])
}

推理

  • minOf4
1
2
3

let minOf4 = ([a,b,c,d]) => {
    return minOf2(a,minOf3([b,c,d])) // 再次调用，并非递归
}
  • minOfN -> minOf(N-1) -> … -> minOf2([b,c])
  • 推广：任意长度数组求最小值，都可以通过minOf2，最终实现

min 的实现

找出数组中最小值

1
2
3
4
5

let getMin = (numbers) => {
    return getMin(
    [numbers[0],getMin(number.slice(1))]
    )
}
  • 求最小值，最终还是两两（数组）元素之间比较大小
  • 二元法分拆：取出第一个元素；去掉第一个元素后的新数组arr.slice(1)
  • 对新数组再次进行二元法分拆
  • 最终只剩两个元素，返回较小值，和最近一次分拆的元素再次比较
  • 直至和原始数组的第一个元素比较，最终返回的值即为数组的最小元素
  • [numbers[0], getMin(numbers.slice(1))]
  • 去掉数组第一项numbers.slice(1)后，并经过比较大小的数比较
  • 代码会死循环，不停调用自己，需要添加一个终止条件
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 设置终止条件
let getMin = (numbers) => {
    if(numbers.length > 2){ // 判断是否剩余两个元素
    return getMin( // 递归 调用自己
        [numbers[0], getMin(numbers.slice(1))] //对传入的形参（数组）进行析构赋值
    )
    }else{
        return Math.min.apply(null,numbers) // 已经封装好的
    }
}

// 优化
let getMin = numbers => (numbers.length > 2) ? getMin([numbers[0],  getMin( numbers.slice(1) )]) : (Math.min.apply(null,numbers))

getMin([4,8,76,1,0,-9]) // -9
  • 用代入法理解一遍

getMin([2, 4, 3, 1])

getMin([2, getMin([4, 3, 1])])

getMin([2, getMin([4, getMin([3, 1]))]])

getMin([2, getMin([4, Math.min.apply(null,[3, 1]))]])

getMin([2, getMin([4, 1])])–>getMin([2, Math.min.apply(null, [4, 1])])

getMin([2, 1])–>Math,min.apply(null, [2, 1])

1

用循环遍历实现getMin

无需考虑终止条件，逐项比较

1
2
3
4
5
6
7
8
9

//循环
let getMin = numbers => {
    let len = numbers.length
    let min = numbers[0]
    for(let i = 1; i < len; i++){
        min = numbers[i] < min ? numbers[i] : min
    }
    return min
}

重写minIndex

永远有两种写法：「递归」和「循环」

  • 目前的minIndex繁琐
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 递归写minIndex
let minIndex = (numbers) => { //下标
    numbers.indexOf( getMin(numbers) )
let getMin = numbers => (numbers.length > 2) ? getMin([numbers[0],  getMin( numbers.slice(1) )]) : (Math.min.apply(null,numbers))

// 用循环重写minIndex 易理解
let minIndex2 = numbers => {
    let index = 0
    for(let i = 1; i < numbers.length; i++){
        if(numbers[i] < numbers[index]){
            index  = i
        } // if
    } // for
    return index
} // minIndex2
minIndex2([2,1,4,5,8,9,-99])

所有递归都可以改成循环

递归

特点

  • 函数不停调用自己，每次调用的参数略有不同，可能是上一次的返回值
  • 当满足条件时，则实现一个简单的调用
  • 确定终止条件
  • 递进到终止条件，代入值，回归，
  • 最终算出结果

理解

  • 用代入法理解递归
  • 用调用栈理解递归（压栈 弹栈）

难度升级：将正整数数组从小到大排序

实现 sort 排序

思路

  • 用循环实现：容易理解，但代码复杂
  • 用递归实现：代入理解，代码简洁

递归思路

  • 选择排序

小试牛刀

将长度为2的数组排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 思路
let sort2_draft = ([a,b]) => {
    if(a < b){
        return [a,b]
    }else{
        return [b,a]
    }
}

// 优化代码
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a]
  • 这里sort2为终止条件 即递归基准

将长度为3的数组排序

1
2
3

let sort3_draft1 = ([a,b,c]) => {
    return [min(a,b,c)],sort2[(???)]
}
  • 发现???拿不到具体的最小的值，即无法将最小值从数值从数组里排除掉
  • 必须知道最小值元素的下标，根据下标删掉最小元素

let index = minIndex(numbers)

从numbers里删掉最小的元素numbers.splice(index,1)，改变原数组

let min = numbers[index]

改进代码[min].concat(numbers)

用求最小值的方法，先把三个数中最小的放到最前面的位置

然后将后面两个数用两数排序的方法排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// 已知求最小值函数为getMin
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))

// 获取数组最小元素下标的函数
let getMinIndex = numbers => {
    // 得到最小值下标
    let minValue = getMin(numbers)
    return numbers.indexOf(minValue)
}
// 已知两个元素排序 这里为终止条件 即递归基准
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a]

// 求排序函数
let sort3 = (numbers) => {
    // 赋值最小值下标
    let index = getMinIndex(numbers)
    let min = numbers[index]
    let number_2 = numbers.slice(0)
    number_2.splice(index,1)
   return [min].concat(sort2(number_2))
}
// 或者
let sort3_draft = (numbers) => {
    // 赋值最小值下标
    let index = getMinIndex(numbers)
    let min = numbers[index]
    numbers.splice(index,1) // 返回去掉的元素组成的数组，并且改变原数组numbers
   return [min].concat(sort2(numbers))
}

console.log(sort3.apply(null,[[11,9,1]]))
console.log(sort3_draft.call(null,[3,2,1]))

将长度为4的数组排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 已知求最小值函数为getMin
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))

// 获取数组最小元素下标的函数
let getMinIndex = numbers => {
    // 得到最小值下标
    let minValue = getMin(numbers)
    return numbers.indexOf(minValue)
}
// 已知两个元素排序 这里为终止条件 即递归基准
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a]

// 求排序函数
let sort3 = (numbers) => {
    // 赋值最小值下标
    let index = getMinIndex(numbers)
    let min = numbers[index]
    numbers.splice(index,1)
   return [min].concat(sort2(numbers))
}
let sort4 = (numbers) => {
    let index = getMinIndex(numbers)
    let min = numbers[index]
    numbers.splice(index,1)
    return [min].concat(sort3(numbers))
    }// sort3 -> sort2 再次调用，并非递归
}
console.log(sort4.apply(null,[[11,9,1,6]]))

推广

每次选择一个最小的数放最前面，连接剩余的元素组成的新数组

然后对后面的数做同样的事情

直到剩下最后两个互相比较排序

回归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 已知求最小值函数为getMin
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))
// 获取数组最小元素下标的函数
let getMinIndex = numbers => {
    return numbers.indexOf(getMin(numbers))
}
let mySort = numbers => {
    if(numbers.length > 2){
        let index = getMinIndex(numbers)
        let min = numbers[index]
        numbers.splice(index,1)
        return [min].concat(mySort(numbers))
    }else{
        return numbers[0]<numbers[1]?numbers:numbers.reverse()
    }
}
console.log(mySort([12,5,8,7,9]))
  • 用代入法理解一遍（SICP）

mySort([12,5,8,7,9])

= [5] + mySort([12,8,7,9])

= [5] + ([7] + mySort([12,8,9]))

= [5] + ([7] + [8] + mySort([12,9]))

= [5] + ([7] + [8] + [9,12])

= [5] + ([7] + [8,9,12])

= [5] + [7,8,9,12]

= [5,7,8,9,12]

如何调试代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

let mySort = numbers => {
    if(numbers.length > 2){
        let index = getMinIndex(numbers)
        let min = numbers[index]
        numbers.splice(index,1)
        return [min].concat(mySort(numbers))
    }else{
        return numbers[0]<numbers[1]?numbers:numbers.reverse()
    }
}
console.log(mySort([12,5,8,7,9]))

//*************************************
// Uncaught ReferenceError: getMinIndex is not defined
//    at sort (<anonymous>:3:17)    2）sort发现getMinIndex不存在，调用栈，压栈
//    at <anonymous>:1:1            1）匿名函数调用了sort

let getMinIndex = numbers => {
    let minValue = getMin(numbers)
    return numbers.indexOf(minValue)
}
console.log(mySort([12,5,8,7,9]))

//*************************************
// Uncaught ReferenceError: getMin is not defined
//    at getMinIndex(<anonymous>:2:11)  3）getMinIndex发现getMin不存在
//    at sort (<anonymous>:3:17)        2）sort调用了getMinIndex
//    at <anonymous>:1:1>               1）匿名函数调用了sort

console.log(mySort([12,5,8,7,9]))

//*************************************

let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))

console.log(mySort([12,5,8,7,9]))

//*************************************
// 把赋值后的结果打印出来
var mySort = (numbers) => {
    if(numbers.length > 2){
        let index = getMinIndex(numbers)
        let min = numbers[index]
        console.log(`min: ${min}`)
        let rest = numbers.splice(index,1)
        console.log(`rest: ${rest}`)
        return [min].concat(mySort(rest))
    }else{
        return numbers[0]<numbers[1]?numbers:numbers.reverse()
    }
}

console.log(mySort([12,5,8,7,9]))

//*************************************
// > min: 5 // 符合预期
// > rest: 5 //rest 不符合预期，numbers.splice(index,1)有问题 查mdn
// > [5,5]
//*************************************

var mySort = numbers => {
    if(numbers.length > 2){
        let index = getMinIndex(numbers)
        let min = numbers[index]
        console.log(`min: ${min}`)
        numbers.splice(index,1)
        console.log(`rest: ${numbers}`)
        return [min].concat(mySort(numbers))
    }else{
        return numbers[0]<numbers[1]?numbers:numbers.reverse()
    }
}
console.log(mySort([12,5,8,7,9]))

//*************************************
// > min: 5                 //先摘除5
// > numbers: [12,8,7,9]
// > min: 7                 //再摘除7
// > numbers: [12,8,9]
// > min: 8                 //再摘除8
// > numbers: [12,9]        //最后剩两个数组排序
// [5,7,8,9,12]    //先摘除5，再摘除7，再摘除8，最后剩两个数组排序，再依次反向捅回去
//*************************************

选择排序的循环写法

选择排序的循环思路

用循环改写递归的sort

思路不变

每次找到最小的数，放前面

然后对后面的书做同样的事情（递归）

然后 i++（循环）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

//递归思路
let sort_recursion = numbers => {
    if(numbers.length > 2){
        let index = minIndex(numbers) // minIndex()　的实现省略
        let min = numbers[index]
        numbers.splice(index, 1)
        return [min].concat(sort_recursion(numbers))
    }else{
        return numbers[0] < numbers[1]? numbers : numbers.reverse()
    }
}

// 循环思路
let sort_circulation = numbers => {
    for(let i = 0; i < ???; i++){
        let index = minIndex(numbers) // minIndex()　的实现省略
        // index 是当前最小数的下标
        // index 对应的数应该放到 i 处，互换值
        swap(numbers, index, i) // 还没实现swap() 把最小的和当前的交换位置
        // index i 都是 index 的意思， 建议 i 改名
    }
}

分析

  • 如何知道 i < ??? 处应该怎么写
  • 提前写好minIndex省略实现，能有效简化问题
  • 用swap占位能有效简化问题

实现swap 互换传值/址

1
2
3
4
5
6

let swap = (array, i, j) => {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
}
swap(numbers,1,2)

容易错误地实现swap

1
2
3
4
5
6

let swap = (a,b) => {
    let temp = a
    a = b
    b = temp
}
swap(numbers[1], numbers[2]) // 改变原数组

会发现，numbers[1]和numbers[2]的值原封不动

因为a b是简单类型，传参的时候会复制值

而numbers是对象，传参是复制地址

传值 V.S. 传址

  • 用ES6的析构赋值
1
2
3
4
5
6
7
8

let a = 1, b = 2
[a,b] = [b,a]
let numbers = ['a','b']
// > undefined
[numbers[0],numbers[1]] = [numbers[1],numbers[0]]
// > (2) ["b", "a"]
numbers
// > (2) ["b", "a"]

思路改进：循环选择排序

分析

  • 如何知道 i < ??? 处应该怎么写
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

let sort = numbers => {
    for(let i = 0; i < ???; i++){ // i < ???
        let index = minIndex(numbers) // minIndex()　的实现是否符合预期？
        // index 是当前最小数的下标
        // index 对应的数应该放到 i 处，即每次 i 接受一次 index 的值：
        swap(numbers, index, i) // swap() 已实现
        // index i 都是 index 的意思， 建议 i 改名
    }
}

// 用循环写minIndex
let minIndex = numbers => {
    let index = 0
    for(let i = 1; i < numbers.length; i++){
        if(numbers[i] < numbers[index]){
            index  = i
        } // if_end
    } // for_end
    return index
} // minIndex2_end
  • 暴力分析，代入法：假设numbers的长度n = 4
n i index可能的结果 index预期的结果
4 0 swap(numbers, index, 0)，index可能为0/1/2/3 1/2/3
4 1 swap(numbers, index, 1)，index可能为0/1/2/3 2/3
4 2 swap(numbers, index, 2)，index可能为0/1/2/3 3
4 3 swap(numbers, index, 3)，index可能为0/1/2/3 在上一次已经取完，不存在
  • 发现问题：

每次index都在数组的所有元素中取

有可能找到已经排好的第一个最小值，不再调换剩余项的位置

即minIndex查找index范围有问题

  • let index = minIndex(numbers)错误，不该在原数组里找
  • 解决问题：

i的最大值应为numbers.length - 1

即???里应该写numbers.length - 1

每次循环对比上一次，应该去掉上次找到的最小值

  • 如果上次循环已经找到一个最小的值，那么下一次找最小值时候，就必须忽略（排除）上次那个找到的最小值
  • 把本次找到的最小值提前swap()
  • 截取第i次之后的新数组numbers.slice(i)，不改变原数组
  • 得到截取后最小值的下标minIndex( numbers.slice(i) )
  • 将最小值序号变为minIndex( numbers.slice(i) ) + i
  • 即let index = minIndex( numbers.slice(i) ) + i，i为遍历的下标范围小于numbers.length - 1
i 要找几个 忽略几个
0 4 0
1 3 1
2 2 2
  • 每次找minIndex(numbers.slice(i))里面最小的

为什么要+ i

  • 如果不加，那么index总是从0数起，每次都会少掉 i 个
  • minIndex(numbers.slice(i))切掉下标的要加回来

重新分析代码

1
2
3
4
5
6

let sort = numbers => {
    for(let i = 0; i < ???; i++){ // i < ???
        let index = minIndex( numbers.slice(i) ) + i // slice() 不改变原数组
        swap(numbers, index, i) // swap()改变原数组 将每次排除 i 项的剩余最小值提前
    }
}
  • 代入法：假设numbers的长度n = 4
n i index可能的结果
4 0 swap(numbers, index, 0)，index可能为 1/2/3
4 1 swap(numbers, index, 1)，index可能为 2/3
4 2 swap(numbers, index, 2)，index可能为 3
4 3 swap(numbers, index, 3)，numbers.slice(3)是[i]，i = 3不行，所以i < n - 1
  • i < ???应为numbers.length - 1

画图

[27,44,35,16]

Object.keys([27,44,35,16]) -> Array(4) [ "0", "1", "2", "3" ]

最小值16，最小值下标"3"

i = 0，最小值下标"3"，下标 i 和"3"的值 对换位置swap()

新数组[16,44,35,27]，第1项固定

i = 1，找后面3个元素中最小值 下标"3"，下标 i 和"3"的值 对换位置swap()

新数组[16,27,35,44]，前2项固定

i = 2，找后面2个元素中最小值 下标"2"，下标 i 和"2"的值 不用对换

比较完了，不必再进行循环i = 3

改进代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// 试写
let sort = (numbers) => {
    for(let i = 0; i < numbers.length - 1; i++){
        console.log(`----`) // 打log精髓
        console.log(`i: ${i}`)
        let index = minIndex(numbers.slice(i)) + i
        console.log(`index: ${index}`)
        console.log(`min: ${numbers[index]}`)
        // 小标不相等 交换值的位置；相等什么也不做
        if(index !== i){
            swap(numbers, index, i)
            console.log(`swap ${index}: ${i}`)
            console.log(`numbers: ${numbers}`)
        }else{// if_end
            console.log(`不交换`)
        }
    } // for_end
    return numbers
}

// 换值/址函数
let swap = (array, i, j) => {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
}

// 最小值下标函数
let minIndex = (numbers) => {
    let index = 0
    for(let i = 1; i < numbers.length; i++){
        if(numbers[i] < numbers[index]){
            index = i
        } //  if_end
    } //  for_end
    return index
} //  minIndex_end

sort([1, 199, 27, 93, 124, 4903, 4])

最终代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

let sort = (numbers) => {
    for(let i = 0; i < numbers.length - 1; i++){
        let index = minIndex(numbers.slice(i)) + i
        if(index !== i){
            swap(numbers, index, i)
        } // if_end
    } // for_end
    return numbers
} // sort_end

// 换值/址函数
let swap = (array, i, j) => {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
} // swap_end

// 最小值下标函数
let minIndex = (numbers) => {
    let index = 0
    for(let i = 1; i < numbers.length; i++){
        if(numbers[i] < numbers[index]){
            index = i
        } //  if_end
    } //  for_end
    return index
} //  minIndex_end

sort([1, 199, 27, 93, 124, 4903, 4])

循环选择排序小结

  • 所有递归都能改成循环
  • 循环的时候有很多细节
    • 难以想清楚
    • 代入法手动列出表格，找规律
    • 难以确定边界条件，即终止条件
    • 未实现处理长度为0和1的数组
  • 如何Debug
    • 看控制台
    • 打log
    • 打log同时添加标记

搞定选择排序，每次选择最小/最大的，选完就排完

选择排序算法总结

  • 求最小值
    • 2个数
    • 3个数
    • N个数
  • 排序
    • 2个数
    • 3个数
    • 4个数
    • N个数
  • 用到的概念
    • 数组（数据结构）slice、concat、splice、reverse
    • 递归：代入法理解；归纳法；确定终止条件分支
    • 循环写法

算法心得

  • 擦起键盘肝->运行调试->循环->优化
  • 耐心
  • 查改删 筛重排

手写题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 手写一个递归的数组选择排序
let sort = numbers =>{
    if(numbers.length <= 2){ //递归终止条件
    return numbers[0] < numbers[1]? numbers:numbers.reverse()
    }else{//递进条件 (numbers.length > 2)
    let index = minIndex(numbers) //需要实现求最小值下标的函数
    let min = numbers[index]
    numbers.splice(index,1)
    return [min].concat(sort(numbers)) //连接剩余部分
    }
}

算法中的递归

1.递归的概念 2.递归三要素：

  • 拆解寻找子问题
  • 最小子问题（基本问题）
  • 递归终止退出条件

3.高频题目精讲

1. 递归的概念

2. 递归三要素

3. 高频题目精讲

参考文章

伪代码与流程图.pdf

算法入门（上）.pdf

算法入门（下）.pdf

数据结构（上）.pdf

程序员的算法课 递归

相关文章

  • 无
  • 作者： Joel
  • 文章链接：
  • 版权声明
  • 非自由转载-非商用-非衍生-保持署名
  • 河 掘 思 知 简