|
3月30日
c++常用算法1 算法: 可以理解为解决问题的方法.
2 算法的五个重要特征:
1) 有穷性 // 必须要执行有限步 2) 确切性 // 每一步的含义必须要明确 3) 输入 // 算法必须有初始条件,或者输入,来表述运算对象的初始状态 4) 输出 // 必须有执行的结果产生,否则这个算法没有实际意义 5) 可行性 // 必须能够有效地实施 算法的执行效率越高,所需的资源越少,我们说这个算法的复杂性越低.对于算法来说,复杂度越低越好.
一个算法是否合格,首先要考虑的是程序是否正确,然后再考虑运行速度,其它方面相对可以次要一点. 容易造成程序可靠性不强的原因: 没有初始化的指针和变量. 常用的算法设计策略: 蛮力法,递归,分治法,模拟法,贪心算法,优化法. 3 贪心算法一般来说可以找到一个相对好的解决方案,但是不一定是最好的.
比如背包问题: 如果有一个可以装固定重量的背包,和一些不同重量的物品,如何装最大重量的物品到背包中? 这个问题用贪心算法就不一定能够找到最好的解决方案,如背包可装8KG,而有三块金块分别为6KG,5KG,3KG,那么如果按照贪心法来解决,则只会装一块6KG的金块,而按照正常思路,肯定是选择5KG和3KG的金块装入背包. 4 常用的重要排序算法有如下几种:
1) 选择排序法 时间复杂度: O(N*N) 步骤：<1>从无序数据中找出最小的 <2>跟已排序数据后面的元素交换 下面是一个选择排序的实现: void select( int* p, int len ) { for( int i=0; i<len-1; i++ ){ int pos=i;//i是已经排好序的数据个数，同时表示未排好序的元素下标； for( int j=i+1; j<len; j++ ){ if( p[j]<p[pos] ) pos = j;//找出最小的元素的下标 } swap(a[i],a[pos]); } } } 2) 冒泡排序法 时间复杂度: O(N*N) 是一种多轮排序的方法,每轮都要比较相邻的数据对,按单一方向交换,直到所有数据都排好顺序为止. 最好用于基本有序的有序数据排序； 下面是一个冒泡排序的实现: void bubble( int* p, int len ) { bool bSwapped; do { bSwapped = false; for( int i=1; i<len; i++ ){ if( p[i-1] > p[i] ){ // 由该条件确定是升序还是降序,此处为升序(将大的数往后放，一轮结束把最大元素的位置确定好了) swap( p[i-1], p[i]); // 交换相邻的两个数据 bSwapped = true; } } } while( bSwapped ); } 3) 插入排序法 时间复杂度: O(N*N)
先认为第一个元素是已经排好顺序的,然后依次把后面的元素"插入"到这个已经排好序的数列中正确的位置. 步骤：<1>把要处理的数据保存一份； <2>再依次看（左）面的元素，凡是比它大的，都向后移动一个位置（它自身的位置），直到左边的元素不比它大时或最左边时为止； <3>将其插入到空位置中； 下面是一个插入排序的实现: void insert( int * p, int len ) { for( int i=1; i<len; i++ ){ // 从第二个元素开始 int j; int cur=p[i]; //<1> for( j=i; j>0 && p[j-1]>cur; j-- ) // 从已经排好序的数列中的最后一个位置向前比较直到确定正确的位置 p[j] = p[j-1]; //<2>腾出空间 if( j!=i ) p[j] = cur; //<3>把待插入的数据放到正确的位置 } } 4) 快速排序法 时间复杂度: O(N*log N) 被认为是比较排序中效率最高的方法. 思想是由一个分界值把数组分成两部分, 然后把大于等于分界值的数据集中到一边,而把小于分界值的数据放到另外一边, 然后不断对分开的部分再做同样的操作,直到排好顺序为止. 下面是一个利用原地分组的方法实现的快速排序:
void swap( int* a, int* b ) { int c = *a; *a = *b; *b = c; } void quick( int* p, int len ) { if( len<=1 ) return; swap( *p, *(p+(len/2)) ); //swap(*p,p[len>>1]) int pivot = *p; int* l=p+1; //以第一个为分界值，指定到第二个元素； int* r=p+len-1; //指定到最后一个元素； while( l<r ){ while( l<r && *l<pivot ) l++; //从左往右找，找比分界值小的； while( r>=l && *r>=pivot ) r--; //从右往左找，找比分解值大的或相同的值； if( l<r ) swap( l, r ); } if( *r < pivot ) swap( p, r ); quick( p, r-p ); //对左边组再排序，（r-p）元素的个数 quick( r+1, len-1-(r-p) ); //对右边组再排序，（len-1-(r-p)）元素的个数 |
|
|
