“分治”,分而治之。其思想就是将一个大问题分解为若干个子问题,针对子问题分别求解后,再将子问题的解整合为大问题的解。
利用分治思想解决问题,一般分三步走:
思路分析:
归并排序是对分治思想的典型应用,它按照如下的思路对分治思想“三步走”的框架进行了填充:
function mergeSort(arr) { const len = arr.length // 处理边界情况 if(len <= 1) { return arr } // 计算分割点 const mid = Math.floor(len / 2) // 递归分割左子数组,然后合并为有序数组 const leftArr = mergeSort(arr.slice(0, mid)) // 递归分割右子数组,然后合并为有序数组 const rightArr = mergeSort(arr.slice(mid,len)) // 合并左右两个有序数组 arr = mergeArr(leftArr, rightArr) // 返回合并后的结果 return arr } function mergeArr(arr1, arr2) { // 初始化两个指针,分别指向 arr1 和 arr2 let i = 0, j = 0 // 初始化结果数组 const res = [] // 缓存arr1的长度 const len1 = arr1.length // 缓存arr2的长度 const len2 = arr2.length // 合并两个子数组 while(i < len1 && j < len2) { if(arr1[i] < arr2[j]) { res.push(arr1[i]) i++ } else { res.push(arr2[j]) j++ } } // 若其中一个子数组首先被合并完全,则直接拼接另一个子数组的剩余部分 if(i<len1) { return res.concat(arr1.slice(i)) } else { return res.concat(arr2.slice(j)) } }
快速排序在基本思想上和归并排序是一致的,仍然坚持“分而治之”的原则不动摇。
区别在于,快速排序并不会把真的数组分割开来再合并到一个新数组中去,而是直接在原有的数组内部进行排序。
思路分析:
快速排序会将原始的数组筛选成较小和较大的两个子数组,然后递归地排序两个子数组。
选取基准值方法:固定位置、随机选取、三数取中
以下代码采取固定中间位置选取基准值
function quickSort(arr){ if(arr.length<=1) { return arr; } let pivotIndex=Math.floor(arr.length/2); let pivot=arr.splice(pivotIndex,1)[0]; // 声明两个数组,分别用于存放比基准值小的数据和比基准值大的数据 let left=[],right=[]; for(let i=0;i<arr.length;i++){ // 根据基准值填充数组 if(arr[i]<pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } } // 分别对基准值划分出来的数组递归调用快速排序,然后合并数组 //return quickSort(left).concat([pivot],quickSort(right)); return [...quickSort(left),pivot,...quickSort(right)] }
思考:快速排序算法的优化
优化1、当待排序序列的长度分割到一定大小后,使用插入排序。
原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排
优化2、在一次分割结束后,可以把与基准值相等的元素聚在一起,继续下次分割时,不用再对与基准值相等元素分割
优化3、优化递归操作:快排函数在函数尾部有两次递归操作,我们可以对其使用尾递归优化