利用分治思想解决问题,我们一般分三步走:
归并排序和快速排序就是用了这种思想。
例:[8, 7, 6, 5, 4, 3, 2, 1]
首先重复地分割数组,整个分割过程如下:
[8, 7, 6, 5,| 4, 3, 2, 1] [8, 7,| 6, 5,| 4, 3,| 2, 1] [8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]
接下来开始尝试解决每个子问题。将规模为1的子数组两两合并为规模为2的子数组,合并时确保有序
[7, 8,| 5, 6,| 3, 4,| 1, 2]
继续将规模为2的按照有序原则合并为规模为4的子数组:
[5, 6, 7, 8,| 1, 2, 3, 4]
最后将规模为4的子数组合并为规模为8的数组:
[1, 2, 3, 4, 5, 6, 7, 8]
一直重复一个过程 分割、合并,涉及重复的可以采用递归。
归并排序在实现上依托的就是递归思想。
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)) } }
// 计算分割点 const mid = Math.floor(len / 2) // 递归分割左子数组,然后合并为有序数组 const leftArr = mergeSort(arr.slice(0, mid)) // 递归分割右子数组,然后合并为有序数组 const rightArr = mergeSort(arr.slice(mid,len))
所以,时间复杂度就是 O(nlog(n))。
快速排序在基本思想上和归并排序是一致的,仍然是分治。区别在于,快速排序并不会把真的数组分割开来再合并到一个新数组中去,而是直接在原有的数组内部进行排序。
快速排序会将原始的数组筛选成较小和较大的两个子数组,然后递归地排序两个子数组。
例子:[5, 1, 3, 6, 2, 0, 7]
首先要做的事情就选取一个基准值。基准值的选择有很多方式,这里我们选取数组中间的值,左右指针分别指向数组的两端。
[5, 1, 3, 6, 2, 0, 7] ↑ 基准 ↑
接下来我们要做的,就是先移动左指针,直到找到一个不小于基准值的值为止;然后再移动右指针,直到找到一个不大于基准值的值为止。
[5, 1, 3, 6, 2, 0, 7] 基准 ↑ ↑
交换 6 和 0,同时两个指针共同向中间走一步:
[5, 1, 3, 0, 2, 6, 7] ↑ 基准 ↑
此时 2 比 6 小,故右指针不动,左指针继续前进:
[5, 1, 3, 0, 2, 6, 7] ↑ 基准 right↑ left
此时右指针所指的值不大于 6,左指针所指的值不小于 6,故两个指针都不再移动。此时我们会发现,对于左指针所指的数字来说,它左边的所有数字都比它小,右边的所有数字都比它大(这里注意也可能存在相等的情况)。由此我们就能够以左指针为轴心,划分出一左一右、一小一大两个子数组:
[5, 1, 3, 0, 2] [6, 7]
针对两个子数组,重复执行以上操作,直到数组完全排序为止。这就是快速排序的整个过程。
// 快速排序入口 function quickSort(arr, left = 0, right = arr.length - 1) { // 定义递归边界,若数组只有一个元素,则没有排序必要 if(arr.length > 1) { // lineIndex表示下一次划分左右子数组的索引位 const lineIndex = partition(arr, left, right) // 如果左边子数组的长度不小于1,则递归快排这个子数组 if(left < lineIndex-1) { // 左子数组以 lineIndex-1 为右边界 quickSort(arr, left, lineIndex-1) } // 如果右边子数组的长度不小于1,则递归快排这个子数组 if(lineIndex<right) { // 右子数组以 lineIndex 为左边界 quickSort(arr, lineIndex, right) } } return arr } // 以基准值为轴心,划分左右子数组的过程 function partition(arr, left, right) { // 基准值默认取中间位置的元素 let pivotValue = arr[Math.floor(left + (right-left)/2)] // 初始化左右指针 let i = left let j = right // 当左右指针不越界时,循环执行以下逻辑 while(i<=j) { // 左指针所指元素若小于基准值,则右移左指针 while(arr[i] < pivotValue) { i++ } // 右指针所指元素大于基准值,则左移右指针 while(arr[j] > pivotValue) { j-- } // 若i<=j,则意味着基准值左边存在较大元素或右边存在较小元素,交换两个元素确保左右两侧有序 if(i<=j) { swap(arr, i, j) i++ j-- } } // 返回左指针索引作为下一次划分左右子数组的依据 return i } // 快速排序中使用 swap 的地方比较多,我们提取成一个独立的函数 function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]] }
快速排序的时间复杂度的好坏,是由基准值来决定的。
本文链接https://blog.csdn.net/qq_39903567/article/details/115673107