完形匹配算法
‘壹’ 字符串匹配的传统算法
传统的匹配算法
串匹配算法虽然发展了几十年，然而非常实用的算法是近年才出现。串匹配问题的研究存在理论研究和实际应用的脱节。那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。而开发人员只追求实际应用中尽可能快的算法。两者之间从不注意对方在干什么。将理论研究和实际应用结合的算法(如BNDM算法)只是近年才出现。在实际应用中常常很难找到适合需求的算法——这样的算法实际上是存在的，但是只有资深专家才比较了解。考虑如下情况，一位软件开发人员，或者一位计算生物学家，或者一位研究人员，又或者一位学生，对字符串匹配领域并没有深入了解，可是现在需要处理一个文本搜索问题。那些汗牛充栋的书籍使得阅读者淹没在各种匹配算法的海洋中，却没有足够的知识选择最适用的算法。最后，常常导致这样的局面：选择一种最简单的算法加以实现。这往往导致很差的性能，从而影响整个开发系统的质量。更糟糕的是，选择了一个理论上看起来很漂亮的算法，并且花费了大量精力去实现。结果，却发现实际效果和一个简单算法差不多，甚至还不如简单算法。因此，应该选用一种“实用”算法，即在实际应用中性能较好，并且一个普通程序员能在几小时内完成算法的实现代码。另外，在字符串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。
传统的串匹配算法可以概括为前缀搜索、后缀搜索、子串搜索。代表算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技术包括滑动窗口、位并行、自动机、后缀树等。
‘贰’ 图像匹配的算法
迄今为止，人们已经提出了各种各样的图像匹配算法，但从总体上讲，这些匹配算法可以分成关系结构匹配方法、结合特定理论工具的匹配方法、基于灰度信息的匹配方法、基于亚像元匹配方法、基于内容特征的匹配方法五大类型 基于内容特征的匹配首先提取反映图像重要信息的特征，而后以这些特征为模型进行匹配。局部特征有点、边缘、线条和小的区域，全局特征包括多边形和称为结构的复杂的图像内容描述。特征提取的结果是一个含有特征的表和对图像的描述，每一个特征由一组属性表示，对属性的进一步描述包括边缘的定向和弧度，边与线的长度和曲率，区域的大小等。除了局部特征的属性外，还用这些局部特征之间的关系描述全局特征，这些关系可以是几何关系，例如两个相邻的三角形之间的边，或两个边之间的距离可以是辐射度量关系，例如灰度值差别，或两个相邻区域之间的灰度值方差或拓扑关系，例如一个特征受限于另一个特征。人们一般提到的基于特征的匹配绝大多数都是指基于点、线和边缘的局部特征匹配，而具有全局特征的匹配实质上是我们上面提到的关系结构匹配方法。特征是图像内容最抽象的描述，与基于灰度的匹配方法比，特相对于几何图像和辐射影响来说更不易变化，但特征提取方法的计算代价通常较，并且需要一些自由参数和事先按照经验选取的闭值，因而不便于实时应用同时，在纹理较少的图像区域提取的特征的密度通常比较稀少，使局部特征的提 取比较困难。另外，基于特征的匹配方法的相似性度量也比较复杂，往往要以特征属性、启发式方法及闭方法的结合来确定度量方法。基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于图像的特征点比象素点要少很多，因而可以大大减少匹配过程的计算量同时，特征点的匹配度量值对位置的变化比较敏感，可以大大提高匹配的精确程度而且，特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的适应能力。所以基于图像特征的匹配在实际中的应用越来越广-泛。所使用的特征基元有点特征明显点、角点、边缘点等、边缘线段等。
‘叁’ 串模式匹配算法（C语言）100分悬赏
第一个朴素算法:
1.普通的串模式匹配算法:
int index(char s[],char t[],int pos)
/*查找并返回模式串T在S中从POS开始的位置下标,若T不是S的子串.则返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分别指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //计算主串和模式串的长度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}
第二个KMP算法.该算法支持从主串的任意位置开始搜索.
2.KMP算法:
//求模式串的next函数.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}
//KMP模式匹配算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函数,求P在主串S中从第POS个字符开始的位置*/
/*若匹配成功.则返回模式串在主串中的位置下标.否则返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];
‘肆’ 字符串匹配算法是怎么算的
这是一个毕业老师出的字符串的算法的题目！这是答案 可以参考一下！ boyermoore算法的sample程序 TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind) { // // 声明： // 该段代码只是BoyerMoore(名字也许不准确) 的基本思想，当 // 然不是最优的，具体完善工作就留给你自己乐！嘻嘻。 // 该算法的本质就是从字符串的右端而不是左端开始比较，这 // 样，当查询不匹配时才有可能直接跃过多个字符（最多可以跃过 // strlen(sFind)个字符）， 如果最右边的字符匹配则回溯。比如： // // pain // ^ 这是第一次比较n和空格比 // The rain in SpainThe rain in Spain // // pain // ^ 这是第二次比较，好爽呀！ // The rain in SpainThe rain in Spain // // 当然，这样比较会产生一些问题，比如： // // pain // ^ （图1） // The rain in SpainThe rain in Spain // // 如果比较到这儿，大家都会看到，只需再向后移到两个字符 // 就匹配成功了，但如果接下去还按上面的方法跳strlen( sFind)的 // 话，就会错过一次匹配！！！！！ // // pain // ^ // The rain in SpainThe rain in Spain // // 怎么办？当然可以解决！大家回头看图1，当时a是pain的子 // 串，说明有可能在不移动strlen(sFind) 的跨度就匹配成功，那就 // 人为地给它匹配成功的机会嘛！串一下pain串， 直接让两个a对齐 // 再做比较！呵呵，如果要比较的字符不是pain的子串，当然就可 // 以直接跨过strlen(sFind)个字符了！ 不知我说明白没？ // // // 查询串的长度 int nLenOfFind = lstrlen(sFind); // 被查询串的长度 int nLenOfSrc = lstrlen(sSrc); // 指向查询串最后一个字符的指针 TCHAR * pEndOfFind = sFind + nLenOfFind -1; // 指向被查询串最后一个字符的指针 TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比较过程中要用到的两个指针 TCHAR * pSrc = sSrc; TCHAR * pFind; // 总不能一直让它比较到 win.com 文件的地址去吧？嘻嘻！ while ( pSrc <= pEndOfSrc ) { // 每次匹配都是从右向左，这是本算法的核心。 pFind = pEndOfFind; // 如果比较不成功，被查询串指针将向右串的字符数 int nMoveRightSrc; // 比较被查询串的当前字符是否和查询串的最右边字 // 符匹配，如果匹配则回溯比较，如果全匹配了，该 // 干什么，我就不用说了吧？:-) while ( pFind >= sFind ) { // TNND，白废功夫比了！看看需要向右移动几个 // 字符吧（如果说从右到左是本算法的核心，则 // 判断向右移几个字符则是本算法的技巧）。 if ( *pSrc != *pFind ) { // 被查询串的当前字符是否在查询串里？ TCHAR * p = strrchr( sFind, *pSrc ); // 没在，直接移lstrlen(sFind)个字符 if ( NULL == p ) nMoveRightSrc = nLenOfFind; else // 哇塞！真的在，那就只需... nMoveRightSrc = pEndOfFind - p; break; } // 哈！又匹配成功了一个！接着向左回溯... pFind --; pSrc --; } // 如果在上面的while循环里每一次比较都匹配了 // 那就对了呗！告诉用户找到了 if ( pFind < sFind ) return ( pSrc + 1 ); // 没匹配成功，nMoveRightSrc上面已经算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序运行到这儿肯定是没指望了！ return NULL; } 行了，函数写完了，我们可以试一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("没找到"); } //另外一个 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }
‘伍’ C语言求二部图完备匹配
二部图是一种十分重要的数据结构。在对二部图及匹配的概念进行了阐述后,给出了求二部图所有极大匹配的算法,该算法也可用于求二部图的所有最大匹配和完全匹配。用C语言程序验证了此算法的有效性。
机构:
德州学院计算机系 山东德州253023;
领域:
计算机软件及计算机应用；
关键词:
二部图； 匹配； 极大匹配； 最大匹配； 完全匹配； 算法；
‘陆’ KMP模式匹配算法是什么
KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。
1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。
图1改进算法的模式匹配过程示意
‘柒’ 字符串匹配算法的基本思想是什么
这个用到了正规表达式对字符串的匹配.程序如下,是javascript的.
<script language="javascript">
function check(obj)
{var str=/^[0-9]{4}-[0-9]{7}$/ig;
if(str.test(obj))
alert("this is your number");
else
alert("write again");}
</script>
<form name="form1">
<input type="text" name="mytext" size="12">
<input type="button" value="click" onclick="check
(form1.mytext.value)">
</form>
要求输入的是标准电话号码.看不懂问我.呵呵.
‘捌’ 数据结构串匹配十大经典算法
1。
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。
int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函数值求T在主串S中第pos 个字符之后的位置的KMP算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函数：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next
我现在只有这两个答案。
‘玖’ 离散数学的图论中的二部图的完全匹配和最大匹配问题怎么理解
11个互不同构的生成子图，18个互不同构的子图
ps:生成子图按边数考虑，边数从0到6，子图按顶点数考虑
‘拾’ 有关匹配和排序的算法，高手帮帮忙哈
一、插入排序(Insertion Sort)
1. 基本思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2. 排序过程：
【示例】：
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
Procere InsertSort(Var R : FileType);
//对R[1..N]按递增序进行插入排序, R[0]是监视哨//
Begin
for I := 2 To N Do //依次插入R[2],...,R[n]//
begin
R[0] := R[I]; J := I - 1;
While R[0] < R[J] Do //查找R[I]的插入位置//
begin
R[J+1] := R[J]; //将大于R[I]的元素后移//
J := J - 1
end
R[J + 1] := R[0] ; //插入R[I] //
end
End; //InsertSort //
二、选择排序
1. 基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2. 排序过程：
【示例】：
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 〔38 65 97 76 49 27 49]
第二趟排序后 13 27 〔65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97
Procere SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 //
Begin
for I := 1 To N - 1 Do //做N - 1趟选择排序//
begin
K := I;
For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]//
begin
If R[J] < R[K] Then K := J
end;
If K <>; I Then //交换R[I]和R[K] //
begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;
end
End; //SelectSort //
三、冒泡排序(BubbleSort)
1. 基本思想：
两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。
2. 排序过程：
设想被排序的数组R〔1..N〕垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
Procere BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//
Begin
For I := 1 To N-1 Do //做N-1趟排序//
begin
NoSwap := True; //置未排序的标志//
For J := N - 1 DownTo 1 Do //从底部往上扫描//
begin
If R[J+1]< R[J] Then //交换元素//
begin
Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
NoSwap := False
end;
end;
If NoSwap Then Return//本趟排序中未发生交换，则终止算法//
end
End; //BubbleSort//
四、快速排序（Quick Sort）
1. 基本思想：
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
2. 排序过程：
【示例】：
初始关键字 [49 38 65 97 76 13 27 49〕
第一次交换后 〔27 38 65 97 76 13 49 49〕
第二次交换后 〔27 38 49 97 76 13 65 49〕
J向左扫描，位置不变，第三次交换后 〔27 38 13 97 76 49 65 49〕
I向右扫描，位置不变，第四次交换后 〔27 38 13 49 76 97 65 49〕
J向左扫描 〔27 38 13 49 76 97 65 49〕
（一次划分过程）
初始关键字 〔49 38 65 97 76 13 27 49〕
一趟排序之后 〔27 38 13〕 49 〔76 97 65 49〕
二趟排序之后 〔13〕 27 〔38〕 49 〔49 65〕76 〔97〕
三趟排序之后 13 27 38 49 49 〔65〕76 97
最后的排序结果 13 27 38 49 49 65 76 97
各趟排序之后的状态
Procere Parttion(Var R : FileType; L, H : Integer; Var I : Integer);
//对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置 //
Begin
I := 1; J := H; X := R[I] ;//初始化，X为基准//
Repeat
While (R[J] >;= X) And (I < J) Do
begin
J := J - 1 //从右向左扫描，查找第1个小于 X的元素//
If I < J Then //已找到R[J] 〈X//
begin
R[I] := R[J]; //相当于交换R[I]和R[J]//
I := I + 1
end;
While (R[I] <= X) And (I < J) Do
I := I + 1 //从左向右扫描，查找第1个大于 X的元素///
end;
If I < J Then //已找到R[I] >; X //
begin R[J] := R[I]; //相当于交换R[I]和R[J]//
J := J - 1
end
Until I = J;
R[I] := X //基准X已被最终定位//
End; //Parttion //
Procere QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//
Begin
If S < T Then //当R[S..T]为空或只有一个元素是无需排序//
begin
Partion(R, S, T, I); //对R[S..T]做划分//
QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]//
QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] //
end;
End; //QuickSort//
五、堆排序(Heap Sort)
1. 基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3. 排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆
Procere Sift(Var R :FileType; I, M : Integer);
//在数组R[I..M]中调用R[I]，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆//
Begin
X := R[I]; J := 2*I; //若J <=M, R[J]是R[I]的左孩子//
While J <= M Do //若当前被调整结点R[I]有左孩子R[J]//
begin
If (J < M) And R[J].Key < R[J+1].Key Then
J := J + 1 //令J指向关键字较大的右孩子//
//J指向R[I]的左、右孩子中关键字较大者//
If X.Key < R[J].Key Then //孩子结点关键字较大//
begin
R[I] := R[J]; //将R[J]换到双亲位置上//
I := J ; J := 2*I //继续以R[J]为当前被调整结点往下层调整//
end;
Else
Exit//调整完毕，退出循环//
end
R[I] := X;//将最初被调整的结点放入正确位置//
End;//Sift//
Procere HeapSort(Var R : FileType); //对R[1..N]进行堆排序//
Begin
For I := N Div Downto 1 Do //建立初始堆//
Sift(R, I , N)
For I := N Downto 2 do //进行N-1趟排序//
begin
T := R[1]; R[1] := R[I]; R[I] := T;//将当前堆顶记录和堆中最后一个记录交换//
Sift(R, 1, I-1) //将R[1..I-1]重成堆//
end
End; //HeapSort//
六、几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。