求n个元素的全排序(从分治思想超详细解析)

阅读数: 次 2020-05-08

概述

这是一道典型的数据结构考研题，我看目前网上大部分博主讲的都不太通俗易懂，代码质量也参差不齐，本博文将用大白话帮你理解这道典型的分治思想算法题。

1.分治思想

1.1定义

分治算法在维基百科上的定义为：在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治和递归的区别：分治算法是一种处理问题的思想，递归是一种编程技巧

1.2基本步骤

治算法大都采用递归来实现，并且用递归实现的。分治算法的基本步骤为：

1：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2：解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3：合并：将各个子问题的解合并为原问题的解。

2.n个元素的全排序

2.1全排列

首先我们来看什么是全排列，百度百科中如下定义：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

可能大家看定义还是不懂，我们来通过例子列举一下：

一个数字（1）：不需要排列：1

两个数字（1，2），共两种：1，2 | 2，1

三个数字（1，2，3），共六种：1，2，3 | 1，3，2 | 2，3，1 | 2，1，3 | 3，1，2 | 3，2，1

2.2算法思路

我们通过上面的例子不难发现，三个数字的全排列就是我先挑出一个数字例如1，则对2，3排列的规则，不就是用两个数字的规则嘛，产生的就是123和132。

同样，我们通过分治思想分而治之，求n个元素全排列时，我们可以将它逐步分解成一个个小问题：先把第一个元素单独拎出来，然后我们对n-1元素进行全排列，依次类推……直到只有一个数字我们就不需要排列，也可以说我们的一个排列就好了。

而这个第一个元素，我们通过上面的例子就可以知道，就是所有的单个数字嘛，如123先拎出1，然后2，最后3。所以我们需要将第一个元素和之后的每一个元素进行互换来保证第一个元素把所有的数字都拎出来了。

然而当我们一个递归完成之后，我们可能在之前把第一个元素和后面的元素互换了，这时候如果我们直接递归的话原有的顺序会打乱，由于我们是依次让第一个元素和之后的每一个元素进行互换，所以我们需要先把他通过回溯还原成原有数组顺序在进行递推，这里我举个简单的例子：

比如我们对123进行全排序，按照刚刚的思路，我们会走到1和2进行互换，变成213，然后对13进行排列。。

这时候假如我们把213所有的排序好了，接着直接再次重复第一个元素和之后的每一个元素进行互换这个操作的话，就会把2和3进行互换，这可能会出现重复交换的后果，而我们需要的其实是1和3进行互换，所以我们通过再次交换第一个元素和刚刚交换的元素(也就是套个娃)实现回溯，变成123，接着重复以上步骤就可以了

由此，我们给出核心的算法思路：

通过i遍历n个元素的个数
将第一个元素和第i个元素互换位置
交给此时的第一个元素的下一个元素进行排列处理
回溯将交换位置的元素还原，以供其他下降路径使用

2.3代码实现

/**
 * 交换数组的两个位置的元素
 * @param arr
 * @param i
 * @param j
 */
public static  void swap(char[] arr,int i,int j) {
	char temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
/**
 * 求一个数组的全排列
 * @param arr
 * @param k	当前关注点
 */
public static void permutation(char[] arr,int k) {
	if(k==arr.length) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]);
		}
		System.out.println();
		return;
	}
	for(int i=k;i<arr.length;i++) {
		swap(arr,i, k);
		permutation(arr, k+1);
		swap(arr, i, k);
	}
}

测试代码

public static void main(String[] args) {
	//将一个String改为char数组，打印所有排列形式
	char data[]= "ABC".toCharArray();    //转化为char型数组语句
	
	permutation(data,0);    //传data数组
}

3.海量数据处理

这里再介绍一下分治思想的具体例子，可能面试也会问这样的问题，帮助我们更好的理解分治这种思想的实际应用场景：

给 10GB 的订单文件按照金额排序这样一个需求，看似是一个简单的排序问题，但是因为数据量大，有 10GB，而我们的机器的内存可能只有 2、 3GB ，总之就是小于订单文件的大小因而无法一次性加载到内存，所以基础的排序算法在这样的场景下无法使用。

要解决这种数据量大到内存装不下的问题，我们就可以利用分治的思想。我们可以将海量的数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。实际上，利用这种分治的处理思路，不仅仅能克服内存的限制，还能利用多线程或者多机处理，加快处理的速度。

这就是类似于我们的桶排序，桶排序其实就是彻底的分治思想的体现，具体用桶排序的解决方案详情见我的另一篇博客《复杂度分析，递归算法，排序算法最强入门攻略》

结语

这里要感谢廉晓庆和王云龙两位同志，要不是他们的帮忙，我可能一辈子都理解不了这个🐕☀的全排序😭

话不多说，就是🐂🍺