分析算法排序：
-
时间复杂度: 一个算法执行所耗费的时间。
-
空间复杂度: 运行完一个程序所需内存的大小。
-
执行效率、内存消耗、稳定性 三方面入手。
1. 排序
1.1 冒泡排序
冒泡的过程只涉及相邻数据的交换操作，所以它的空间复杂度为 O(1)。
为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序。 所以冒泡排序是稳定的排序算法。
最佳情况：T(n) = O(n)，当数据已经是正序时。
最差情况：T(n) = O(n(2))，当数据是反序时。
平均情况：T(n) = O(n(2))。
bubbleSort = (arr) => { if (arr.length <= 1) return arr; for (let i = 0; i < arr.length - 1; i++) { let hasChange = false; for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; hasChange = true; } } if (!hasChange) return; } console.log('arr', arr) return arr; } const arr = [7, 8, 4, 5, 6, 3, 2, 1]; bubbleSort(arr);1.2 插入排序
插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)。
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
最佳情况：T(n) = O(n)，当数据已经是正序时。
最差情况：T(n) = O(n(2))，当数据是反序时。
平均情况：T(n) = O(n(2))。
步骤
-
从第一个元素开始，该元素可以认为已经被排序；
-
取出下一个元素，在已经排序的元素序列中从后向前扫描；
-
如果该元素（已排序）大于新元素，将该元素移到下一位置；
-
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
-
将新元素插入到该位置后；
-
重复步骤 2 ~ 5。
insertSort = (arr) => { if (arr.length <= 1) return arr; let preIndex, current; for (let i = 1; i < arr.length; i++) { preIndex = i - 1; current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } if (preIndex + 1 !== i) { arr[preIndex + 1] = current; } } console.log('arr', arr) return arr; }优化插入排序：折半插入
-
取 0 ~ i-1 的中间点 ( m = (i-1) >> 1 )，array[i] 与 array[m] 进行比较，若 array[i] < array[m]，则说明待插入的元素 array[i] 应该处于数组的 0 ~ m 索引之间；反之，则说明它应该处于数组的 m ~ i-1 索引之间。
-
重复步骤 1，每次缩小一半的查找范围，直至找到插入的位置。
-
将数组中插入位置之后的元素全部后移一位。
-
在指定位置插入第 i 个元素。
// 折半插入排序 const binaryInsertionSort = array => { const len = array.length; if (len <= 1) return; let current, i, j, low, high, m; for (i = 1; i < len; i++) { low = 0; high = i - 1; current = array[i]; while (low <= high) { //步骤 1 & 2 : 折半查找 // 注: x>>1 是位运算中的右移运算, 表示右移一位, 等同于 x 除以 2 再取整, // 即 x>>1 == Math.floor(x/2) . m = (low + high) >> 1; if (array[i] >= array[m]) { //值相同时, 切换到高半区，保证稳定性 low = m + 1; //插入点在高半区 } else { high = m - 1; //插入点在低半区 } } for (j = i; j > low; j--) { //步骤 3: 插入位置之后的元素全部后移一位 array[j] = array[j - 1]; console.log('array2 :', JSON.parse(JSON.stringify(array))); } array[low] = current; //步骤 4: 插入该元素 } console.log('array2 :', JSON.parse(JSON.stringify(array))); return array; };1.3 选择排序
选择排序空间复杂度为 O(1)
选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。所以，选择排序是一种不稳定的排序算法。
最佳/最差/平均情况：T(n) = O(n(2))。
步骤
-
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
-
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
-
重复第二步，直到所有元素均排序完毕。
const selectionSort = array => { const len = array.length; let minIndex, temp; for (let i = 0; i < len - 1; i++) { minIndex = i; for (let j = i + 1; j < len; j++) { if (array[j] < array[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; console.log('array: ', array); } return array; };1.4 快速排序
因为 partition() 函数进行分区时，不需要很多额外的内存空间，所以快排是原地排序算法。
和选择排序相似，快速排序每次交换的元素都有可能不是相邻的，因此它有可能打破原来值为相同的元素之间的顺序。因此，快速排序并不稳定。
最佳情况：T(n) = O(n log n)。
最差情况：T(n) = O(n(2))。
平均情况：T(n) = O(n log n)。
步骤
-
先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
-
左右分别用一个空数组去存储比较后的数据。
-
最后递归执行上述操作，直到数组长度 <= 1;
特点：快速，常用。
缺点：需要另外声明两个数组，浪费了内存空间资源。
const quickSort1 = arr => { if (arr.length <= 1) { return arr; } //取基准点 const midIndex = Math.floor(arr.length / 2); //取基准点的值，splice(index,1) 则返回的是含有被删除的元素的数组。 const valArr = arr.splice(midIndex, 1); const midIndexVal = valArr[0]; const left = []; //存放比基准点小的数组 const right = []; //存放比基准点大的数组 // 遍历数组，进行判断分配 // 递归动态数组不要用len=arr.length替换arr.length for (let i = 0; i < arr.length; i++) { if (arr[i] < midIndexVal) { left.push(arr[i]); //比基准点小的放在左边数组 } else { right.push(arr[i]); //比基准点大的放在右边数组 } } //递归执行以上操作，对左右两个数组进行操作，直到数组长度为 <= 1 return quickSort1(left).concat(midIndexVal, quickSort1(right)); }; const array2 = [5, 4, 3, 2, 1]; console.log('quickSort1 ', quickSort1(array2)); // quickSort1: [1, 2, 3, 4, 5]1.5 希尔排序
空间复杂度为 O(1)
希尔排序不稳定
最佳情况：T(n) = O(n log n)。
最差情况：T(n) = O(n log(2) n)。
平均情况：T(n) = O(n log(2) n)。
const shellSort = arr => { let len = arr.length, temp, gap = 1; console.time('希尔排序耗时'); while (gap < len / 3) { //动态定义间隔序列 gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { for (let i = gap; i < len; i++) { temp = arr[i]; let j = i - gap; for (; j >= 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; console.log('arr :', arr); } } console.timeEnd('希尔排序耗时'); return arr; };2. 动态规划
2.1 斐波拉契数列
0，1，1，2，3，5，8，13，21，34，55，......
function fibo (n) { if (n <= 0) return 0; if (n === 1) return 1; return fibo(n - 1) + fibo(n - 2); } 优化之后 function fibo (n) { if (n <= 0) return 0; if (n <= 1) return 1; var res, a = 0, b = 1; for (var i = 2; i <= n; i++) { res = a + b; a = b; b = res; } return res; }2.2 寻找最长公共字串
function maxSubString (str1, str2) { if (!str1 || !str2) return ''; var len1 = str1.length, len2 = str2.length; var maxSubStr = ''; for (var i = 0; i < len1; i++) { for (var j = 0; j < len2; j++) { var tempStr = '', k = 0; while ((i + k < len1) && (j + k < len2) && (str1[i + k] === str2[j + k])) { tempStr += str1[i + k]; k++; } if (tempStr.length > maxSubStr.length) { maxSubStr = tempStr; } } } return maxSubStr; }2.3 背包问题
-
-
-