算法笔记：分治法

Posted on | In | Views:

概念

分而治之，大问题分解成为n个同样解决步骤的相同问题，小问题的解可以合并成大问题的解。这么一看，满足分治思想的问题都是满足递归条件的——可分解，有结束条件，所以下边的几个算法基本全是递归。

常见问题

二分查找

在一大堆数中找某（些）数，使用条件：给的数据得是排好序的

coding

问题描述：一个有序列表，返回值为 ‘hohoho’ 的元素下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const list = ['ahhh','baaa','cola','diii','emmm','hohoho','icu','jack Ma','kuuu','mumumu']
function half_interval_search (list,target) {
  let low = 0
  let high = list.length - 1
  while(low <= high){
    let mid = Math.floor((high + low)/2)
    if(list[mid] === target){
      return mid
    }
    if(list[mid] > target){
      high = mid - 1
    }else{
      low = mid + 1
    }
  }
  return null
}

half_interval_search (list,'kuuu')  // 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math
list = ['ahhh','baaa','cola','diii','emmm','hohoho','icu','jack Ma','kuuu','mumumu']
def half_interval_search (list,target):
  low = 0
  high = len(list) - 1
  while low <= high:
    mid = math.floor((low + high)/2)
    if list[mid] == target:
      return mid
    if list[mid] > target:
      high = mid - 1
    else:
      low = mid + 1
  return None

print(half_interval_search(list=list,target='icu'))

思路

从中间开始比较，每次比较都可以丢弃一半无用数据。
二分法有三个指针（low，high，mid），通过比较改变low，high的值缩小查找范围，最终让mid命中target。可以看到，while里的部分就是分解出的小问题的解决步骤。通过不断的解决小问题，获得源问题的解。

归并排序

嗯，就是排序

coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function merge_sort (list) {
  if(list.length < 2){
    return list
  }
  let [mid, left_part, right_part] = [Math.floor(list.length/2), list.slice(0,mid), list.slice(mid)]
  return merge(merge_sort(left_part), merge_sort(right_part)) // 递归分解，逐层合并
}

function merge (left, right) {
  let [i, j, temp] = [0, 0, []]
  while(i < left.length && j < right.length){ // 左右数组相互比较
    if(left[i] < right[j]){
      temp.push(left[i++])
    }else{
      temp.push(right[j++])
    }
  }
  while(i < left.length){ // 左右比较完后，剩下的直接push进结果
    temp.push(left[i++])
  }
  while(j < right.length){
    temp.push(right[j++])
  }
  return temp
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import math
def merge_sort (list):
  if len(list) < 2:
    return list
  mid = math.floor(len(list)/2)
  left_part = list[0:mid]
  right_part = list[mid:]
  return merge(merge_sort(list=left_part), merge_sort(list=right_part))

def merge (left, right):
  i = 0
  j = 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] < right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1

  while i < len(left):
    result.append(left[i])
    i += 1
  
  while j < len(right):
    result.append(right[j])
    j += 1
  
  return result

print(merge_sort(list=list))

思路

分治思想嘛，先分后治，引用一个图。

“分”的阶段将数组层层分解，最终分解为单个元素。
image.png

“治”的阶段由单个元素开始，层层排序，最终合并成一个完整的有序数组。

快速排序

嗯，也是排序

coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quick_sort (list) {
  if(list.length < 2){
    return list
  }
  let [mid,left,right] = [Math.floor(list.length/2),[],[]]
  for(let i = 0; i < list.length; i++){
    if(i == mid) continue;
    if(list[i] < list[mid]){
      left.push(list[i])
    }else{
      right.push(list[i])
    }
  }
  return quick_sort(left).concat(list[mid],quick_sort(right))

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
def quick_sort (list):
    if len(list) < 2:
        return list
    
    mid = math.floor(len(list)/2)
    left = []
    right = []

    for i in range(0,len(list)):
        if i == mid:
            continue
        
        if list[i] < list[mid]:
            left.append(list[i])
        else:
            right.append(list[i])
        
    return quick_sort(left) + [list[mid]] + quick_sort(right)

思路

选择数组中间的一个元素为基准，大于这个基准的移到右边，小于基准的移到左边，左 + 中 + 右构成了一个新数组，对左右数组递归重复以上过程，最终就得到了排好序的数组。

总结

分治法类似数学归纳法，但是和做数学题有点不一样。大致步骤为

  • 找出分解问题的方法
  • 将源问题分解成多个小问题
  • 找出小问题的求解公式
  • 考虑随着问题规模增大时的求解方法
  • 设计递归函数
0%