归并排序
归并排序是典型的分治法应用实例(divide and conquer)，递归实现起来有一些技巧，即在分的时候实现治，各层分治递归同时进行，这是递归比较巧妙的地方
常见算法动态演示图见： 常见算法动态演示
归并排序时间复杂度：O(n * log₂ n)，自己的理解(片面)：因为原数组拆分需要 log₂n 次，每一次合并都需要最多 n - 1次比较，因此算法时间复杂度 O( n * log₂n)
空间复杂度：O(n)，归并排序需要一个与原数组相同长度的数组做辅助来排序，即把两个n个元素的有序数组合并成2n个元素的有序数组需要借助一个长度为2n的数组来实现，当然这是标准答案下，有时自己写的远大于这个
稳定性： 稳定排序
把数组分解, 自己尝试非递归
//模拟分
function arr_divide (arr){
for(let gap = parseInt(arr.length / 2); gap >=1; gap = parseInt(gap / 2)){
for(let i = 0; i < arr.length; i += gap) {
let temp = []
for(let j = i; j < i + gap; j++) {
temp.push(arr[j])
//console.log(arr[j])
}
console.log(temp)
}
}
}
// [8, 9, 1, 7, 2, 3, 6, 0]
arr_divide([8, 9, 1, 7, 2, 3, 6, 0])
把数组合并，自己尝试非递归
//模拟治
function arr_conquer(arr) {
for(let gap = parseInt(arr.length / 2); gap >=1; gap = parseInt(gap / 2)){
for(let i = 0; i < arr.length; i += parseInt(arr.length / gap)) {
let temp = []
for(let j = i; j < i + parseInt(arr.length / gap); j++){
temp.push(arr[j])
}
console.log(temp)
}
//if(gap === 5) break
}
//console.log(arr)
}
//arr_conquer([8, 9, 1, 7, 2, 3, 6, 0])
归并排序实现一：非直接操作原数组，递归分解数组的时候 new 新数组，不推荐空间复杂度高
function mergeSort(arr){
let gap = parseInt(arr.length / 2)
if(gap === 0) return arr
//slice执行了 14 次,即原arr数组分成14个独立的数组
let left = mergeSort(arr.slice(0, gap))
let right = mergeSort(arr.slice(gap))
//merge被调用 arr.length - 1 次, 每次都 new 一个数组
return merge(left, right)
}
let testArr = [8, 9, 1, 7, 2, 3, 6, 0]
let res = mergeSort(testArr )
console.log(res)
console.log(testArr)
function merge(leftArr, rightArr) {
let temp = []
while(leftArr.length && rightArr.length) {
//采用这种方法，这里要用 <= 不然就不是稳定排序了
if(leftArr[0] <= rightArr[0]) {
temp.push(leftArr.shift())
}else{
temp.push(rightArr.shift())
}
}
//while(leftArr.length) temp.push(leftArr.shift())
//while(rightArr.length) temp.push(rightArr.shift())
//return temp
//上边三行优化如下
return temp.concat(leftArr).concat(rightArr)
}
//自己写的一版merge()函数，使用双指针法，可以实现任意两个有序数组合并成一个有序数组
function testMerge(leftArr, rightArr){
//定义左数组指针，初始指向leftArr[0]
let left = 0
//定义右数组指针，初始指向rightArr[0]
let right = 0
let temp = []
while(left < leftArr.length && right < rightArr.length) {
//采用这种方法，稳定排序 <=
if(leftArr[left] <= rightArr[right]) {
temp.push(leftArr[left++])
}else{
temp.push(rightArr[right++])
}
//左侧元素都比右侧元素小
if(left === leftArr.length){
while(right < rightArr.length){
temp.push(rightArr[right++])
}
}
//右侧元素都比左侧元素小
if(right === rightArr.length){
while(left < leftArr.length) {
temp.push(leftArr[left++])
}
}
}
return temp
}
归并排序实现二：直接操作原数组, 每次merge 都 new 一个数组
function mergeSort(arr, left, right, temp){
let middle = Math.floor((left + right ) / 2)
if(left < right) {
//分数组左边
mergeSort(arr, left, middle)
//分数组右边
mergeSort(arr, middle + 1, right)
//合并数组,在这里进行排序
merge(arr, left, right)
}
}
function merge(arr, left, right) {
//每次进入merge将temp数组置空
let temp = []
//这里更好的做法是调用的时候传过来mid值，而不是重新再计算一次
let mid = Math.floor((left + right) / 2)
let leftArr = arr.slice(left, mid + 1)
let rightArr = arr.slice(mid + 1, right + 1)
//console.log(leftArr, rightArr)
let lp = 0, rp = 0
while(lp < leftArr.length && rp < rightArr.length) {
//稳定排序 <=
if(leftArr[lp] <= rightArr[rp]){
temp.push(leftArr[lp++])
}else{
temp.push(rightArr[rp++])
}
}
while(lp < leftArr.length){
temp.push(leftArr[lp++])
}
while(rp < rightArr.length){
temp.push(rightArr[rp++])
}
//console.log(temp)
//依次把temp数组元素拷贝到原数组相应位置
// 01 23 03 45 67 47 07,仔细分析还是有规律的
for(let i = left; i <= right; i++) {
arr[i] = temp[i - left]
}
}
归并排序实现二：直接操作原数组, 优化空间复杂度
调用mergeSort时，直接传入一个temp全局空数组，这样不用每次进入merge都 new 新数组了
function mergeSort(arr, left, right, temp){
let middle = Math.floor((left + right ) / 2)
if(left < right) {
//分数组左边
mergeSort(arr, left, middle, temp)
//分数组右边
mergeSort(arr, middle + 1, right, temp)
//合并数组,在这里进行排序
merge(arr, left, right,temp)
}
}
function merge(arr, left, right, temp) {
//每次进入merge将temp数组置空
temp = []
//这里更好的做法是调用的时候传过来mid值，而不是重新再计算一次
let mid = Math.floor((left + right) / 2)
let leftArr = arr.slice(left, mid + 1)
let rightArr = arr.slice(mid + 1, right + 1)
//console.log(leftArr, rightArr)
let lp = 0, rp = 0
while(lp < leftArr.length && rp < rightArr.length) {
// 稳定排序 <=
if(leftArr[lp] <= rightArr[rp]){
temp.push(leftArr[lp++])
}else{
temp.push(rightArr[rp++])
}
}
while(lp < leftArr.length){
temp.push(leftArr[lp++])
}
while(rp < rightArr.length){
temp.push(rightArr[rp++])
}
//console.log(temp)
//依次把temp数组元素拷贝到原数组相应位置
// 01 23 03 45 67 47 07,仔细分析还是有规律的
for(let i = left; i <= right; i++) {
arr[i] = temp[i - left]
}
}
//merge函数优化，优化以下几点，青铜与王者的差距在此
function merge(arr, left, right, middle, temp) {
//优化一：传middle过来, 不要再重新计算
//优化二：不再构造leftArr, rightArr了, 使用指针
//优化三：每次进来不用置空 temp = [] , 每次进来 tp = 0
//优化四 优化if语句为三元运算符
let lp = left, rp = middle + 1, tp = 0 //分别指向左，右，temp数组的指针
while(lp <= middle && rp <= right) {
//arr[lp] <= arr[rp] ? temp[tp++] = arr[lp++] : temp[tp++] = arr[rp++]
// 优化如下
temp[tp++] = arr[lp] <= arr[rp] ? arr[lp++] : arr[rp++]
}
while(lp <= middle){
temp[tp++] = arr[lp++]
}
while(rp <= right){
temp[tp++] = arr[rp++]
}
for(let i = left; i <= right; i++) {
arr[i] = temp[i - left]
}
//另一种写法
//tp = 0
// for(let i = left; i <= right; i++) {
// arr[i] = temp[tp++]
// }
}
归并排序迭代实现
一般可以用递归实现的都可以用栈来模拟，但自己试着写了一下，以下为示例，最后发现实在写不下去，因为循环一次只能divide一个方向（左/右）的数组，不能实现像递归那种回溯处理完左侧再处理右侧
function mergeSortLoop(arr) {
let stack = []
let middle = Math.floor(arr.length / 2)
let leftArr = arr.slice(0, middle)
let rightArr = arr.slice(middle, arr.length)
stack.push(rightArr)
stack.push(leftArr)
// while(leftArr.length > 1) {
// let mid = Math.floor(leftArr.length / 2)
// let left = leftArr.slice(0, mid)
// let right = leftArr.slice(mid, middle)
// stack.push(right)
// stack.push(left)
// middle = mid
// leftArr = left
// //rightArr = right
// }
// while(rightArr.length > 1) {
// let mid = Math.floor(rightArr.length / 2)
// let left = rightArr.slice(0, mid)
// let right = rightArr.slice(mid, middle)
// stack.push(right)
// stack.push(left)
// middle = mid
// rightArr = right
// }
console.log(stack)
}
因此如果，脑袋里一直想着迭代把数组分开，再利用栈的特性来回溯，实在是没招，写了半天，想了半天，没写出来，最后想到自己提前实现了一版把数组合并（见上），把数组里每个元素看成单个序列他就是有序的，因此从这里着手，每次先访问2个元素，把这2个排序好，再访问4个元素，把这4个元素处理好。。。这样不也变相实现了吗，but, too young too simple, 这样的实现的只能排序 4/8/16。。。个元素的数组,整体思路还是对的
//用迭代和栈怎么把数组分隔？感觉是个难点，所以有些递归用迭代处理不用借助栈，不要思维定势
//第一版，测试用的是8个元素数组，把这版写出来也是费了很多事，debug了半天
function arr_conquer(arr) {
let temp = []
let lp = 0, rp = 0, tp = 0
for(let gap = parseInt(arr.length / 2); gap >= 1; gap = parseInt(gap / 2)){
let step = parseInt(arr.length / gap)
for(let i = 0; i < arr.length; i += step ) {
lp = i
rp = i + step * 1/2
tp = 0
while(lp < i + step * 1/2 && rp < i + step) {
temp[tp++] = arr[lp] <= arr[rp] ? arr[lp++] : arr[rp++]
}
while(lp < i + step * 1/2){
temp[tp++] = arr[lp++]
}
while(rp < i + step){
temp[tp++] = arr[rp++]
}
tp = 0
for(let j = i; j < i + step; j++) {
arr[j] = temp[tp++]
}
}
}
}
归并排序迭代，用了四个指针实现
//改进版，上边写的那个暂时写不动了，下边是根据别人用C写的改过来的，用了四个指针实现的
function mergeSortIteration(arr) {
let temp = []
//分别定义left_min_p, left_max_p, right_min_p, right_max_p 指向每轮要排序的元素
let i = 0, next_p = 0, left_min_p = 0, left_max_p = 0, right_min_p = 0, right_max_p = 0
let n = arr.length
for(i = 1; i < n; i *= 2){
for(left_min_p = 0; left_min_p < n - i; left_min_p = right_max_p){
//定义好left_max_p, right_min_p, right_max_p相对于left_min_p的位置
right_min_p = left_max_p = left_min_p + i
right_max_p = left_max_p + i
// 奇数个元素排序时, right_max_p会大于元素个数n
if(right_max_p > n){
right_max_p = n
}
//把指向temp的指针归零,然后取过来
next_p = 0
//两个有序的数组进行比较得到一个有序数组
while(left_min_p < left_max_p && right_min_p < right_max_p){
if(arr[left_min_p] < arr[right_min_p]){
temp[next_p++] = arr[left_min_p++]
}else{
temp[next_p++] = arr[right_min_p++]
}
}
//经过上边循环比较，如果左边有剩余元素没放temp，则直接移到对应位置就可以了
while(left_min_p < left_max_p) {
arr[--right_min_p] = arr[--left_max_p]
}
//把经过比较的较小的值取出来放到数组对应的位置，这个位置经由上边的循环空出的位置
while(next_p > 0) {
arr[--right_min_p] = temp[--next_p]
}
}
}
}
本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 21, 2021 at 10:21 am
转载请注明来源