目录：几种排序

  • 选择排序：重复选出最小值，放前面
  • 快速排序：重复指定基准值，小于基准排前面，大于的排后面
  • 归并排序：分拆直至单个，两两排序，归并，引入空数组保存的较小值
  • 计数排序
  • 时间空间复杂度
  • 其他排序算法

选择排序selection sort

复习代码

 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++){
    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)
    }
}
  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
    }
  }
  return index
}

详见上一节

快速排序quick sort

递归思路

以某某为基准

  • 学号有[12,2,7,21,5,9,4,6]
  • 「以某某为基准，较小的排前面，较大的排后面」

快速排序（Quicksort）的Javascript实现 by 阮一峰

 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

// ES6
let quickSort = arr => {
    if (arr.length <= 1) { //终止条件
        return arr
} // if_end
    /* 得到基准 pivot */
    let pivotIndex = Math.floor(arr.length / 2)
    /* 取到基准值 */
    let pivot = arr.splice(pivotIndex, 1)[0]
    // splice()返回的还是数组，取值，第一项值，即splice(xxx)[0]
    // 原数组中删掉了基准值 pivot
    let left = []
    let right = []
    /* 左边数组 基准值 右边数组 */
    for (let i = 0; i < arr.length; i++){
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else { // 大于或等于
            right.push(arr[i])
        } // if_end
    } // for_end

    /* 快排左边数组 连接 基准值 和 快排右边数组 */
    return quickSort(left).concat([pivot], quickSort(right) )
} // quickSort_end

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

归并排序merge sort

归并排序递归思路

不以某某为基准

  • 学号有[12,2,7,21,5,9,4,6]
  • 左边一半排好序，右边一半排好序
  • 然后把左右两边合并（merge）起来

画图

[12 ,3, 7, 21, 5, 9, 4, 6]

分成 左边[12, 3, 7, 21] 和 右边[5, 9, 4, 6] 分别各自排好序，先不管怎么排

左边[3, 7, 12, 21] 右边[4, 5, 6, 9]

空[] 分别从头比较到尾 的每一项，并将较小的项依次放入 即合并同时排序

两个index 同时遍历

左边[12, 3, 7, 21]再分成 左右两个数组[12, 3] [7, 21]

两两排序[12] [3] 和 [7] [21]

空[] 分别从头比较到尾 的每一项，并将较小的项依次放入 即合并同时排序 得到[3, 12]和[7, 21]

合并同时排序 得到[3, 7, 12, 21]

右边[5, 9, 4, 6]同理分拆 合并 排序 得到[4, 5, 6, 9]

再次合并 排序

只要数组排好序，就能合并再排序 分拆成单个 两两比较 合并排序

 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

let mergeSort = arr =>{
    let k = arr.length
    if(k===1){return arr} // 长度1 即默认已经排好序 递归的终止条件

    /* 二分法 */
    /* 左半数组 */
    let left = arr.slice(0, Math.floor(k/2)) //左闭右开
    /* 右半数组 */
    let right = arr.slice(Math.floor(k/2)) // 左闭右开 自动补全参数 到最后
    /* 分别对 左半数组进行归并排序
    **        右半数组进行归并排序
    **        调用merge函数 合并
    **        递归到1时 假装排好序了
    */
    return merge(mergeSort(left), mergeSort(right))
} // mergeSort_end

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)) // slice不改变原数组，返回截取后的新数组
} //merge_end
mergeSort([1, 199, 27, 93, 124, 4903, 4])
  • 对merge()画图

[1, 5, 10] [2. 4. 9]

比较第一项1和2，提出较小项 1

[1, merge( [5, 10], [2, 4, 9] )]

[5, 10], [2, 4, 9]

比较第一项5和2，提出较小项 2

[1, 2, merge( [5, 10], [4, 9] )]

比较第一项5和4，提出较小项 4

[1, 2, 4, merge([5, 10], [9])]

比较第一项5和9，提出较小项 5

[1, 2, 4, 5, merge([10], [9])]

比较第一项10和9，提出较小项 9

[1, 2, 4, 5, 9, merge([10], [])] 只要一个数组空了，就返回另一个

[1, 2, 4, 5, 9, 10]

  • [b[0]].concat(merge(a, b.slice(1)))，数组b的第一项较小，连接上合并了a和除去第一项数组b的结果
  • [a[0]].concat(merge(a.slice(1), b))，数组a的第一项较小，连接上合并了除去第一项数组a和数组b的结果

小结

目前学了三种排序

  • 选择排序：选最小的排前面
  • 快速排序：基准小的往前，大的往后 剩1
  • 归并排序：拆分直至一个和一个 两两排序 两部分默认排好序，对排好序进行合并

计数排序count sort

思路

  • 数据结构：哈希表
  • 用一个哈希表作为记录
  • 发现数字N就记为N:1，如果再次发现N，就加1
  • 最后把哈希表的key全部打印出来
  • 假设N:m，那么N就需要打印m次
  • 二维表
  • 记录最大值为长度
  • 整数 依次+1 循环对比哈希表中是否存在该整数
  • 存在的记录到一个结果数组中
  • 即洗牌算法

画图演示

max = 12 每次比较，较大的记录下来

[12, 3, 9, 4, 2, 8, 5, 7]

{

12: 1,

3: 1,

9:1,

4:1,

2:1,

8:1,

5:1,

7:1

}

i: 0 ~ 12

result = [2, 3, 4, 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

let countSort = arr => {
    let hashTable = {},
    max = 0,
    result = []
    for(let i = 0; i < arr.length; i++){ // 先遍历result
        if( !(arr[i] in hashTable) ){ // 对不存在于哈希表里的元素，添加属性，属性名为形参数组的各个元素的值，属性值为记录的次数
            hashTable[arr[i]] = 1
        }else{ //对存在于哈希表里的元素，属性名对应哈希表里的属性值为记录的次数加1
            hashTable[arr[i]] += 1
        } // if_end 收集哈希表完毕

        /*  对 max 进行循环更新 */
        if(arr[i] > max){ max = arr[i] }
    } // for_end

    for(let j = 0; j <= max; j++){ // 再遍历hashTable 可取到最大值
        if(j in hashTable){ // 对于整数计数，存在的元素记录到结果数组中
            result.push(j)
        } // if_end
    } // for_end // 有bug
    return result
} // countSort_end // 有bug 自带去重的功能

相似的，如何记录一句话里的字母出现次数，Hi, I'm John

统计字母出现的次数：{H: 1, i: 1, ...}

遍历字母表的26个元素，结果放到一个数组中去

我在故宫修bug，去掉去重的功能，反应出现的次数

可优化，记录最小值min； 只适用于整数排序

 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

let countSort = arr => {
    let hashTable = {},
    max = 0,
    result = []
    for(let i = 0; i < arr.length; i++){ // 先遍历result
        if( !(arr[i] in hashTable) ){
            hashTable[arr[i]] = 1
        }else{
            hashTable[arr[i]] += 1
        } // if_end

        /*  */
        if(arr[i] > max){ max = arr[i] }
    } // for_end

    /* 解决元素出现两次的bug 时间复杂度变为O(n^2) */
    for(let j = 0; j <= max; j++){ // 再遍历hashTable
        if(j in hashTable){ // 属性名遍历
            for(let k = 0; k < hashTable[j]; k++){ // 值遍历, 对于记录的次数遍历
                result.push(j) // j 的值是几，就要push几次
            }
        } // if_end
    } // for_end
    return result
} // countSort_end
countSort([1, 199, 27, 93, 124, 4903, 4])

计数排序的特点

  • 数据结构不同
    • 使用了额外的数据结构hashTable，数据结构升级，算法升级
    • 只遍历原数组一遍，但需要遍历一次hashTable，对比之前的排序需要遍历多次原数组
    • 即「用空间换时间」，用存储在内存的空间hashTable节省时间
  • 时间复杂度对比
    • 选择排序O(n^2)
    • 快速排序O(n log2 n)
    • 归并排序O(n log2 n)
    • 计数排序O(n + max) 最快的，但空间占得多

时间空间复杂度

长度为1000的数组

  • 选择排序

第一次从[0, …, 999]中找最小的数字最多需要999次，赋值为min1，并在原数组里排出

第2次 在剩下的数组 [1, …, 999] 需找998次， min2

第999次 需找1次

每次都要比，1000 x 1000 n^2

  • 快速排序

规模每次减半

10层，每层1000

log(2)1000 x 1000

  • 归并排序

归并每次减半

10层，每层1000

log(2)1000 x 1000

  • 计数排序

遍历数组 1000 放哈希 冲撞操作

遍历哈希 最大长度

n + max - min

看衰减规律

算法学习总结

思路简单

细节很多 耐心

举例，画表，画图，多打log

手写伪代码，注重算法本身，而不是语言的API

终极排序

堆排序

其他排序算法

参考文章

算法入门（下）

快速排序（Quicksort）的Javascript实现

visualgo.net/zh/sorting

sorting.at/

相关文章

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