[TOC] # 排序 推荐阅读 [掘金-排序算法总结](https://juejin.im/post/57dcd394a22b9d00610c5ec8#heading-27) 排序算法性能分析的指标：**关键码的比较次数**，**记录交换次数**。 稳定性：如果一种排序算法不会改变关键码值相同的记录的相对顺序，则称其为稳定的 ## 冒泡排序 依次比较、交换相邻的元素，每轮将一个最大的元素“冒泡”到最后(第i位置) ```javaScript // 公共方法；以下均假设实现升序排列 function swap(arr, index1, index2) { let tmp = arr[index1] arr[index1] = arr[index2] arr[index2] = tmp } ``` ```javaScript function bubbleSort(arr) { for(let i = arr.length - 1; i > 0; i--) { for (let j = 0; j < i; j++) { if (arr[j] > arr[j+1]) { swap(arr, j, j+1) } } } } ``` ## 选择排序 每一次内循环遍历寻找最小的数，记录下 minIndex，并在这次内循环结束后交换 minIndex 和 i 的位置。重复这样的循环 n - 1 次即得到结果。 ```javaScript function selectionSort(arr) { for (let i = 0, len = arr.length; i < len - 1; i++) { let minIndex = i for (let j = i+1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j } } swap(arr, i, minIndex) } } ``` ## 插入排序： 逐个处理待排序的记录。每个新记录与前面已排序的子记录比较，将其插入到子序列正确的位置 ```javaScript function insertSort(arr) { for (let i = 1; i < arr.length; i++) { for (let j = i; j > 0; j--) { if (arr[j] < arr[j-1]) { swap(arr, j, j-1) } } } } ``` ## 希尔排序 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： - 选择一个增量序列 t1，t2，…，tk，其中 ti > tj，tk = 1； - 按增量序列个数 k，对序列进行 k 趟排序； - 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。  ```js function shellSort (arr) { let N = arr.length // 最开始时的增量 gap 为数组长度的一半 for (let gap = Math.floor(N / 2); gap > 0; gap = Math.floor(gap / 2)) { // 对各个分组进行插入排序 for (let i = gap; i < N; i++) { // 将 arr[i] 插入到所在分组正确的位置上 insertI(arr, gap, i) } } } function insertI (arr, gap, i) { let inserted = arr[i] let j for (j = i - gap; j >=0 && inserted < arr[j]; j -= gap) { arr[j + gap] = arr[j] } arr[j + gap] = inserted } ``` ## 归并排序 2路归并排序：归并排序（划分过程）用递归实现。 若当前（未排序）序列的长度不大于1 返回当前序列 否则，将当前未排序序列分割为大小相等的两个子序列，分别用归并排序对两个子序列进行排序，将返回的两个有序子序列**合并**成一个有序序列 ```javaScript function mergeSort(arr) { const len = arr.length if (len < 2) { return arr } const mid = Math.floor(len / 2) const left = arr.slice(0, mid) const right = arr.slice(mid) return merge(mergeSort(left), mergeSort(right)) } function merge(left, right) { const result = [] // 注意长度限制 while (left.length > 0 && right.length > 0) { result.push(left[0] <= right[0] ? left.shift() : right.shift()) } return result.concat(left, right) // 注意合并剩下的 } ``` ## 快速排序 算法思想：若当前（未排序）序列的长度不大于1 返回当前序列。否则，在待排序记录中选取一个记录做为**轴值(pivot)**，通过**划分算法**将其余待排记录划分成两部分，比P小的记录放在P之前，比P大的记录放在P之后；分别用快速排序对前后两个子序列进行排序（注意轴值已经在最终排序好的数组中的位置,无须继续处理） **非标准版本** ```javaScript function quickSort(arr) { const pivot = arr[0] const left = [] const right = [] if (arr.length < 2) { return arr } for (let i = 1, len = arr.length; i < len; i++) { arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]) } return quickSort(left).concat([pivot], quickSort(right)) } ``` **单循环版本？** ``` javaScript function quickSort(arr, left = 0, right = arr.length - 1) { if (left < right) { const pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } return arr; } function partition (arr, left ,right) { let pivot = left; // 以第一个元素为 pivot for (let i = left + 1; i <= right; i++) { if (arr[i] < arr[left]) { swap(arr, i, pivot); pivot += 1; } } swap(arr, left, pivot); //将 pivot 值移至中间 return pivot; } ``` **不知道啥版本** ```javaScript function partition(arr, left, right, pivotValue) { do { while (arr[++left] < pivotValue); // 注意加分号表示没有循环体 while((left < right) && arr[--right] > pivotValue); swap(arr, left, right) } while (left < right) return left // 返回右半部分的第一个元素的下标 } // left, right视为数组的下标 function quickSort(arr, left, right) { if (left >= right) return // 1个元素不需要再划分 let pivotindex = Math.floor((left + right) / 2) // 选取轴值，可以考虑随机选取 swap(arr, pivotindex, right) // 把轴值与当前数组末尾元素交换 let k = partition(arr, left-1, right, arr[right]) // 划分数组，返回轴值位置 swap(arr, k, right) // 把轴值换回来 // 注意k位置已经固定 quickSort(arr, left, k-1) quickSort(arr, k+1, right) } let myArray = [11, 81, 92, 72, 43, 53, 64, 34, 25, 16] let myArray2 = [5, 5, 3, 2, 6, 4, 5] quickSort(myArray2, 0, myArray2.length - 1) quickSort(myArray, 0, myArray.length - 1) console.log(myArray) console.log(myArray2) ``` 最后一个版本是我学数据结构课的书上的，还有那时候画的图，这是对[11, 81, 92, 72, 43, 53, 64, 34, 25, 16]的第一轮快速排序的流程图  ## 堆排序 堆排序利用了二叉堆的特性来做，二叉堆通常用数组表示，并且二叉堆是一颗完全二叉树（所有叶节点（最底层的节点）都是从左往右顺序排序，并且其他层的节点都是满的）。二叉堆又分为大根堆与小根堆。 * 大根堆是某个节点的所有子节点的值都比他小 * 小根堆是某个节点的所有子节点的值都比他大 堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例，某个节点的左边子节点索引是`i * 2 + 1`，右边是`i * 2 + 2`，父节点是`(i - 1) /2`。 算法思路： <1>.将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区； <2>.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]； <3>.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 ```javaScript function heapSort(arr) { let size = arr.length; // 初始化堆，i 从最后一个父节点开始调整，直到节点均调整完毕 for (let i = Math.floor(size / 2) - 1; i >= 0; i--) { heapify(arr, i, size); } // 堆排序：每轮将堆顶元素和最后一个元素交换，然后重新调整堆 for (let i = size - 1; i > 0; i--) { swap(arr, 0, i); size -= 1; heapify(arr, 0, size); } return arr; } // 参数：数组，父结点下标，数组大小 function heapify(arr, index, size) { let largest = index; let left = 2 * index + 1; let right = 2 * index + 2; // 如果左子结点的值比父结点大则互换 if (left < size && arr[left] > arr[largest]) { largest = left; } // 如果右子结点的值比父结点的值大则互换 if (right < size && arr[right] > arr[largest]) { largest = right; } // 如果发生了互换，对父结点再次做堆特性的判断 if (largest !== index) { swap(arr, index, largest); heapify(arr, largest, size); } } // test const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24]; console.log(heapSort(arr)); ``` ## 桶排序 算法思想：先将数组分到有限个桶中（根据映射函数），再对每个桶中的数据进行排序，对每个桶中数据的排序可以是桶排序的递归，或其他算法，在桶中数据较少的时候用插入排序最为理想。 ```js /** * * @param {arr} arrry 待排序数组 * @param {Number} num 桶的数量 */ function bucketSort (arr, num) { if (arr.length <= 1) return arr let len = arr.length, buckets = [], result = [], min = max = arr[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0 num = num || ((num > 1 && regex.test(num)) ? num : 10) for (let i = 1; i < len; i++) { min = min <= arr[i] ? min : arr[i] max = max >= arr[i] ? max : arr[i] } space = (max - min + 1) / num for (let j = 0; j < len; j++) { let index = Math.floor((arr[j] - min) / space) // 映射函数 if (buckets[index]) { // 非空桶，插入排序 let k = buckets[index].length - 1 while (k >= 0 && buckets[index][k] > arr[j]) { buckets[index][k + 1] = buckets[index][k] k-- } buckets[index][k + 1] = arr[j] } else { // 空桶，初始化 buckets[index] = [] buckets[index].push(arr[j]) } } while (n < num) { result = result.concat(buckets[n]) n++ } return result } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] console.log(bucketSort(arr,4)) // [ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ] ``` ## 时间复杂度及适用情况分析 **插入排序：** 最适合于已经有一定顺序的元素排列 - 最佳情况：输入数组按升序排列。T(n) = O(n) - 最坏情况：输入数组按降序排列。T(n) = O(n^2) - 平均情况：T(n) = O(n^2) **归并排序：** 以空间换时间 - 最差情况：T(n) = O(nlogn) - 最优情况：T(n) = O(nlogn) - 平均情况：T(n) = O(nlogn) **快速排序：** 最好情况：Partition函数每次恰好能均分序列； 最坏情况：每次划分只能将序列分为一个元素与其他元素两部分，这时的快速排序退化为冒泡排序。 * 最佳情况：T(n) = O(nlogn) * 最差情况：T(n) = O(n^2) * 平均情况：T(n) = O(nlogn) **堆排序：** 时间复杂度分析：建堆：O(n) ； n次取堆的最大元素：O(log n) ；堆排序的总时间代价：O(2nlog n) * 最佳情况：T(n) = O(nlogn) * 最差情况：T(n) = O(nlogn) * 平均情况：T(n) = O(nlogn) | 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 备注 | | :-: | :-: | :-: | :-: | :-: | | 选择排序 | × | N² | 1 | | | 冒泡排序 | √ | N² | 1 | | | 插入排序 | √ | N ~ N² | 1 | 时间复杂度和初始顺序有关 | | 希尔排序 | × | N 的若干倍乘于递增序列的长度 | 1 | 改进版插入排序 | | 快速排序 | × | NlogN | logN | | | 三向切分快速排序 | × | N ~ NlogN | logN | 适用于有大量重复主键 | | 归并排序 | √ | NlogN | N | | | 堆排序 | × | NlogN | 1 | 无法利用局部性原理 | # 查找 ## 二分查找 ```js // 二分查找，数组必须是有序的 function BinarySearch (arr, target) { let low = 0 let high = arr.length - 1 while (low <= high) { mid = Math.floor((low + high) / 2) if (arr[mid] === target) return mid if (arr[mid] < target) { low = mid + 1 } else { high = mid - 1 } } return -1 } ``` # 其他常见算法题 ## 全排列 [https://www.cnblogs.com/sooner/p/3264882.html](https://www.cnblogs.com/sooner/p/3264882.html) ```javaScript function swap(arr, index1, index2) { let tmp = arr[index1] arr[index1] = arr[index2] arr[index2] = tmp } // 重复元素不交换 function isSwap(arr, nBegin, nEnd) { for(let i = nBegin; i < nEnd; i++) { if (arr[i] === arr[nEnd]) { return false } } return true } /** * * @param {*} arr 数组 * @param {*} cur 当前待交换的数的下标 * @param {*} n 末尾下标 */ let cnt = 0 function permutation(arr, cur, n) { if (cur === n-1) { cnt++ let str = '' arr.forEach((item, index) => { str+=item }) console.log(`第${cnt}个全排列: ${str}`) } else { for (let i = cur; i < n; i++) { if (isSwap(arr, cur, i)) { swap(arr, cur, i) permutation(arr, cur+1, n) swap(arr, cur, i) } } } } let arr = [1, 3, 5] permutation(arr, 0, arr.length) /* 135 153 315 351 531 513 */ ``` ## 最大公约数 ```js // 辗转相除 function gcd (a, b) { let c = a % b while (c !== 0) { a = b b = c c = a % b } return b } /* 319 % 377 = 0 (余 319) 377 % 319 = 1 (余 58) 319 % 58 = 5 (余 29) 58 % 29 = 2 (余 0) 所以 (319, 377) 的最大公约数为 29 */ // or function gcd (a, b) { return a % b === 0 ? b : gcd(b, a % b) } ``` ## 字典序算法  ```js function swap (arr, index1, index2) { let temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp } function Prim (arr) { let len = arr.length let indexFirst, indexSecond // 1 * 2 * 3 * ... n 个排列 let num = 1 for (let i = 1; i <= len; i++) { num *= i } num-- // 不算 123 了 while (num --) { // step1: 从右往左，找出第一个左边小于右边的数，记为 list[a] for (let i = len - 1; i > 0; i--) { if (arr[i - 1] < arr[i]) { indexFirst = i - 1 break } } // step2：从右往左，找出第一个大于 list[a] 的数，记为 list[b] for (let i = len - 1; i > 0; i--) { if (arr[i] > arr[indexFirst]) { indexSecond = i break } } // step3：交换 list[a] list[b]，将原先 list[a] 后面的数据(不包过 list[a])从小到大排列 swap(arr, indexFirst, indexSecond) // [1, 3, 2] -> [] arr = arr.slice(0, indexFirst + 1).concat(arr.slice(indexFirst + 1).sort()) console.log(arr.join('')) } } Prim([1, 2, 3]) /** * 132 * 213 * 231 * 312 * 321 */ ``` ## 回文字符串 回文字符串：一个字符串，不论是从左往右，还是从右往左，字符的顺序都是一样的（如 abba，abcba 等） 判断回文字符串比较简单，即用两个变量 left，right 模仿指针（一个指向第一个字符，一个指向最后一个字符），每比对成功一次，left 向右移动一位，right 向左移动一位，如果 left 与 right 所指的元素不相等则退出，最后比较 left 与 right 的大小，如果 left > right 则说明是回文字符串。 ## Ksum 问题 参考：[https://blog.csdn.net/haolexiao/article/details/70768526#commentBox](https://blog.csdn.net/haolexiao/article/details/70768526#commentBox) 在一个数组中，找出 K 个数相加和等于给定的数，这个叫做 Ksum 问题。 在 leetcode 中有以下几个题都是与之相关的 [two-sum](https://leetcode.com/problems/two-sum/) [3Sum](https://leetcode.com/problems/3sum/#/description) [3Sum Closest](https://leetcode.com/problems/3sum-closest/#/description) [4Sum](https://leetcode.com/problems/4sum/#/description) [4Sum II](https://leetcode.com/problems/4sum-ii/#/description) <span style="font-size: 20px; font-weight: bold;">2Sum</span> 从数组中找出相加和为给定的数，有两种思路： 1. 将数组排序，设置首尾两个指针往中间走，直到得到满足条件的解或指针相遇 2. 对数组中每个数建立一个 hashmap，然后再扫描一遍数组，判断 target - nums[i] 是否存在 第一种方法的时间复杂度为 O(nlogn)，主要是排序所花费的时间 第二种方法的时间复杂度为 O(n) <span style="font-size: 20px; font-weight: bold;">3Sum</span> 这个问题也有两种思路： 1. 最外层遍历一遍，转换为 2Sum 问题 2. 另一种思路是，先预处理一遍数组中两两相加的结果，然后遍历每一个数`nums[i]`，判断`target-nums[i]`是否在预处理的那个和中 两种方法的时间复杂度都为 O(n^2) <span style="font-size: 20px; font-weight: bold;">3Sum Closest</span> 这次要找的是最接近给定值的三个数之和，跟 3Sum 类似，只不过需要定一个 diff 变量来记录差的绝对值 <span style="font-size: 20px; font-weight: bold;">4Sum</span> 这个问题也有两种思路： 1. 先遍历第一个数，然后固定第一个数之后，转化为剩下元素的 3Sum 问题 2. 先遍历两个数，求和，然后转化为剩下元素的 2Sum 问题