第五章,归纳法,Induction。
对于带有参数n的问题,在寻找这类问题的解时,有时可以从求解一个带有小一点参数的相同问题开始,如参数是n-1,n/2等,然后再把解推广到参数为n的情况。这个过程可以用数学归纳法证明。如数学归纳法有个前提条件一样,只有在知道如何求解参数小于n的同样问题时,这个递推归纳的过程才能进行。所以这种算法过程也很容易的可以写成递归。
典型的例子,选择排序,插入排序,基数排序等等。这里给出几个典型的程序。
基数排序
参考http://www.cnblogs.com/dlutxm/archive/2011/10/20/2219321.html
这位博主的代码很有意思,radix=10,但是他没有用到10个表来保存对应的数据,而是一种很巧妙的方法。不过我觉得代码里对i滥用了,还有计算第k个位置数据的radix重复计算了一次,所以我用了一个数组保存第一次计算的结果。空间换时间,也或许并没有换到时间。
基数排序的时间复杂度是O(kn),虽然是线性时间复杂度,但并不一定表示比快速排序,归并排序速度快,而且基数排序用于无符号数,对其他类型的数据支持的就不太好了。
基数排序有两个需要注意的地方,一个就是要从低位向高位排序,另一个问题就是同一数位的排序子程序要使用稳定排序。先给出链接http://www.cnblogs.com/sun/archive/2008/06/26/1230095.html。
代码如下,
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class Type>
void print(vector<Type>& A)
{
for(unsigned int i=0;i<A.size();i++)
{
cout << " " << A[i];
}
cout << endl;
}
void radixsort(vector<unsigned int>& A)
{
if(A.size()<2)
return;
const int radixNum = 10;
vector<unsigned int> cnt(radixNum,0);
vector<unsigned int> tmp(A.size(),0);
vector<unsigned int> tq(A.size(),0);
int d = 1;
for(unsigned int i=0;i<A.size();i++)
{
int c = 1;
unsigned int p = A[i];
while(p/10)
{
p = p / 10;
c++;
}
if(c>d)
d = c;
}
int r = 1;
for(unsigned int i=0;i<d;i++)
{
for(unsigned int j=0;j<radixNum;j++)
cnt[j]= 0;
for(unsigned int k=0;k<A.size();k++)
{
int p = A[k]/r;
int q = p % 10;
tq[k] = q;
cnt[q]++;
}
for(unsigned int j=1;j<radixNum;j++)
cnt[j] += cnt[j-1];
for(int k=A.size()-1;k>=0;k--)
{
int s = tq[k];
tmp[cnt[s]-1] = A[k];
cnt[s]--;
}
for(unsigned int j=0;j<A.size();j++)
A[j] = tmp[j];
r *= 10;
}
}
int main()
{
int N = 16;
vector<unsigned int> A(N,0);
for(int i=0;i<N;i++)
A[i] = rand() % 1000;
print(A);
radixsort(A);
print(A);
return 0;
}
当学会使用rand()之后,测试也简单多了。
原文链接: https://www.cnblogs.com/Frandy/archive/2012/05/15/algorithm_course_5_1.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/50339
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!