蛮力法

一、什么是蛮力法

  蛮力法，又称枚举法，是基础的算法之一。这是一种算法思想，顾名思义，就是将问题的可能结果全部都列举出来，再根据列举的结果根据问题的约束条件选择出问题的解。
  所依赖的技术最主要的是遍历，重复步骤。往往用这种算法去求解问题，时间复杂度会很大。但是确是最简单，直白容易想到的解法。
  思想还是得用实例来体现的，不然会感觉这个思想的东西只是思想，我们不会用的话，感觉这些思想没什么用，所以要用起来。选择排序是蛮力法的一个例子，我们应该抓住的是如何将这种思想应用起来，这才是关键。

二、例子——选择排序

1.问题

  选择排序方法对一个序列进行升序排序

2.基本思想

  听到选择排序，顾名思义，这是一种有选择的排序方法。怎么选择，如何体现蛮力？
  选择，就是将序列分为有序跟无序，这两部分，刚开始，有序部分的元素肯定为空集。接下来，就是所谓的蛮力的部分，开始不管三七二十一，就在无序的部分开始找啊，找到在无序中最小的数，将把最小的数与无序序列的第一个元素交换。到这一步后，又开始划有序与无序部分，这个时候，要把刚才找的最小的数放到有序部分中。这时，有序部分的元素就加1了，所谓排好一个了，还有剩下的元素在无序序列中。再开始蛮力部分。一直这样更新有序无序序列，蛮力；更新有序序列，蛮力。直至无序序列中没有元素。这样我们就实现了排序。

  大概想法是这样的，现在开始扣细节。因为这只是我们想法，计算机认识吗？当然不认识。我们要把我们的思想改得细致点。好了，我们知道蛮力法最重要的是遍历和重复步骤。我们要对整个序列进行排序，根据刚才的思想，序列中的每一个元素都会被挑出来重新放到有序序列中，所以，在这里可以用一个遍历去实现。然而，对于每一个的挑选的过程，是很蛮力的，就是一直在无序序列中找，比较。直至到无序序列的结尾。所以这也可以用遍历去实现。所以整体框架就是
重复（次数为原始序列个数，为更新有序与无序序列）
  开始找最小的值
    在无序序列中找到最小值
    交换值在无序序列中的位置

3.代码实现

void SelectSort(int array[],int n)
{
	int i,j,index,temp;
	for(i=0;i<n-1;i++)  //最外层遍历
	{
		index=i;//无序区的第一位
		for(j=i+1;j<n;j++) //开始找无序区的最小元素
			if(array[j]<array[index] index=j;   //记录最小值
		if(index!=i)
		{
		  temp=array[i];array[i]=array[index]; array[index]=temp; //将最小值放到有序区中
		}
	}
}

总结

对于蛮力法的应用，首先要明白它的特征，就是遍历，重复步骤的过程。要分析问题，哪些东西是在求解过程中是重复的，将这些东西提炼出来，先形成一个初步的求解轮廓，是不是这样就可以求解问题，然后在将这个轮廓逐渐细化。逐渐清晰，再转化为适用计算机的求解步骤，最后代码实现。蛮力法，就是简单粗暴，时间复杂度和空间复杂度往往较大，但是确是首先想到的方法。