排序算法

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

必备知识

  • 数据结构
    • 用数组[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
  • 看起来MathObject一样是构造函数,但不是,没有函数的共用属性
  • 实际上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) ) + ii为遍历的下标范围小于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])

循环选择排序小结

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

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


选择排序算法总结

  • 求最小值
    • 2个数
    • 3个数
    • N个数
  • 排序
    • 2个数
    • 3个数
    • 4个数
    • N个数
  • 用到的概念
    • 数组(数据结构)sliceconcatsplicereverse
    • 递归:代入法理解;归纳法;确定终止条件分支
    • 循环写法

算法心得

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

手写题

 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

程序员的算法课 递归

相关文章