博文
[原]自己总结的排序算法(2007-12-20 10:13:00)
摘要：1,快速排序
这个有点难解释,感觉上就是纽来纽去,先从首记录开始也行,从未记录开始也行,以后补上.
Tony Hoare在1962年首次提出了快速排序算法。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时，其它排序算法才可能胜过快速排序算法。快速排序算法是利用分治技术的典型例子，随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步：
（1）将问题分成若干大小基本相等的子问题；
（2）独立地解决这些子问题；
（3）将子问题归并成原问题的解。
快速排序的基本思路是：首先我们选择一个中间值middle（程序中我们可使用数组中间值），把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架（从各类数据结构教材中可得）：
void QuickSort(int *pData, int left, int right)
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中间值
do
{
while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
i++;
while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
j--;
if (i <= j) //找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次）
......
转算法复杂度的分析方法及其运用(2007-12-19 16:17:00)
摘要：算法复杂度是在《数据结构》这门课程的第一章里出现的，因为它稍微涉及到一些数学问题，所以很多同学感觉很难，加上这个概念也不是那么具体，更让许多同学复习起来无从下手，下面我们就这个问题给各位考生进行分析。
首先了解一下几个概念。一个是时 间复杂度，一个是渐近时 间复杂度。前者是某个算法的时 间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时 间复杂度的数量级。
当我们评价一个算法的时 间性能时，主要标准就是算法的渐近时 间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时 间复杂度T(n)=O(f(n))简称为时 间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时 间复杂度。以保证算法的运行时 间不会比它更长。
常见的时 间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3 n^2 1000 , g(n)=25n^3 5000n^2 , h(n)=n^1.5 5000nlgn
请判断下列关系是否成立：
（1） f(n)=O(g(n))
（2） g(n)=O(f(n))
（3） h(n)=O(n^1.5)
（4） h(n)=O(nlgn)
这里我们复习一下渐近时 间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。
◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
◆ （2）成立。与上同理。......
转用Visual C++实现排序算法大全(2007-12-19 15:58:00)
摘要： 1.引言
2005年10月25～26日，包括笔者在内的十多位成员组队参加了武汉原动力的野外拓展（Outward Bound）。在攀岩悬崖之前，教官组织了这样的一个游戏项目：
教官将团队里的所有成员分开，然后用布条蒙上大家的眼睛，接着给每人一个3位或4位的数字。他要求成员们蒙着眼睛集合，在不说话也看不到彼此的情况下，在限定的时间内，按所分得数字的大小顺序排成一条线。
要成功地完成这个游戏的确有相当的难度，成员们唯一可以借助的分辨彼此大小的手段可能是摸手指、拍肩膀或跺脚等，而要在限定的时间内分别出所有的大小并排成一条线却依赖一个好的排序算法。 最后我们团队失败了，我们这群都有一定数据结构和算法学习背景的所谓IT人败在了这个游戏的面前。最后，教官对我们进行了一番“团队合作精神如此重要”之类的教育云云。
本文对排序算法的全面论述将从这个游戏说开去，并用Visual C++ 6.0编写一个示例工程以动画演示这个游戏中的成员以各种算法实现成功排序的过程。排序算法是数据结构学科的经典内容，也是计算机科学中最重要的研究问题之一。由于它的应用广泛和固有的理论上的重要性，2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。在演示完各种排序算法的动态过程后，本文将给出面对特定问题时选用合适排序算法的原则。
2.演示工程
单击此处下载演示工程。
以Visual C++编写一个基于对话框的程序，我们假设待排序的队员的总数为10，排序的整个过程为（每个步骤对应一个菜单）：
（1）队员分散：模拟教官将队员分散开来的过程
对应的菜单为：IDM_Disperse_Member
菜单标题为：队员分散 （2）分配数字：模拟教官给每个队员一个3位或4位的数字的过程
对应的菜单为：IDM_CREAT_NUMBER
菜单标题为：产生数字
......
转快速排序算法(2007-12-19 15:35:00)
摘要：
快速排序算法
佚名
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 &nbs......
转排序总结(2007-12-19 14:52:00)
摘要：
一、排序的概念
所谓排序，就是要让所有元素按递增或递减的顺序排列。
二、排序的分类
内部排序：只在主存中完成的排序(由于主存有限，所以内部排序的元素是有上限的)。
外部排序：利用磁盘等外存进行排序。
三、排序的稳定性
在待排序的元素中，存在多个相同的元素，经过排序后，这些元素的相对位置不变，该排序法就为稳定排序，否则为不稳定排序。
四、内部排序法
-----------------------------------------------------------
1.插入排序
算法思想
假设待排序的元素存放在数组A[N]中。初始时，A[0]自成1个有序区，无序区为A[1]~A[N-1]。从i=1起直至i=N-1为止，依次将A[i]插入当前的有序区A[0]~A[i-1]中。排序结束后为含N个元素的有序区。算法的平均时间复杂度为O(N^2)。
程序实现
void
InsertionSort( ElementType A[], int N )
{
int j, P;
ElementTyep Tmp;
for( P = 1; P < N; P++ );
{
Tmp = A[ P ];
for( j = p; j > 0 && A[ j - 1 ] > Tmp; j-- )
A[ j ] = A[ j - 1 ];
A[ j ] = Tmp;
}
}--------------------------------------------------------
2.希尔排序
算法思想
假设有N个待排序的元素，先取一个小于N的整数d1作为第一个增量，把所有距离为d......
转MFC通用类的使用(2007-12-19 12:11:00)
摘要：一、数组类：
CByteArray、CDWordArray、CPtrArray、CUIntArray、CWordArray、CstringArray
成员函数有：
Add() 在数组的最后追加一个元素，可以根据需要增大数组大小
ElementAt() 获得一个指向数组元素的指针
FreeExtra() 释放不用的数组内存
GetAt() 获取数组内指定位置处的值
GetSize() 获取数组中包含的元素个数
GetUpperBound() 获取数组的上界值
InserAt() 在数组的指定位置处插入一个元素，后面的元素的下标加1
RemoveAll() 删除数组中所有的元素
SetAt() 设定数组指定位置处的值。因为制革函数不会增加数组的大小，故这个下标此时一定有效
SetAtGrow() 设定数组的指定位置处的值，可以根据需要增大数组大小
SetSize() 设置数组的初始大小
首先，在View类中声明一个数组对象，如下：
CUIntArray array;
在View类的构造函数中初始化数组，将其设置成包含十个元素：
array.SetSize(10,5); SetSize()函数有两个参数，第一个参数是数组的初始大小，第二个参数是数组元素每次增加的个数。
现在就可以在应用程序中用了！
二、列表类的使用：
Clist() Clist类的构造函数，其中的参数指定分配内存的基本单元
GetHead() 获得列表的第一个元素的值
GetTail() 获得列表的最后一个元素的值
RemoveHead() 删除列表中第一个元素
RemoveTail() 风险列表中最后一个元素
AddHead() 在列表的头部添加一个节点，使这个节点成为列表的新的头
AddTail() 在列表的尾部添加一个节点，使这个节点成为列表的新的尾
RemoveAll() 删除节点中所有的元素
GetHeadPosition() 获得列表的头节点的位置
GetTailPosition() 获得列表中尾节点的位置
GetNext() 获得指定位置下一个节点外的值
GetPrev() 获得指定位置上一个节点外的值......
原CStdioFile总结(2007-12-19 11:53:00)
摘要：CStdioFile继承自CFile.
参数内容:
第一个参数为路径+文件名,最后一个为错误出现的结构.
现在解释下第二个参数
CFile::modeCreate Directs the constructor to create a new file. If the file exists already, it is truncated to 0 length.
指定构造器创建一个新的文件,如果文件已经存在,则内容截0.
CFile::modeNoTruncate Combine this value with modeCreate. If the file being created already exists, it is not truncated to 0 length. Thus the file is guaranteed to open, either as a newly created file or as an existing file. This might be useful, for example, when opening a settings file that may or may not exist already. This option applies to CStdioFile as well.
modeNoTruncate
假如你不用这个参数的话，用modeCreate模式创建和打开一个文件，假如这个文件已经存在，则会清空这个已经存在的文件，加上modeNoTruncate的话，就不会清空这个文件了
CFile::modeRead Opens the file for reading only.
只是以读取方式打开CFile::modeReadWrite Opens the file for reading and writing.
读与写同时
CFile::modeWrite Opens the file for writing only.
只写
CFile::modeNoInherit&n......
个人对回调函数的理解(2007-12-14 11:21:00)
摘要：例如,我正在调用windows系统的函数,但出于某种原因,windows中被调用的函数依赖调用者提供一个函数处理,恩,这样说相当混乱,那么举个例子:(csdn 引用jemmylau（枕头）)
用户A写一段程序，处理某一事务，例如数据排序。他对排序算法有相当研究，因此，他使用了一种高效的排序算法。为了让不懂排序算法的人也能够使用这个高效的算法，他决定为其他用户提供一个函数接口。但是，既然要排序，就必须比较2个对象的大小，而算法编写者对客户的对象没有任何知识，因此，他需要客户提供一个比较对象大小的函数，如，
int comp(const void* obj1, const void* obj2)
当他需要比较大小时，就调用客户提供的这个函数，根据函数返回值确定大小关系。而客户提供的这个比较函数，就可以称作回调(callback)函数,即：本来是我(客户)调用你（算法库），而你会过头来又调用我的函数（比较函数），回调函数由此得名。
回调函数的概念随处可见，其应用并不局限于系统调用。一般来讲，如果某个处理流程具有确定性，而流程中某个具体的处理环节需要根据实际情况具体处理，就可以将这个流程固定下来，在需要具体处理的地方“安插”适当的回调函数接口。
再如,简单版,你是单独处理排序的,我是处理比较大小的,我现在需要对某些数据排序,所以我调用你的函数,但是你只处理排序,你排序过程中又依赖我的比较大小算法,所以你又得调用我的函数,这,就称为回调(我的函数).
......
转潜在抑郁症- [知识](2007-12-14 11:03:00)
摘要：
有些人天生就对环境刺激特别敏感，并比普通人容易在更短的时间内接收并处理更多更综合的信息。如果这种能力出现在低智商的人身上，那么这个人就可能得精神病；但如果这种能力出现在高智商的人身上，那么这个人就会是天才，并有着极高的创造力。
潜在抑制症是一种心理疾病。通常人会把对自己没有直接作用的事物封闭在思考范围之外，而潜在抑制症患者会深度分解思考。比如，当患者看到一条路的时候，会迅速深度想到该条路通向什么方向，或者铺路时的情景。 由于潜在抑制症会引发患者的一系列幻想，想象内容的纵深程度非常之大，低于平均智商或年纪偏小的患者因为无法承受这种想象程度，而引发精神分裂，但平均智商以上或成年人患者则可以控制想象内容的纵深程度，而会成为一个极富创造性的人，几近于天才。 潜在抑制症患者由于想象内容的庞大，以及不断的扩张，而关心所有细小的事情，从邻居的生活，到世界政局的变化；从药品的化学结构，到建筑的结构。这会让体质差一些的患者引发精神衰弱等疾病。
一种非常复杂的精神疾病和心理疾病（低水平意识潜忘能力） 多伦多和哈佛大学的心理学家确认创新能力的生物学基础之一。研究表明善于创造的人大脑更能接受外部环境的刺激。另外一些人的的大脑就屏蔽了同样的信息刺激―这一过程被称为“latent（潜在，潜意识的） inhibition（压抑）―被定义为与动物无意识下的一种能力，为了忽略与自己当前需求无关的刺激。通过心理学测试，似有迹象表明我们的艺术家很可能具有一种低水平的潜意识压抑(仅仅针对外部环境刺激，可能就是所谓的：低危抑郁症).
“富有创造力的个体长期处在环境信息流的刺激中，普通人来说将事务归类以后，就很快忘记它，尽管事务本身可能是复杂而且有趣的。但是富有创造力的人则相反，他们将它放到新的可能性中。”科学家把精神联系到缺少筛选出的刺激。新的研究表明这种缺失（failure）也同样有益于内源的思考，尤其是当与高智商联系在一起的时候......创造能力与精神疾病
严格说来Low Latent Inhibition算是抑郁症的一种，但不是主要的、平时大多人都知道三大抑郁症之中的。科学、医学学术上的不断研究和规范才有了这个特殊的分类，得这种抑郁症比中......
WINDOWS程序设计翻译不顺的地方(2007-12-04 14:16:00)
摘要：有时候，DefWindowProc处理完消息后会产生其它的消息。例如，假设使用者执行HELLOWIN，并且使用者最终单击了 Close按钮，或者假设用键盘或鼠标从系统菜单中选择了 Close， DefWindowProc处理这一键盘或者鼠标输入，在检测到使用者选择了Close选项之后，它给窗口消息处理程序发送一条WM_SYSCOMMAND消息。WndProc将这个消息传给DefWindowProc。DefWindowProc给窗口消息处理程序发送一条WM_CLOSE消息来响应之。WndProc再次将它传给DefWindowProc。DestroyWindow呼叫DestroyWindow来响应这条WM_CLOSE消息。DestroyWindow导致Windows给窗口消息处理程序发送一条WM_DESTROY消息。WndProc再呼叫PostQuitMessage，将一条WM_QUIT消息放入消息队列中，以此来响应此消息。这个消息导致WinMain中的消息循环终止，然后程序结束。
::Sometimes messages generate other messages as a result of DefWindowProc processing. For example, suppose you run HELLOWIN and you eventually click the Close button, or suppose you select Close from the system menu using either the keyboard or the mouse. DefWindowProc processes this keyboard or mouse input. When it detects that you have selected the Close option, it sends a WM_SYSCOMMAND message to the window procedure. WndProc passes this message to DefWindowProc. DefWindowProc responds by sending a WM_CLOSE message to the window procedure. WndP......