## 目录：几种排序 - 选择排序：重复选出最小值，放前面 - 快速排序：重复指定基准值，小于基准排前面，大于的排后面 - 归并排序：分拆直至单个，两两排序，归并，引入空数组保存的较小值 - 计数排序 - 时间空间复杂度 - 其他排序算法 --- ## 选择排序`selection sort` 复习代码 ```JavaScript 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 详见上一节 --- ## 快速排序`quick sort` ### 递归思路 > 以某某为基准 - 学号有`[12,2,7,21,5,9,4,6]` - 「以某某为基准，较小的排前面，较大的排后面」 [快速排序（Quicksort）的Javascript实现 by 阮一峰](http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html) ```JavaScript // 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] > > 再次合并排序 > > 只要数组排好序，就能合并再排序分拆成单个两两比较合并排序 ```JavaScript 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] ```JavaScript let countSort = arr => { let hashTable = {}, max = 0, result = [] for(let i = 0; i < arr.length; i++){ /* 先遍历传入的数组 */ 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；只适用于整数排序 ```JavaScript let countSort = arr => { let hashTable = {}, max = 0, result = [] for(let i = 0; i < arr.length; i++){ // 先遍历result if( !(arr[i] in hashTable) ){ // 对于（本次遍历）不在哈希表中的创建属性并赋值1，即出现次数 hashTable[arr[i]] = 1 }else{ // 对于（本次遍历）在哈希表中的将该属性值加1 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 --- > 终极排序 ## 堆排序 --- ## 其他排序算法 - [冒泡排序](https://visualgo.net/zh/sorting) - [插入排序洗牌](https://visualgo.net/zh/sorting) 点击`INS` - [希尔排序](http://sorting.at/) 选择`Shell Sort` - [计数排序](https://visualgo.net/zh/sorting) 点击`RAD` --- ·未完待续· --- #### 参考链接 [2020版前端体系课【方方】之【算法与数据结构】排序算法(下)](https://xiedaimala.com/tasks/49584830-6445-4d00-bb96-dc6fe91bb55a) [快速排序（Quicksort）的Javascript实现](http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html) [visualgo.net/zh/sorting](https://visualgo.net/zh/sorting) [sorting.at/](http://sorting.at/) [伪代码与流程图.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-1-10-24-6.pdf) [算法入门（上）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2020-1-9-16-20-15.pdf) [算法入门（下）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-8-11-27-48.pdf) [数据结构（上）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-9-22-25-26.pdf) #### 相关文章 - 无 --- - 作者： Joel - 文章链接： - [版权声明](http://xmasuhai.xyz/posts/版权声明链接/) - 非自由转载-非商用-非衍生-保持署名 --- ---

【算法与数据结构02】排序算法（下）