算法分析学习笔记⼆蛮⼒法
算法设计与分析之⼆蛮⼒法
⽬录
1.蛮⼒法的设计思想
2.蛮⼒法优点
3. 冒泡排序分析
4. 选择排序分析
5. 蛮⼒法中冒泡排序与选择排序的时间空间复杂度分析
6. 蛮⼒法C语⾔实现
7. 算法稳定性的问题
8. 百钱买百鸡的问题
9. 补充：鸡尾酒排序法
10.蛮⼒法的思考
作为算法设计技术中最简单的⼀种设计策略，蛮⼒法从最先开始接触编程语⾔时就⼀直伴随着我们。
1. 蛮⼒法的设计思想
课本上的定义：蛮⼒法是指⼀种简单直接
1.蛮⼒法⼜称为枚举法，穷举法，暴⼒法。
2.蛮⼒法是指采⽤遍历（扫描）技术，即采⽤⼀定的策略将待求解问题的所有元素依次处理⼀次，从⽽出问题的解。依次处理所有
元素是蛮⼒法的关键，为了避免陷⼊重复试探，应保证处理过的元素不再被处理。
蛮⼒法解决问题的⽅法
根据问题中的条件将可能的情况⼀⼀列举出来，逐⼀尝试从中出满⾜问题条件的解。但有时⼀⼀列举出的情况数⽬很⼤，如果超过了我们所能忍受的范围，则需要进⼀步考虑，排除⼀些明显不合理的
情况，尽可能减少问题可能解的列举数⽬。
蛮⼒法解决问题的算法设计：
1）出枚举范围：分析问题所涉及的各种情况。
2）出约束条件：分析问题的解需要满⾜的条件，并⽤逻辑表达式表⽰。
2.蛮⼒法优点
1. 逻辑清晰，编写程序简洁
2. 对于⼀些重要的问题（⽐如：排序、查、矩阵乘法和字符串匹配），可以产⽣⼀些合理的算法
3. 解决问题的实例很少时，可以花费较少的代价
4. 可以解决⼀些⼩规模的问题（使⽤优化的算法没有必要，⽽且某些优化算法本⾝较复杂)
5. 可以作为其他⾼效算法的衡量标准
3. 冒泡排序分析（稳定性排序⽅法）
第i趟排序对序列的前n-i+1个元素从第⼀个元素开始依次作如下操作：相邻的两个元素⽐较⼤⼩，若前者⼤于后者，则两个元素交换位置，否则不交换位置。该n-i+1个元素中最⼤值元素移到该n-i+1个元素的最后。冒泡排序⽅法⽐较适合于参加排序的序列的原始状态基本有序的情况。
4. 选择排序分析（⾮稳定性排序⽅法）
选择排序开始的时候，扫描整个序列，到整个序列的最⼩记录和序列中的第⼀个记录交换，从⽽将最⼩记录放到它在有序区的最终位置上，然后再从第⼆个记录开始扫描序列，到n-1个序列中的最⼩记录，再和第⼆个记录交换位置。⼀般地，第i趟排序从第i个记录开始扫描序列，在n-i+1（1≤i≤n-1）个记录中到关键码最⼩的记录，并和第i个记录交换作为有序序列的第i个记录。
每⼀趟排序从序列中未排序的元素中选择⼀个值最⼩的元素，将其置于没有排好序的元素的最前⾯。已排好序的元素不必交换。
5. 蛮⼒法中冒泡排序与选择排序的时间空间复杂度分析
1.选择排序：
平均时间复杂度o(n^2 )
最好时间复杂度o(n^2 )
最坏时间复杂度o(n^2 )
空间复杂度o(1)
2.冒泡排序：
平均时间复杂度o(n^2 )
最好时间复杂度o(n)
最坏时间复杂度o(n^2 )
空间复杂度o(1)
6.1蛮⼒法中冒泡排序C语⾔实现
#include<stdio.h>
void maopaopaixu(int s[],int n);
void main()
{
int s[20];
int i;
int n;
printf("请输⼊要输⼊的个数：");
scanf("%d",&n);
printf("请输⼊要排序的序列：\n");
for(i =0; i < n; i++)
{
scanf("%d",&s[i]);
}
maopaopaixu(s,n);
printf("排序后的序列：\n");
for(i =0; i < n; i++)
{
printf("%d\t",s[i]);
}
}
void maopaopaixu(int s[],int n)
{
int i, j;
int temp;c语言的冒泡排序算法
for(i =0; i < n; i++)
{
for(j =0; j < n-1; j++)
{
if(s[i]< s[j])
{
temp = s[i];
s[i]= s[j];
s[j]= temp;
}
}
}
}
6.2蛮⼒法中选择排序C语⾔实现
#include<stdio.h>
void suanzepaixu(int s[],int n);
void main()
{
int n;
int i;
int s[20];
printf("请输⼊要输⼊的个数");
scanf("%d",&n);
printf("请输⼊要排序的数据\n");
for(i =0; i < n; i++)
{
scanf("%d",&s[i]);
}
suanzepaixu(s,n);
for(i =0; i < n; i++)
{
printf("%d\t",s[i]);
}
}
void suanzepaixu(int s[],int n)
{
int i,j;
int k;
int temp;
for(i =0; i < n; i++)
{
k = i;
for(j = i +1; j < n; j++)
{
if(s[j]< s[k])
{
k = j;
}
}
if(k != i)
{
temp = s[k];
s[k]= s[i];
s[i]= temp;
}
}
}
7.算法稳定性的问题
冒泡排序：
冒泡排序就是把⼩的元素往前调或者把⼤的元素往后调。⽐较是相邻的两个元素⽐较，交换也发⽣在这两个元素之间。所以，如果两个元素相等，不⽤交换；如果两个相等的元素没有相邻，那么即使通过前⾯的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是⼀种稳定排序算法。
选择排序：
选择排序即扫描整个序列，到整个序列的最⼩记录和序列中的第⼀个记录交换，从⽽将最⼩记录放
到它在有序区的最终位置上，然后再从第⼆个记录开始扫描序列，到n-1个序列中的最⼩记录，再和第⼆个记录交换位置。⼀个序列当如果当前元素⽐⼀个元素⼩，⽽该⼩的元素⼜出现在⼀个和当前元素相等的元素后⾯，那么交换后稳定性就被破坏了。因此选择排序是⾮稳定性的。
8.百钱买百鸡问题
数学家张丘建提出百鸡百钱问题，今有鸡翁⼀，值钱五，鸡母⼀，值钱三，鸡雏三，值钱⼀。百钱买百鸡，问鸡翁，鸡母，鸡雏各⼏何？翻译后：设鸡翁，鸡母，鸡雏分别为x,y,z，给出⼀百钱要买百鸡。如果全买公鸡最多买20只，显然x在0—20之间，同理y的取值在0-33之间，所以根据分析，不难⽤枚举法求出问题的所有符合情况的解。
这是个经典问题，从我们学数学就避不开的问题，⽤蛮⼒法实现应该是最不费脑筋的。⾸先，简单分析⼀下枚举范围，都买公鸡最多⼆⼗只，x的范围0-20，都买母鸡最多30只，y的范围0-30。
#include<stdio.h>
//鸡翁x，鸡母y，鸡雏z
void main()
{
int z =0;
int x, y;
//鸡翁的数量变化范围
for(x=0; x <20; x++)
{
//鸡母的数量变化范围
for(y =0; y <33; y++)
{
z =100- x - y;
//鸡雏的受制约范围
if(z %3==0&&5* x +3* y + z /3==100)
{
printf("x = %d,y = %d,z = %d\n",x,z,y);
}
}
}
}
9.鸡尾酒排序
鸡尾酒排序法，⼜名双向冒泡排序法，算法传统冒泡法的⼀点改进。但是对于鸡尾酒排序，算法的时间复杂度与空间复杂度并没有改进。
  不同的是排序的交换次数。某些情况下鸡尾酒排序⽐普通冒泡排序的交换次数少。⽐如{2,3,4,1}，鸡尾酒排序只需交换2次，⽽冒泡排序需要三次。总体上，鸡尾酒排序可以获得⽐冒泡排序稍好的性能。但是完全逆序时，鸡尾酒排序与冒泡排序的效率都⾮常差。
  鸡尾酒排序的思想就是在从前往后依次循环依靠邻近数据交换实现结果的同时，依次从后往前循环数据交换。前者交换获取未排序最⼤值，⽽后者交换获取未排序最⼩值。实现过程如下图：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。