signed

QiShunwang

“诚信为本、客户至上”

分治算法解题思路

2021/1/28 11:44:55   来源:

文章目录

    • 一、分治算法概念
    • 二、分治算法的关键点
    • 三、分治算法的典型应用
      • 3.1、快速排序
        • 快速排序的算法思想(重点 : 定主元)
        • 单向扫描分区法:
        • 双向扫描分区法:
        • 三指针分区法:适用于数组重复率较高的快排
        • 快排的优化问题:
      • 3.2、归并排序


一、分治算法概念


分治法(divide and conquer,D&C):将原问题 划分 成若干个规模较小而结构与原问题一致的子问题;递归 地解决这些子问题,然后再 合并 其结果,就得到原问题的解。

容易确定运行时间,是分治算法的优点之一。

分治模式在每一层递归上都有三个步骤:

  • 分解(Divide):将原问题分解成一系列子问题;
  • 解决(Conquer):递归地求解各子问题。若子问题足够小,则直接有解;
  • 合并(Combine):将子问题的结果合并成原问题的解。

二、分治算法的关键点


  • 原问题可以一直分解为 形式相同 的子问题,当子问题规模较小时,可 自然求解 (自然求解其实就是直接返回值就是解)
  • 子问题的解通过 合并 可以得到原问题的解
  • 子问题的分解以及解的合并一定是比较 简单 的,否则分解和合并所花的时间可能超出暴力破解,得不偿失、

三、分治算法的典型应用


这儿我们主要学习两种经典的算法:快速排序归并排序。(本文只加以介绍,详细代码请看博主另一篇博客:快速排序和归并排序)

这两种算法都是分治理念的典型应用,但是两者在实现分治理念时有着很大的不同。

在分治算法的三个步骤上:

  • 分解(Divide):归并排序 处理的相对比较简单,但是 快速排序 的核心就在于划分子问题
  • 解决(Conquer):都是利用递归的理念求解
  • 合并(Combine):快速排序 处理的比较简单,但是 归并算法 的核心就在于归并子问题的解

3.1、快速排序


快速排序的算法思想(重点 : 定主元)

按照分治思想:

  1. 划分:先找到一个中位数(主元),将它放到数组中央,使其左边的数都小于它,右边的数都大于它
  2. 对主元左右两边的数进行递归求解
  3. 合并:因为子数组都是原址排序的,所以不需要合并

那么 划分 就是关键

QuickSort(Arr, p, r):
  if p < r
    q = Partition(A, p, r)
    QuickSort(A, p, q - 1)
    QuickSort(A, q + 1, r)

而快排用于划分的算法就是 分区算法:Partition(A, p, r),它的作用就是为我们确定 主元 的位置。


单向扫描分区法:

  • 思路:用两个指针将数组划分为三个区间
  • 扫描指针(scan_pos)的左边是确认小于等于 主元
  • 扫描指针到某个指针(next_bigger_pos)中间为 未知 的,因此我们将第二个指针(next_bigger_pos)称为未知区间末指针,末指针的右边区间为确认大于主元的元素

这个分区算法的思路:首先应该确定一个主元(pivot),我们一般选取数组第一个元素。然后再确定扫描指针和末指针(实际上 Java 中没有指针,这儿只是为了方便理解,我们可以认为这是一个类似游标的东西)
在这里插入图片描述

Partition(A, p, r):
	pivot = A[p];
	sp = p + 1;	// 扫描指针
	bigger = r // 右侧的指针
	while(sp <= bigger):
		if(A[sp] <= pivot)	// 扫描元素小于主元,左指针右移
			sp++;
		else
			swap(A, sp, bigger);	// 扫描元素大于主元,二指针指向的元素交换,右指针左移
			bigger--;
			
	swap(A, p, bigger);
	return bigger;

双向扫描分区法:

  • 思路:先定个主元(pivot),默认就是数组第一个元素,然后头尾指针往中间扫描,从左找到 大于 主元的元素,从右找到 小于等于 主元的元素并将两指针指向的元素交换,继续扫描,直到左侧无大元素,右侧无小元素。
    在这里插入图片描述

  • 结束时也比较特殊,bigger 指向的位置其实就是主元的位置,所以应该交换主元和 bigger 指向的元素。
    在这里插入图片描述

Partition2(A, p, r):
	pivot = A[p];
	left = p + 1;
	right = r;
	
	while(left <= right):
    	// left 不停向右移动,直到遇到大于主元的元素
   		// 下面两个循环都需要考虑极端情况,例如数组本来就有序,或者其他极端情况,需要加上判断
    
    	// 退出时,left 一定指向数组中第一个大于主元的元素的位置
    	while(left <= right && A[left] <= pivot) left++;	
    
    	// 退出时,right 一定指向数组中最后一个小于等于主元的元素
    	while(left <= right && A[right] > pivot) right--;	
    
    	if(left < right)	// 相等的时候交换没什么意义
    		swap(A, left, right);
    	
  // 如果 while 退出时,两者交错,且 right 指向最后一个小于等于主元的元素的位置,
  // 也就是主元的位置
  swap(A, p, right);
  return right;

三指针分区法:适用于数组重复率较高的快排

  • 目的:稍微提高快排的效率
  • 主要理念,让重复的 主元(pivot)不参与排序
  • 思路:使用 三个指针 将数组划分为四个区间
  • next_scan_pos:扫描指针
  • next_bigger_pos:末指针
  • next_less_pos:主元指针
  • 实现:在单向分区扫描法的基础上进行优化。

开始是这样的:
在这里插入图片描述
我们最后要实现的数组是这样的:

在这里插入图片描述

partition(A, p, r):
	int[] res = new int[2];
	int pivot = A[p];
	less = p + 1;
	scan = p + 1;
	bigger = r;
	
	while(scan <= bigger)
    if(A[scan] < pivot) 	// scan 指向元素小于主元
      if(A[less] == pivot)	// 此时 less 已经指向了等于主元的区间首地址
      	swap(A, less, scan);
      	less++;
      	scan++;
      else
      	scan++;
    else if(A[scan] > pivot) // scan 指向元素大于主元
      	swap(A, scan, bigger);
      	bigger--;
    else	// scan 指向元素等于主元
    	if(A[less] != pivot)	// 第一次 scan 扫到了等于主元的元素
    		less = scan;
    	scan++;		// 不管怎样,scan 都要右移
      
  if(less == lo + 1) // 如果上面的扫描完成后,没有发现和主元相等的元素,我们使用的是 单向扫描法
  	swap(arr, bigger, lo);
  	less = bigger;
  else		// 如果存在和主元相同的元素,我们使用 三分法
  	swap(A, --less, p);
  	
	res[0] = less;
	res[1] = bigger;
	
	return res;

快排的优化问题:

前面三种方法,我们选取的主元一直取的是首元素,它取的是有问题的,pivot 并不在中间的部分,我们期望的 pivot 的位置越在中间越好。

如果主元为第一个且恰好最大,那么快排时间复杂度就会退化为 O(n^2)

所以我们要进行优化:
优化方法(在双向扫描分区法中优化):

  • 三点中值法(用的多)
    • 在双向扫描分区法的基础上进行改进,我们选取数组下标:左、中、右,对这三个下标指向的元素进行比较,选取中间值作为主元,然后进行双向分区扫描(这个算法极端情况下和普通双向扫描是一样的)
    • 想要是快排的时间复杂度一直为 n log n 可以使用绝对中值法。
  • 绝对中值法(万无一失)
    • 利用插排取绝对中值,时间复杂度虽然是 nlogn 但是它的常数时间会增大
  • 待排序列表较短时,用插入排序
    • 在双向扫描分区法中,比如数组长度小于等于 10 的时候,可以使用插入排序

3.2、归并排序


  • 归并排序(Merge Sort) 算法完全依照了分治模式
    - 分解:将 n 个元素分成各含 n / 2 各元素的子序列
    - 解决:对两个子序列递归进行排序
    - 合并:合并 两个已排序的子序列以得到结果
  • 和快排不同的是
    - 归并的分解比较随意
    - 重点是合并

比较重要的是,归并排序动用了一个全局辅助数组:helper

全局数组 helper = new int[A.length]

MergeSort(A, lo, hi):
	if(lo >= hi)
		return;
	
	int mid = (lo + hi) >>> 1;
	sort(A, lo, mid);
	sort(A, mid + 1, hi);
	merge(A, lo, mid, hi);
	
merge(A, lo, mid, hi):
	// 先把 A 中的数据拷贝到 helper 中
	copy(A, lo, helper, lo, hi - lo + 1);
	// 需要三个指针进行操作
	left = lo;	// 左边数组的头指针,指向待比较的元素
	right = mid + 1; // 右边数组的头指针,指向待比较的元素
	current = lo;	// 原数组的指针,指向待填入数据的位置
	
	while(left <= mid && right <= hi)
		if(helper[left] <= helper[right])
			A[current] = helper[left];
			current++;
			left++;
		else
			A[current] = helper[right];
			current++;
			right++;
		
	while(left <= mid)
		A[current++] = helper[left++];