javascript实现归并排序

in 算法 with 0 comment

归并排序

归并排序是典型的分治法应用实例(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]
      }
    }
  }
}
评论已关闭.