良许Linux教程网 干货合集 蛮力法求解排序问题

蛮力法求解排序问题

蛮力法(brute force method,也称为穷举法或枚举法)是一种简单直接地解决问题的方法,常常直接基于问题的描述,所以,蛮力法也是最容易应用的方法。

蛮力法求解排序问题

选择排序思想:

在选择排序开始的时候,扫描整个列表,找到最小元素,然后和第一个元素交换,将最小元素放到它在有序列表的最终位置上。然后我们从第二个元素开始扫描列表,找到最后(n-1)的元素的最小值,再和第二个元素交换,把第二小的元素放在它在列表中的最终位置上。一般来说,在对列表做第 i 遍扫描的时候,(i的值从0~n-2),该算法再最后(n-i)个元素中寻找最小元素,然后拿它和Ai交换,在(n-1)遍之后,该列表就排好序了。

下面是我的代码实现:C++

#include
using namespace std;
int main()
{
   int i,j,temp,minn,N;
   cin>>N;
   int *Arr=new int[N];
   for(i=0;i>Arr[i];

   for(i=0;ifor(j=i+1;jif(Arr[minn]>Arr[j])
               minn=j;//记录最小值的下标
       }
       temp=Arr[minn];     //交换Arr[minn]和Arr[i]。
       Arr[minn]=Arr[i];
       Arr[i]=temp;
   }

   for(i=0;i" ";
   return 0;
}

算法分析:

输入的规模是由元素的个数n决定的,基本操作是键值比较 Arr[minn]>Arr[j]。这个比较的执行次数仅仅依赖于数组的规模,

C(n)=∑[i=0,i=N-2] ∑[j=i+1,j=N-1]=∑[i=0,i=N-2] ((N-1)-(i+1)+1))=∑i=0,i=N-2=(n-1)*n/2

即对于任何输入来说,选择排序都是一个时间复杂度为Θ(n2)的算法。键的交换次数是Θ(n) 这使得选择排序性能较优。

以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

img
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

邮箱地址不会被公开。 必填项已用*标注

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部