Hi Java!

MD5即Message-Digest Algorithm 5（信息-摘要算法  5），由于输入信息A是不定长的，长度没有限制，对A进行MD5运算之后，生成的摘要B[B=MD5(A)]长度却是固定的，为128-bits 。无论是对一个空字符串还是bt下载的十几个G的文件，生成摘要的长度都是一样的。这就决定了信息A和摘要B是一种“多对一的关系”。

山东大学王小云教授成功破解MD5 , 王小云教授的研究成功在于实现了在可计算时间内实现找到C，使得MD5(C)=MD5(A)=B，但C未必等于A。这种信息和摘要的多对一关系，本身就决定了不可能从MD5 HASH中恢复出明文。

当然也并不是说这种破解研究毫无意义，看一下这篇文章就知道了：关于MD5破解这件事

另外推荐一个不错的加密解密的站点：http://www.md5.com.cn/

算法题目：

有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（其中 O[i]<R[i]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。
比方说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。

解答：

只需要按照R值和O值之差（即释放空间的大小）从大到小排序，依次处理请求就可以了。

转自：http://www.matrix67.com/blog/archives/1714

1、 堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
注意：
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直 接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比 较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行 了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<stdio.h>
 
int main()
{
	char str[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
	char data[100];
	printf("Input a number:\n");
	int n,m,i=0;
	scanf("%d",&n);
 
	while(n!=0)
	{
		m=n & 0xf;
		data[i]=str[m];
		n=n >> 4;
		i++;
	}
	data[i]='\0';
 
	for(--i;i>=0;i--)
	{
		printf("%c",data[i]);
	}
	printf("\n");
	return 0;
}

其中不得不提的是，m=n & 0xf（除16取余）n=n >> 4（除16取商，右移4位），这样能够提高程序的执行效率，面试经常被问到的问题。

关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 void selection_sort(int list[], int n)
 {
   int i, j, min;
 
   for (i = 0; i < n - 1; i++)
   {
     min = i;
     for (j = i+1; j < n; j++)
     {
        if (list[j] < list[min])
        {
           min = j;
        }
     }
     swap(&list[i], &list[min]);
   }
 }

关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 void quicksort(int list[],int m,int n)
 {
	int key,i,j,k;
	if( m < n)
	{
	   k = choose_pivot(m,n);
	   swap(&list[m],&list[k]);
	   key = list[m];
	   i = m+1;
	   j = n;
	   while(i <= j)
	   {
		  while((i <= n) && (list[i] <= key))
				 i++;
		  while((j >= m) && (list[j] > key))
				 j--;
		  if( i < j)
				 swap(&list[i],&list[j]);
	   }
 
	   swap(&list[m],&list[j]);
	   quicksort(list,m,j-1);
	   quicksort(list,j+1,n);
	}
 }

原文：http://cprogramminglanguage.net/quicksort-algorithm-c-source-code.aspx