janqii

原来ABC还可以译作“原理，原则”来着，呵呵。。。偶然发现。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
这两天在读《设计模式精解》（其实该叫做“设计模式入门导读”），设计模式是从建筑学借来的一个词汇，是指“在某一个情景下的问题解决方案”。

在软件设计中，“四人团”总结提炼出23种模式（设计模式入门导读只列举了10种），分为结构型（Facade,Adapter,Bridge,Decorator等），行为型（Strategy，Observer等）和创建型 （Abstract Factory,Singleton等）三种大的类别。

这些模式总体上遵循一些原则：
1、封装变化。
2、优先使用对象组合，而不是优先使用继承

另外，关于对象的理解。
站在概念规格上，把对象看成是具有责任的实体；而非仅仅是在实现规格上，把它看作数据和方法的集合。 阅读全文
类别：设计模式 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/5182eb09ce178b32b1351d86.html

unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;

while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}

return (hash & 0x7FFFFFFF);
}

// RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;

while (*str)
{
hash = hash * a + (*str++);
a *= b;
}

return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;

while (*str)
{
hash ^= ((hash << 5) + (*str++) + (hash >> 2));
}

return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
unsigned int hash             = 0;
unsigned int test             = 0;

while (*str)
{
hash = (hash << OneEighth) + (*str++);
if ((test = hash & HighBits) != 0)
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}

return (hash & 0x7FFFFFFF);
}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x    = 0;

while (*str)
{
hash = (hash << 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
hash &= ~x;
}
}

return (hash & 0x7FFFFFFF);
}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;

while (*str)
{
hash = hash * seed + (*str++);
}

return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;

while (*str)
{
hash += (hash << 5) + (*str++);
}

return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash = 0;
int i;

for (i=0; *str; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
}
}

return (hash & 0x7FFFFFFF);
} 阅读全文
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/9402270b263c24990a7b8229.html

如果使用概率算法的话，虽然速度较快，但会有一定的误差，而且这种误差还不稳定。
考虑使用确定算法，一般来讲，单词数量越多，第n个需要进行比较的单词操作时间越长。
今天在bbs上看到一种字典序的方法，每个单词与已经存在的单词的比较的时间花费只和自身的长度有关。也就是这样做得：
单词中的第i（0<i<n+1）位字母有26（对应26个英文字母）个预置位置，其(ASII－'a')值为其占有的位置，每个位置设置1个标志位标识该位是否是单词结束字母位置，定义每个对象都包含26个预留位置、1个标志符和指向下一个对象的指针。每个单词只需要按照顺序寻找第i位字母的对应位置，如果位置被占，直接寻找第i+1个字母的位置，如没有被占，就把这个位置new出来，直到最后一个字母，然后查看最后一位字母的位置的标识，如是被修改过，则是重复出现的单词，否则是新单词。  叙述的很乱，还是直接上代码吧。

＠感谢LevinLin同学的贡献

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/ec5ba7bcbf08b90619d81ff8.html

1、随机排列数组

方法1：给每个元素A[i]随机分配一个优先级p[i]，然后按照优先级对数组A进行排序。例如初始A=<1,2,3,4>而且随机得到的优先级数组P=<36,3,97,19>，则得出随即数组B=<2,4,1,3>。这个过程称为PERMUTE_BY_SORTING。时间复杂度为O(nlgn)

方法2：原地排列给定数列。在第i次迭代时，元素A[i]是从元素A[i]到A[n]中随机选取的。时间复杂度为O(n)

n=length[A];

for i=1 to n

do swap(A[i], A[RANDOM(i,n)])

2、生日悖论

对于n=365，如果k=28，即如果至少有28个人，则可以期望至少有1对人的生日相同。

在n天中，k个人生日互不相同的组合有P(n,k)中，所有的组合（包括相同的）有n的k次方中，记为n^k，则k个人生日互不相同的概率为P(n,k)/n^k。

当k>=23时，P(n,k)/n^k<50%，则1-P(n,k)/n^k>50%，也就是说，当一个房间里有23个人时，至少有两个人生日相同的概率大于50%。

3、赠券收集者问题

一个人如果想要收集齐b种不同赠券中的每一种，大约需要b*lnb张随机得到的赠券才能完成。

用球和盒子的模型说明：把相同的球随机投到b个盒子中去。  

1>有多少个求落入指定的盒子中？服从二态分布(k；n，1/b)，则期望值为n/b

2>在给定的盒子中至少一个球之前，平均需要投多少个球？服从几何分布，概率为1/b，成功前的期望个数为1/(1/b)=b

3>在每个盒子至少有一个球之前，要投多少个球？

我们称一次投球中落入一个空盒子为“击中”。

将n次投球分成b个阶段，阶段i包括第i-1次击中到i次击中之间的投球次数。第i阶段的每一次投球有i-1个盒子有球，n-k+1个盒子是空的，这样第i阶段的所有投球击中的概率都为（n-k+1）/b

用ni表示第i阶段的投球次数

n=SUM(ni)<i=1 to b>    每个随机变量ni都服从几何分布，成功概率为(n-k+1)/b

则      E(ni)=b/(b-k+1)

E(n)=E(SUM(ni))=SUM(E(ni))=SUM(b/(b-k+1))=b*SUM(1/(b-k+1))

根据调和级数的界可得 E(n)=b*(b+……+1/2+1)=b*(ln(n)+O(1))

所以大约投球b*lnb次就可以满足条件

4、最长序列问题

抛一枚均匀硬币n次，期望看到连续正面的最长序列有多长？答案是O(lgn)。

用X(i,k)=I{A(i,k)}表示对应于长度为k的序列开始于第i次抛硬币的指示器随机变量。

定义 X=SUM(X(i,k))<i=1 to n-k+1>

则     E(X)=E(....)=...=SUM(1/2^k)=(n-k+1)/2^k

令     k=clgn，对某个常数c，有

E(X)=......=O(1/n^(c-1))

当c<1/2时，E(X)=O(n^(1/2))，期望会有大量长为1/2*lgn的序列，因此，最长序列期望值长度为O(lgn)

5、苏格拉底的捡麦穗问题

怎么才可以捡到期望的最大麦穗呢？

方法是在前k次中不捡麦穗，但是比较找出最大麦穗并记住，在后面的n-k个麦穗中第一次遇到比前k个中的最大的还要大的麦穗就捡起，就是目标麦穗。如果没有发现比前k个还要大的，就捡最后一个第n个。

这里的关键是取好k的值，使得能够捡到最大的麦穗的可能性最大，根据算法导论（中文版）第67和68页分析，这个k值取n/e时，则可以至少有1/e的概率渠道最大的麦穗。k=n/e

阅读全文
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/a23e93df0fa9fdadcd1166d8.html

Problem D:【算法】:排列的字典序问题

Time Limit:2000MS Memory Limit:65536K
Total Submit:200 Accepted:66

Description

n个元素{1,2,..., n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：

任务：给定n 以及n 个元素{1,2,..., n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
Input

第1 行是元素个数n(n < 15)。接下来的1 行是n个元素{1,2,..., n }的一个排列。

Output

第一行是字典序值，第2行是按字典序排列的下一个排列。

Sample Input
8
2 6 4 5 8 1 7 3

Sample Output
8227
2 6 4 5 8 3 1 7
-----------------------------------------------------------------------------------------------------------------------

字典序法：
字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
字典序算法如下：
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即   j=max{i|pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pi，pk
4）再将pj+1......pk-1pkpk+1pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。
例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
自右至左找出排列中第一个比右边数字小的数字4          839647521
在该数字后的数字中找出比4大的数中最小的一个5        839647521
将5与4交换                                                                         839657421
将7421倒转                                                                          839651247
所以839647521的下一个排列是839651247。

--------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

void dict_sort(int arr[],int size);
int find_first_small(int arr[],int size);
int find_smallest(int arr[],int start,int size);
void swap(int arr[],int idx1,int idx2);
void converse(int arr[],int start,int end);
int factorial(int n);
int find_position(int arr[],int size,int *pos);

int main(void)
{
int i,n,val;
int pos;
int *a;

scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++)
{
   scanf("%d",&a[i]);
   //a[i]=val;
}

dict_sort(a,n);
find_position(a,n,&pos);

printf("%d\n",pos);
for(i=0;i<n;i++)
   printf("%d ",a[i]);

return 0;
}

void dict_sort(int arr[],int size)
{

int idx1;
int idx2;

idx1=find_first_small(arr,size);

if(idx1==-1)
{
   printf("the last one...\n");
   return ;
}

idx2=find_smallest(arr,idx1+1,size);
swap(arr,idx1,idx2);
converse(arr,idx1+1,size-1);
}

int find_position(int arr[],int size,int *pos)
{
int i,nr;
int sum=0;
for(i=0;i<size-1;i++)
{
   nr=get_counter(arr,i,size);

   if(nr>0)
    sum += nr*factorial(size-i-1);
}
*pos=sum+1;

return *pos;
}

int factorial(int n)
{
int rt=1;
while(n>0)
{
   rt *=n;
   n--;
}
}

int find_first_small(int arr[],int size)
{
int i=size-1;

for(i=size-1;i>=0;i--)
{
   if(arr[i-1]<arr[i])
    return i-1;
}

return -1;
}

int get_counter(int arr[],int start,int size)
{
int i;
int counter=0;
int start_val=arr[start];

for(i=start+1;i<size;i++)
{
   if(arr[i]<start_val)
    counter++;
}

return counter;
}

int find_smallest(int arr[],int start,int size)
{
int i;
int pos=start;
int start_val=arr[start-1];
int key=arr[start];

for(i=start+1;i<size;i++)
{
   if(arr[i]>start_val&&arr[i]<key)
   {
    key=arr[i];
    pos=i;
   }

}

return pos;
}

void swap(int arr[],int idx1,int idx2)
{
int tmp=arr[idx1];

arr[idx1]=arr[idx2];
arr[idx2]=tmp;
}

void converse(int arr[],int start,int end)
{
int i=end;

for(i=end;i>=(start+end+1)/2;i--)
{
   swap(arr,end-i+start,i);
}
}

阅读全文
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/a181ba5b08102b8d800a18a6.html

国王招来100个囚犯，对他们说：你们犯的是死罪，本应该将你们统统杀掉，但我慈悲为怀，给你们一次求生的机会。15分钟以后，你们将被关进一个有100间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送）

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。院子里有一盏路灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，如果灯泡坏了或是电路出了故障会马上修好，当然修理人员不会改变灯的状态（开或关）。

除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。

牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。

好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放： 若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。当然要有证据！因为我只会给你们一次机会，如果向我证明的那个人无法自圆其说，你们就全部砍头。所以，要珍惜这次机会。如果你们永远做不到我的要求，你们就全部关到死。

现在给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流。

-------------------------------------------------------------------------------------------------------------

第一天出来的人作为“计数者”（第一个出来的人确定自己是“计数者”，其他人确定自己不是“计数者”）

如果是“计数者”就把灯打开（关闭的情况下打开），计数+1，若灯开着的话就什么也不做

如果不是“计数者”，如果是第一次出来放风而且灯开着就关闭它，否则什么也不做

当“计数者”的 counter=100的时候就可以想国王申请走人了。

-------------------------------------------------------------------------------------------------------------

这种算法需要多长的时间才可以获得释放呢，写代码验证之。答案是10000天左右，也就是20-30年的时间，够漫长的。不知道还有没有其他更好的方法。

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;

int   getDays(void);
bool not_selected(vector<int> v,int key);

int main(void)
{
cout<<getDays()<<endl;
return 0;
}

int getDays(void)
{
int observer=-1;
int rd=-1;
int counter=0;
int days=0;
vector<int> prison;
volatile bool b_light=false;

srand(time(NULL));
observer=rand()%100;
b_light=true;
days++;

while(1)
{
   days++;
   if((rd=rand()%100)==observer)
   {
    if(b_light==false)
    {
     counter++;
     b_light=true;
    }
    if(counter==99)
     break;
   }
   else
   {
    if(b_light&&not_selected(prison,rd))
    {
     prison.push_back(rd);
     b_light=false;
    }
   } //else
} //while

return days;
}

bool not_selected(vector<int> v, int key)
{
for(vector<int>::iterator iter=v.begin();iter!=v.end();++iter)
{
   if(*iter==key)
    return false;
}

return true;
}

阅读全文
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/3756d81afc73f04943a9adae.html

C++ Primer中建议delete一个指针之后，执行ptr=NULL,来让指针指向0，以后再使用ptr，系统就会报错。

--------------------------------------C++ Primer----------------------------------------------------------------

执行语句 delete p; 后，p变成没有定义。

在很多机器上，尽管 p 没有定义，但仍然存放了它之前所指向对象的地址，然而 p 所指向的内存已经被释放，因此 p 不再有效。

删除指针后，该指针变成悬垂指针。

悬垂指针指向曾经存放对象的内存，但该对象已经不再存在了。悬垂指针往往导致程序错误，而且很难检测出来。

一旦删除了指针所指向的对象，立即将指针置为 0，这样就非常清楚地表明指针不再指向任何对象。

阅读全文
类别：c/c++ 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/e430a396d1dfe047d1135eca.html

散列表是普通数组的推广。

设计散列表主要是对哈希函数和处理冲突碰撞的选择和设计，好的哈希函数h可以使关键字比较均匀的散列在哈希表中，冲突较少。所谓“好”的哈希函数的主导思想，是使h尽可能地随机，减少碰撞，但是不可能完全避免碰撞，因为关键字域的势 |U|>m，m为散列表的槽数，总会有两个不同的关键字映射到同一个槽中，产生碰撞。

1、哈希函数

一个好的哈希函数应（近似地）满足简单一致散列的假设：每个关键字都等可能的散列到m个槽位的任何一个中去，并与其他的关键字已被散列到哪个槽位中无关。

不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。

算法导论中列举了四种哈希函数：直接定址法、除法散列法、乘法散列法和全域散列法。

其中除法散列法和乘法散列法利用了启发式的方法，第三个利用了随机化的技术。

a、除法散列法（模除法）

h(k)=k mod m

m的取值常常是与2的整数幂不太接近的质数（m是指散列表的槽数）。

b、乘法散列法

h(k)=|m*(k*A mod 1)| （取底）

用关键字k乘以常数A（0<A<1），并取出kA的小数部分。然后用m乘以这个值，对结果取底。

对 m 的选择没有特别的要求，一般选择为 2 的整数次幂

Knuth认为 A=（sqrt（5）-1）=0.6180339887......，取这个值比较理想

c、全域散列

h(k)=((a*k+b) mod p) mod m   （哈希函数族）

选择一个足够大的质数p，使得每一个可能的关键字k都落到0到p-1之间（包括0和p-1）。

Zp表示集合｛0，1，……，p-1｝，Zp*表示集合｛1，2，……，p-1｝。

容易知道p>m（p>=|U|>m）

a属于Zp*，B属于Zp

从函数族中随机的选取一个作为哈希函数

d、在严蔚敏的数据结构中还介绍了其他的构造哈希函数的方法（比如平方取中法，折叠法等）

2、处理碰撞的方法

a、哈希链接法

把冲突的关键字存储在冲突槽的链表中

在简单一致散列的假设下，一次不成功查找的期望时间为O（1+α），平均情况下一次成功的查找也需要同样的时间

b、开放寻址法

线性探测    h(k,i)=(h'(k)+i) mod m,i=0,1,……，m-1

二次探测   h(k,i)=(h'(k)+c1*i+c2*i*i) mod m     严蔚敏的数据结构中 c1=0，c2=-1

双重哈希（再哈希法） h(k,i)=(h1(k)+i*h2(k)) mod m

每一个关键字的探查序列

<h(k,0)，h（k,1）,……，h(k,m-1)>    

直到探寻到合适的位置为止

c、完全散列法

基本思想比较简单，采用两级的散列方案，每一级都采用全域散列。

有点类似哈希链接法，只不过，在冲突槽的链表上再采用一次全域哈希。

d、严蔚敏的数据结构中还介绍了 建立一个公共溢出区 的方法

------------------------------------一个小例子（哈希链接法 处理冲突）-------------------------------------------------

/*
* 算法导论 第十一章 散列表
*
* 哈希函数：模除散列法
* 冲突避免：哈希链接法
* */

/* 输出：14 1

               1   0

*/

#include<stdio.h>
#include<stdlib.h>

struct hash_node{
struct hash_node *next;
int data;
};

struct hash_table{
struct hash_node *base;
unsigned int count;
unsigned int size;
};

unsigned int hash1(int key, int m)
{
/*int rt=-1;*/
return key%m;
}

unsigned int hash2(int key, int m)
{
return 1+(key%(m-1));
}

unsigned int hash(int key, int m, int i)
{
return (hash1(key,m)+i*hash2(key,m))%m;
}

void chain_insert(struct hash_table *tbl, int key)
{
unsigned int pos=-1;
struct hash_node *new_node=NULL;

new_node=(struct hash_node *)malloc(sizeof(struct hash_node));
new_node->data=key;
new_node->next=NULL;

pos=hash(key,tbl->size,0);

if(tbl[pos].count==0)
{
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
else
{
   new_node->next=tbl[pos].base;
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
}

void chain_search(struct hash_table *tbl, int key, unsigned int *row,unsigned int *col)
{
int i=0;
int idx=-1;
struct hash_table tb;

idx=hash(key,tbl->size,0);

if(tbl[idx].count > 0)
{
   tb=tbl[idx];
   while(tb.base!=NULL && tb.base->data!=key)
   {
    tb.base=tb.base->next;
    i += 1;
   }
  
   *row=idx;
   *col=i;
  
   if(tb.base==NULL)
   {
    *row=-1;
    *col=-1;
   }
}
else
{
   *row=-1;
   *col=-1;
}
}

#define m 13

int main()
{
int i=0;
int row, col;
struct hash_table tbl[m];

for(i=0;i<m;i++)
{
   tbl[i].base=NULL;
   tbl[i].count=0;
   tbl[i].size=m;
}
chain_insert(tbl,1);
chain_insert(tbl,14);
chain_search(tbl,14,&row,&col);

printf("%d ",tbl[1].base->data);
printf("%d ",tbl[1].base->next->data);
printf("\n%d %d\n",row,col);

return 0;
}

阅读全文
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/68f8d9f87233052e4f4aea5c.html

计划之 4-18 to 4-25

----------------------------------------------------------------------------------------------------------------------------

linux kernel 结束第一遍

练习使用matlab

算法导论 至少读2章

expert 至少看完第五章

对所有认识的人微笑，打招呼

对所有不认识但是眼神碰撞的人微笑

类别：Plans 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/6f65bb15d7ffc914972b438a.html

写了一个快排算法

然后进行了一些修改，随机的选择中轴元素，随机化处理了一下。

对两个算法进行比较，随机产生553k的数据进行排序，分别统计花费的时间。

一开始在windows下，直接 cl 进行编译链接，可执行文件112k，输出分别是 31ms和110ms。

后来偶然使用VC6编译，运行，可执行文件544k，大了432k，输出为94ms和171ms，分别慢了3倍和60+ms。

VS到底做了什么使得效率低了下来？？！！

另外还有一个发现，在数据比较多，随机化处理过的快排算法要比没有处理的快排效率要差很大。印象中好像是应该反过来，期望运行时间应该要优于后者，因为快排的最好的情况下才是O(n*lgn)，而随机化处理过之后期望运行时间是O(n*lgn)。

或者是因为多了随机化操作、数据交换操作和过程调用时间消耗而引起的？

---------------------------------------------------------code--------------------------------------------------------------------

#include<iostream>
#include<cassert>
#include<ctime>
#include<cstdlib>
using namespace std;

void quickSort(int arr[],int p,int r);
int Partition(int arr[],int p,int r);

void random_QuickSort(int arr[],int p,int r);
int random_Partition(int arr[],int p,int r);

inline void swap(int &a,int &b);
void writeFile(string file_name);
void readFile(string file_name,int arr[],int size);
void writeToFile(string file_name,int arr[],int size);

int main()
{
/*int i=-1;
int size=-1;
int *arr=NULL;

cin>>size;
arr=new int[size];

for(i=0;i<size;i++)
{
   cin>>arr[i];
}
quickSort(arr,0,size-1);
for(i=0;i<size;i++)
   cout<<arr[i]<<" ";

delete []arr;*/
const int size=100000;
int arr[size];
int arr2[size];

string in_file="dataIn.txt";
string out_file="dataOut.txt";
string out2_file="dataOut2.txt";

writeFile(in_file);
readFile(in_file,arr,size);
readFile(in_file,arr2,size);

clock_t start=clock();
quickSort(arr,0,size-1);
clock_t end=clock();
double diff=(double)(end-start);
cout<<diff<<endl;

clock_t start2=clock();
// insert_sort_rec(arr2,size-1);
random_QuickSort(arr2,0,size-1);
clock_t end2=clock();
double diff2=(double)(end2-start2);
cout<<diff2<<endl;

writeToFile(out_file,arr,size);
writeToFile(out2_file,arr2,size);
return 0;
}

void quickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=Partition(arr,p,r);

   quickSort(arr,p,q-1);
   quickSort(arr,q+1,r);
}
}

void random_QuickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=random_Partition(arr,p,r);
   random_QuickSort(arr,p,q-1);
   random_QuickSort(arr,q+1,r);
}
}

int Partition(int arr[],int p,int r)
{
int key=arr[r];
int i=p-1;
int j=p;

for(j=p;j<r;j++)
{
   if(arr[j]<=key)
   {
    i++;
    swap(arr[i],arr[j]);
   }
}

swap(arr[i+1],arr[r]);

return i+1;
}
int random_Partition(int arr[],int p,int r)
{
srand(time(NULL));
int rd=rand()%(r-p+1)+p;

swap(arr[rd],arr[r]);

return Partition(arr,p,r);
}

inline void swap(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}

void writeFile(string file_name)
{
int i=0;
FILE *fp;

fp=fopen(file_name.c_str(),"w");

if(!fp)
{
   cerr<<"failed to open file"<<endl;
   exit(-1);
}

srand(time(0));

while((i++)<100000)
{
   fprintf(fp,"%d ",rand()%100);
}

fclose(fp);
}

void readFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"r");

assert(fp!=NULL);

for(int i=0;i<size;i++)
   fscanf(fp,"%d",&arr[i]);

fclose(fp);
}

void writeToFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"w");
assert(fp!=NULL);

for(int i=0;i<size;i++)
   fprintf(fp,"%d ",arr[i]);

fclose(fp);

}

void insert_sort_rec(int array[],int size)
{
if(size>3)
   insert_sort_rec(array,size-1);

int i=size-1;
int key;

key=array[i];
i--;

while(i>=0 && array[i]>key)
{
   array[i+1]=array[i--];
}

array[i+1]=key;
}

阅读全文
类别：算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/4b0a2035d3e577d1a3cc2b39.html