算法的代码

1. KMP算法详细代码

private int KMP(String inText, String inMode)
{
if (inText.Length < inMode.Length)
{
return -1;
}

int[] arrNext = new int[inMode.Length + 1];
this.Next(inMode, arrNext);
int i, j; // i是主串游标 j是模式串游标
for (i = j = 0; i < inText.Length && j < inMode.Length; )
{
if (j == -1 || // 模式串游标已经回退到第一个位置
inText[i] == inMode[j]) // 当前字符匹配成功
{ // 满足以上两种情况时两个游标都要向前进一步
++i;
++j;
}
else // 匹配不成功,模式串游标回退到当前字符的arrNext值
{
j = arrNext[j];
}
}
if (j >= inMode.Length)
{
return i - inMode.Length;
}
else
{
return -1;
}

}

private void Next(String inMode, int[] arrNext)
{
arrNext[0] = -1;
for (int i = 0, j = -1; i < inMode.Length; )
{ // i是主串游标 j是模式串的游标
if (j == -1 || // 如果模式串游标已经回退到第一个字符
inMode[i] == inMode[j]) // 如果匹配成功
{ // 两个游标都向前走一步
++i;
++j;
arrNext[i] = j; // 存放当前的arrNext值为此时模式串的游标值
}
else // 匹配不成功j就回退到上一个arrNext值
{
j = arrNext[j];
}
}

}

2. 哈夫曼编码的算法代码

//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案 //by jirgal 2005.4.18 #include<iostream.h> #include<iomanip.h> #define NUM 26 //字母数 #define TNUM 51 // #define LTH 15 //编码最大长度 class Node { public: char data; int weight; int parent; int lchild; int rchild; }; void main() { char ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l', 'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26个字母 int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42, 339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率 Node nodes[TNUM]; //用对象数组存储哈夫曼树 int i,j,one,two,a,b; int hc[NUM][LTH]; //用于存储编码 int m,n; //初始化数组 for(i=0;i<NUM;i++) { nodes[i].data=ch[i]; nodes[i].weight=weit[i]; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } for(i=NUM;i<TNUM;i++) { nodes[i].data='@'; nodes[i].weight=-1; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } //建立哈夫曼树 for(i=NUM;i<TNUM;i++) { a=b=-1; one=two=10000; //最大权数 for(j=0;j<i;j++) { if(nodes[j].parent==-1) if(nodes[j].weight<=two) one=two; two=nodes[j].weight; a=b; b=j; } else if(nodes[j].weight>two&&nodes[j].weight<=one) { one=nodes[j].weight; a=j; } } }//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点 nodes[a].parent=i; nodes[b].parent=i; nodes[i].lchild=a; nodes[i].rchild=b; nodes[i].weight=nodes[a].weight+nodes[b].weight; } //初始化hc for(i=0;i<LTH;i++) { for(j=0;j<NUM;j++) { hc[j][i]=7; } } //编码 for(i=0;i<NUM;i++) { j=LTH-1; for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent) { if(nodes[n].lchild==m) { hc[i][j]=0; } else { hc[i][j]=1; } j--; } } //输出 nodes cout<<"HuffmanTree:"<<endl; cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) <<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; for(i=0;i<TNUM;i++) { cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) <<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; } //输出编码 cout<<endl<<"Result:"<<endl; cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; for(i=0;i<NUM;i++) { cout<<setw(6)<<ch[i]<<setw(8)<<weit[i]; cout<<" "; for(j=0;j<LTH;j++) { if(hc[i][j]!=7) { cout<<hc[i][j]; } } cout<<endl; } cout<<"\nDone.\n"<<endl; }

3. C语言实现七种排序算法的演示代码是什么

（1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void
bubble(int
*a,int
n)
/*定义两个参数：数组首地址与数组大小*/
{
int
i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
/*注意循环的上下限*/
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理简单，但其缺点是交换次数多，效率低。
下面介绍一种源自冒泡法但更有效率的方法“选择法”。
（2）“选择法”
选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。
void
choise(int
*a,int
n)
{
int
i,j,k,temp;
for(i=0;i<n-1;i++)
{
k=i;
/*给记号赋值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j])
k=j;
/*是k总是指向最小元素*/
if(i!=k)
{
/*当k!=i是才交换，否则a[i]即为最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。
（3）“快速法”
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j).
它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。下面分析其代码：
void
quick(int
*a,int
i,int
j)
{
int
m,n,temp;
int
k;
m=i;
n=j;
k=a[(i+j)/2];
/*选取的参照*/
do
{
while(a[m]<k&&m<j)
m++;
/*
从左到右找比k大的元素*/
while(a[n]>k&&n>i)
n--;
/*
从右到左找比k小的元素*/
if(m<=n)
{
/*若找到且满足条件，则交换*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j)
quick(a,m,j);
/*运用递归*/
if(n>i)
quick(a,i,n);
}
（4）“插入法”
插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。
void
insert(int
*a,int
n)
{
int
i,j,temp;
for(i=1;i<n;i++)
{
temp=a[i];
/*temp为要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j])
{
/*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
/*插入*/
}
}
（5）“shell法”
shell法是一个叫
shell
的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序。下面让我们来分析其代码：
void
shell(int
*a,int
n)
{
int
i,j,k,x;
k=n/2;
/*间距值*/
while(k>=1)
{
for(i=k;i<n;i++)
{
x=a[i];
j=i-k;
while(j>=0&&x<a[j])
{
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2;
/*缩小间距值*/
}
}
上面我们已经对几种排序法作了介绍，现在让我们写个主函数检验一下。
#include<stdio.h>
/*别偷懒，下面的"..."代表函数体，自己加上去哦！*/
void
bubble(int
*a,int
n)
{
...
}
void
choise(int
*a,int
n)
{
...
}
void
quick(int
*a,int
i,int
j)
{
...
}
void
insert(int
*a,int
n)
{
...
}
void
shell(int
*a,int
n)
{
...
}
/*为了打印方便，我们写一个print吧。*/[code]
void
print(int
*a,int
n)
{
int
i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
}
main()
{
/*为了公平，我们给每个函数定义一个相同数组*/
int
a1[]={13,0,5,8,1,7,21,50,9,2};
int
a2[]={13,0,5,8,1,7,21,50,9,2};
int
a3[]={13,0,5,8,1,7,21,50,9,2};
int
a4[]={13,0,5,8,1,7,21,50,9,2};
int
a5[]={13,0,5,8,1,7,21,50,9,2};
printf("the
original
list:");
print(a1,10);
printf("according
to
bubble:");
bubble(a1,10);
print(a1,10);
printf("according
to
choise:");
choise(a2,10);
print(a2,10);
printf("according
to
quick:");
quick(a3,0,9);
print(a3,10);
printf("according
to
insert:");
insert(a4,10);
print(a4,10);
printf("according
to
shell:");
shell(a5,10);
print(a5,10);
}

4. 加密算法实现代码

这个是界面效果，我不是用C++写的，是用C#写的可以参考下：

实现的代码如下：

usingSystem;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Text;

usingSystem.Windows.Forms;

usingSystem.Collections;

usingSystem.IO;

usingSystem.Security.Cryptography;

usingSystem.Security;

namespaceKey

{

publicpartialclassfrmKey:Form

{

privatestringkey;//默认密钥"yupengcheng"

privatebyte[]sKey;

privatebyte[]sIV;

publicfrmKey()

{

InitializeComponent();

}

privatevoidForm1_Load(objectsender,EventArgse)

{

button4.Enabled=false;

}

///<summary>

///选择输入路径

///</summary>

privatevoidbutton1_Click(objectsender,EventArgse)

{

//openFileDialog1.Filter="所有文件(*.*)|*.*";

openFileDialog1.ShowDialog();

stringfilename=openFileDialog1.FileName;

inti=filename.LastIndexOf(".");

if(i!=-1)

{

stringfiletype=filename.Substring(filename.LastIndexOf("."));

if(this.radioButton1.Checked)

{

filename=filename.Replace("(解密文件)","");

textBox2.Text=filename.Substring(0,filename.LastIndexOf("."))+"(加密文件)"+filetype;

}

else

{

filename=filename.Replace("(加密文件)","");

textBox2.Text=filename.Substring(0,filename.LastIndexOf("."))+"(解密文件)"+filetype;

}

}

if(filename!="")

{

textBox1.Text=openFileDialog1.FileName;

}

}

///<summary>

///选择输出路径

///</summary>

privatevoidbutton4_Click(objectsender,EventArgse)

{

this.saveFileDialog1.ShowDialog();

if(saveFileDialog1.FileName!="")

{

this.textBox2.Text=saveFileDialog1.FileName;

}

}

///<summary>

///加密radioButton

///</summary>

privatevoidradioButton1_CheckedChanged(objectsender,EventArgse)

{

button3.Text="开始加密";

}

///<summary>

///解密radioButton

///</summary>

privatevoidradioButton2_CheckedChanged(objectsender,EventArgse)

{

button3.Text="开始解密";

}

///<summary>

///明密/暗密

///</summary>

privatevoidbutton2_Click(objectsender,EventArgse)

{

if(button2.Text=="明密")

{

textBox3.PasswordChar=Convert.ToChar(0);

button2.Text="暗密";

}

else

{

textBox3.PasswordChar=char.Parse("*");

button2.Text="明密";

}

}

///<summary>

///开始加密/开始解密

///</summary>

privatevoidbutton3_Click(objectsender,EventArgse)

{

if(this.textBox1.Text==""||this.textBox2.Text=="")

{

MessageBox.Show("文件路径不能为空！","警告提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);

return;

}

if(textBox3.Text!="yupengcheng")

{

MessageBox.Show("输入的密码不正确，请重新输入！","错误提示",MessageBoxButtons.OK,MessageBoxIcon.Error);

textBox3.Text="";

return;

}

else

{

key="yupengcheng";

if(button3.Text=="开始加密")

{

statusBar1.Visible=true;

statusBar1.Text="正在加密文件，请等待.....";

if(EncryptFile(this.textBox1.Text,this.textBox2.Text,textBox3.Text))

{

statusBar1.Text="加密完成。";

MessageBox.Show("文件加密成功！","成功提示",MessageBoxButtons.OK,MessageBoxIcon.Information);

}

statusBar1.Visible=false;

}

else

{

statusBar1.Visible=true;

statusBar1.Text="正在解密文件，请等待.....";

if(DecryptFile(this.textBox1.Text,this.textBox2.Text,textBox3.Text))

{

statusBar1.Text="解密完成。";

MessageBox.Show("文件解密成功！","成功提示",MessageBoxButtons.OK,MessageBoxIcon.Information);

}

statusBar1.Visible=false;

}

}

}

///<summary>

///取消

///</summary>

privatevoidbutton5_Click(objectsender,EventArgse)

{

Application.Exit();

}

///<summary>

///加密方法

///</summary>

///<paramname="filePath">加密输入路径</param>

///<paramname="savePath">加密输出路径</param>

///<paramname="keyStr">密匙</param>

///<returns></returns>

publicboolEncryptFile(stringfilePath,stringsavePath,stringkeyStr)

{

DESCryptoServiceProviderdes=newDESCryptoServiceProvider();

if(keyStr=="")

keyStr=key;

try

{

FileStreamfs=File.OpenRead(filePath);

byte[]inputByteArray=newbyte[fs.Length];

fs.Read(inputByteArray,0,(int)fs.Length);

fs.Close();

byte[]keyByteArray=Encoding.Default.GetBytes(keyStr);

SHA1ha=newSHA1Managed();

byte[]hb=ha.ComputeHash(keyByteArray);

sKey=newbyte[8];

sIV=newbyte[8];

for(inti=0;i<8;i++)

sKey[i]=hb[i];

for(inti=8;i<16;i++)

sIV[i-8]=hb[i];

des.Key=sKey;

des.IV=sIV;

MemoryStreamms=newMemoryStream();

CryptoStreamcs=newCryptoStream(ms,des.CreateEncryptor(),CryptoStreamMode.Write);

cs.Write(inputByteArray,0,inputByteArray.Length);

cs.FlushFinalBlock();

fs=File.OpenWrite(savePath);

foreach(bytebinms.ToArray())

{

fs.WriteByte(b);

}

fs.Close();

cs.Close();

ms.Close();

returntrue;

}

catch

{

MessageBox.Show("找不到指定的文件,请重新输入!","警告提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);

returnfalse;

}

}

///<summary>

///解密方法

///</summary>

///<paramname="filePath">解密输入路径</param>

///<paramname="savePath">解密输出路径</param>

///<paramname="keyStr">密匙</param>

///<returns></returns>

publicboolDecryptFile(stringfilePath,stringsavePath,stringkeyStr)

{

DESCryptoServiceProviderdes=newDESCryptoServiceProvider();

if(keyStr=="")

keyStr=key;

try

{

FileStreamfs=File.OpenRead(filePath);

byte[]inputByteArray=newbyte[fs.Length];

fs.Read(inputByteArray,0,(int)fs.Length);

fs.Close();

byte[]keyByteArray=Encoding.Default.GetBytes(keyStr);

SHA1ha=newSHA1Managed();

byte[]hb=ha.ComputeHash(keyByteArray);

sKey=newbyte[8];

sIV=newbyte[8];

for(inti=0;i<8;i++)

sKey[i]=hb[i];

for(inti=8;i<16;i++)

sIV[i-8]=hb[i];

des.Key=sKey;

des.IV=sIV;

MemoryStreamms=newMemoryStream();

CryptoStreamcs=newCryptoStream(ms,des.CreateDecryptor(),CryptoStreamMode.Write);

cs.Write(inputByteArray,0,inputByteArray.Length);

cs.FlushFinalBlock();

fs=File.OpenWrite(savePath);

foreach(bytebinms.ToArray())

{

fs.WriteByte(b);

}

fs.Close();

cs.Close();

ms.Close();

returntrue;

}

catch

{

MessageBox.Show("找不到指定的文件,请重新输入!","警告提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);

returnfalse;

}

}

privatevoidtextBox1_TextChanged(objectsender,EventArgse)

{

if(textBox1.Text==""||textBox1.Text==null)

{

button4.Enabled=false;

}

else

{

button4.Enabled=true;

}

}

}

}

5. 求一个A*算法的C语言或C++代码，小弟不胜感激，谢谢

1#include <iostream>
2#include <queue>
3usingnamespace std;
4
5struct knight{
6int x,y,step;
7int g,h,f;
8booloperator< (const knight & k) const{ //重载比较运算符
9return f > k.f;
10 }
11}k;
12bool visited[8][8]; //已访问标记(关闭列表)
13int x1,y1,x2,y2,ans; //起点(x1,y1),终点(x2,y2),最少移动次数ans
14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8个移动方向
15priority_queue<knight> que; //最小优先级队列(开启列表)
16
17boolin(const knight & a){ //判断knight是否在棋盘内
18if(a.x<0|| a.y<0|| a.x>=8|| a.y>=8)
19returnfalse;
20returntrue;
21}
22int Heuristic(const knight &a){ //manhattan估价函数
23return (abs(a.x-x2)+abs(a.y-y2))*10;
24}
25void Astar(){ //A*算法
26 knight t,s;
27while(!que.empty()){
28 t=que.top(),que.pop(),visited[t.x][t.y]=true;
29if(t.x==x2 && t.y==y2){
30 ans=t.step;
31break;
32 }
33for(int i=0;i<8;i++){
34 s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
35if(in(s) &&!visited[s.x][s.y]){
36 s.g = t.g +23; //23表示根号5乘以10再取其ceil
37 s.h = Heuristic(s);
38 s.f = s.g + s.h;
39 s.step = t.step +1;
40 que.push(s);
41 }
42 }
43 }
44}
45int main(){
46char line[5];
47while(gets(line)){
48 x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
49 memset(visited,false,sizeof(visited));
50 k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
51while(!que.empty()) que.pop();
52 que.push(k);
53 Astar();
54 printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
55 }
56return0;
57}
58

6. 快速排序算法的示例代码

usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespacetest{classQuickSort{staticvoidMain(string[]args){int[]array={49,38,65,97,76,13,27};sort(array,0,array.Length-1);Console.ReadLine();}/**一次排序单元，完成此方法，key左边都比key小，key右边都比key大。**@paramarray排序数组**@paramlow排序起始位置**@paramhigh排序结束位置**@return单元排序后的数组*/privatestaticintsortUnit(int[]array,intlow,inthigh){intkey=array[low];while(low<high){/*从后向前搜索比key小的值*/while(array[high]>=key&&high>low)--high;/*比key小的放左边*/array[low]=array[high];/*从前向后搜索比key大的值，比key大的放右边*/while(array[low]<=key&&high>low)++low;/*比key大的放右边*/array[high]=array[low];}/*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high*/array[low]=key;foreach(intiinarray){Console.Write({0} ,i);}Console.WriteLine();returnhigh;}/**快速排序*@paramarry*@return*/publicstaticvoidsort(int[]array,intlow,inthigh){if(low>=high)return;/*完成一次单元排序*/intindex=sortUnit(array,low,high);/*对左边单元进行排序*/sort(array,low,index-1);/*对右边单元进行排序*/sort(array,index+1,high);}}}运行结果：27 38 13 49 76 97 65
13 27 38 49 76 97 6513 27 38 49 65 76 97
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。图示 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。 QUICKSORT(A，p，r)
1if p<r
2then q ←PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
为排序一个完整的数组A，最初的调用是QUICKSORT(A，1，length[A]）。
快速排序算法的关键是PARTITION过程，它对子数组A[p..r]进行就地重排：
PARTITION(A，p，r)
1x←A[r]
2i←p-1
3for j←p to r-1
4do if A[j]≤x
5then i←i+1
6exchange A[i]←→A[j]
7exchange A[i+1]←→A[r]
8return i+1 对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中，我们在真正进行划分之前实现交换：
（其中PARTITION过程同快速排序伪代码（非随机））
RANDOMIZED-PARTITION(A，p，r)
1i← RANDOM(p，r)
2exchange A[r]←→A[i]
3return PARTITION(A，p，r)
新的快速排序过程不再调用PARTITION，而是调用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1if p<r
2then q← RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r) 这里为方便起见，我们假设算法Quick_Sort的范围阈值为1（即一直将线性表分解到只剩一个元素），这对该算法复杂性的分析没有本质的影响。
我们先分析函数partition的性能，该函数对于确定的输入复杂性是确定的。观察该函数，我们发现，对于有n个元素的确定输入L[p..r]，该函数运行时间显然为θ（n）。
最坏情况
无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情况都是相同的。
我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候（设输入的表有n个元素）。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。
对于有n个元素的表L[p..r]，由于函数Partition的计算时间为θ（n），所以快速排序在序坏情况下的复杂性有递归式如下：
T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)
用迭代法可以解出上式的解为T(n)=θ（n2）。
这个最坏情况运行时间与插入排序是一样的。
下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。
设T(n）是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间，则
T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1 (2)
我们假设对于任何k<n，总有T(k）≤ck，其中c为常数；显然当k=1时是成立的。
将归纳假设代入（2），得到：
T(n）≤max(cq2+c(n-q)2)+θ（n)=c*max(q2+(n-q)2)+θ（n)
因为在[1,n-1]上q2+(n-q)2关于q递减，所以当q=1时q2+(n-q)2有最大值n2-2(n-1）。于是有：
T(n）≤cn2-2c(n-1)+θ（n）≤cn2
只要c足够大，上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n）≤cn。
这样，排序算法的最坏情况运行时间为θ（n2），且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。
时间复杂度为o（n2）。
最好情况
如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。这时有：
T(n)=2T(n/2)+θ（n),T(1)=θ（1) (3)
解得：T(n)=θ（nlogn)
快速排序法最佳情况下执行过程的递归树如下图所示，图中lgn表示以10为底的对数，而本文中用logn表示以2为底的对数.
由于快速排序法也是基于比较的排序法，其运行时间为Ω（nlogn)，所以如果每次划分过程产生的区间大小都为n/2，则运行时间θ（nlogn）就是最好情况运行时间。
但是，是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍一看该划分很不对称。我们可以得到递归式：
T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1) (4)
请注意树的每一层都有代价n，直到在深度log10n=θ（logn）处达到边界条件，以后各层代价至多为n。递归于深度log10/9n=θ（logn）处结束。这样，快速排序的总时间代价为T(n)=θ（nlogn），从渐进意义上看就和划分是在中间进行的一样。事实上，即使是99:1的划分时间代价也为θ（nlogn）。其原因在于，任何一种按常数比例进行划分所产生的递归树的深度都为θ（nlogn），其中每一层的代价为O(n），因而不管常数比例是什么，总的运行时间都为θ（nlogn），只不过其中隐含的常数因子有所不同。（关于算法复杂性的渐进阶，请参阅算法的复杂性)
平均情况
快速排序的平均运行时间为θ(nlogn)。
我们对平均情况下的性能作直觉上的分析。
要想对快速排序的平均情况有个较为清楚的概念，我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。
当我们对一个随机的输入数组应用快速排序时，要想在每一层上都有同样的划分是不太可能的。我们所能期望的是某些划分较对称，另一些则很不对称。事实上，我们可以证明，如果选择L[p..r]的第一个元素作为支点元素，Partition所产生的划分80%以上都比9:1更对称，而另20%则比9:1差，这里证明从略。
平均情况下，Partition产生的划分中既有“好的”，又有“差的”。这时，与Partition执行过程对应的递归树中，好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致，假设好、差划分交替出现在树的各层上，且好的划分是最佳情况划分，而差的划分是最坏情况下的划分。在根节点处，划分的代价为n，划分出来的两个子表的大小为n-1和1，即最坏情况。在根的下一层，大小为n-1的子表按最佳情况划分成大小各为（n-1)/2的两个子表。这儿我们假设含1个元素的子表的边界条件代价为1。
在一个差的划分后接一个好的划分后，产生出三个子表，大小各为1，（n-1)/2和（n-1)/2，代价共为2n-1=θ（n）。一层划分就产生出大小为（n-1)/2+1和（n-1)/2的两个子表，代价为n=θ（n）。这种划分差不多是完全对称的，比9:1的划分要好。从直觉上看，差的划分的代价θ（n）可被吸收到好的划分的代价θ（n）中去，结果是一个好的划分。这样，当好、差划分交替分布划分都是好的一样：仍是θ（nlogn），但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出。
在前文从直觉上探讨快速排序的平均性态过程中，我们已假定输入数据的所有排列都是等可能的。如果输入的分布满足这个假设时，快速排序是对足够大的输入的理想选择。但在实际应用中，这个假设就不会总是成立。
解决的方法是，利用随机化策略，能够克服分布的等可能性假设所带来的问题。
一种随机化策略是：与对输入的分布作“假设”不同的是对输入的分布作“规定”。具体地说，在排序输入的线性表前，对其元素加以随机排列，以强制的方法使每种排列满足等可能性。事实上，我们可以找到一个能在O(n）时间内对含n个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间，但它却使得运行时间能够独立于输入数据已排序的情况。
另一种随机化策略是：利用前文介绍的选择支点元素pivot的第四种方法，即随机地在L[p..r]中选择一个元素作为支点元素pivot。实际应用中通常采用这种方法。
快速排序的随机化版本有一个和其他随机化算法一样的有趣性质：没有一个特别的输入会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意给出一个坏的输入也没用，因为随机化排列会使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时，随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态，只有非常少的几个排列才会导致算法的近最坏情况性态。
一般来说，当一个算法可按多条路子做下去，但又很难决定哪一条保证是好的选择时，随机化策略是很有用的。如果大部分选择都是好的，则随机地选一个就行了。通常，一个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价，那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到，对快速排序来说，一组好坏相杂的划分仍能产生很好的运行时间 。因此我们可以认为该算法的随机化版本也能具有较好的性态。

7. Floyd算法的参考代码

function Floyd(w,router_direction,MAX)
%w为此图的距离矩阵
%router_direction为路由类型：0为前向路由；非0为回溯路由
%MAX是数据输入时的∞的实际值
len=length(w);
flag=zeros(1,len);
%根据路由类型初始化路由表
R=zeros(len,len);
for i=1:len
if router_direction==0%前向路由
R(:,i)=ones(len,1)*i;
else %回溯路由
R(i,:)=ones(len,1)*i;
end
R(i,i)=0;
end
disp('');
disp('w(0)');
dispit(w,0);
disp('R(0)');
dispit(R,1);
%处理端点有权的问题
for i=1:len
tmp=w(i,i)/2;
if tmp~=0
w(i,:)=w(i,:)+tmp;
w(:,i)=w(:,i)+tmp;
flag(i)=1;
w(i,i)=0;
end
end
%Floyd算法具体实现过程
for i=1:len
for j=1:len
if j==i || w(j,i)==MAX
continue;
end
for k=1:len
if k==i || w(j,i)==MAX
continue;
end
if w(j,i)+w(i,k)<w(j,k) %Floyd算法核心代码
w(j,k)=w(j,i)+w(i,k);
if router_direction==0%前向路由
R(j,k)=R(j,i);
else %回溯路由
R(j,k)=R(i,k);
end
end
end
end
%显示每次的计算结果
disp(['w(',num2str(i),')'])
dispit(w,0);
disp(['R(',num2str(i),')'])
dispit(R,1);
end
%中心和中点的确定
[Center,index]=min(max(w'));
disp(['中心是V',num2str(index)]);
[Middle,index]=min(sum(w'));
disp(['中点是V',num2str(index)]);
end
function dispit(x,flag)
%x：需要显示的矩阵
%flag：为0时表示显示w矩阵，非0时表示显示R矩阵
len=length(x);
s=[];
for j=1:len
if flag==0
s=[s sprintf('%5.2f ',x(j,:))];
else
s=[s sprintf('%d ',x(j,:))];
end
s=[s sprintf(' ')];
end
disp(s);
disp('---------------------------------------------------');
end
% 选择后按Ctrl+t取消注释号%
%
% 示例：
% a=[
% 0,100,100,1.2,9.2,100,0.5;
% 100,0,100,5,100,3.1,2;
% 100,100,0,100,100,4,1.5;
% 1.2,5,100,0,6.7,100,100;
% 9.2,100,100,6.7,0,15.6,100;
% 100,3.1,4,100,15.6,0,100;
% 0.5,2,1.5,100,100,100,0
% ];
%
% b=[
% 0,9.2,1.1,3.5,100,100;
% 1.3,0,4.7,100,7.2,100;
% 2.5,100,0,100,1.8,100;
% 100,100,5.3,0,2.4,7.5;
% 100,6.4,2.2,8.9,0,5.1;
% 7.7,100,2.7,100,2.1,0
% ];
%
% Floyd(a,1,100)
% Floyd(b,1,100) program floyd;
var
st,en,f:integer;
k,n,i,j,x:integer;
a:array[1..10,1..10] of integer;
path:array[1..10,1..10] of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(k);
if k<>0 then
a[i,j]:=k
else
a[i,j]:=maxint;
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
f:=st;
while f<> en do
begin
write(f);
write('-->');
f:=path[f,en];
end;
writeln(en);
end. //以无向图G为入口，得出任意两点之间的路径长度length[i][j]，路径path[i][j][k]，//途中无连接得点距离用0表示，点自身也用0表示publicclassFLOYD{int[][]length=null;//任意两点之间路径长度int[][][]path=null;//任意两点之间的路径publicFLOYD(int[][]G){intMAX=100;introw=G.length;//图G的行数int[][]spot=newint[row][row];//定义任意两点之间经过的点int[]onePath=newint[row];//记录一条路径length=newint[row][row];path=newint[row][row][];for(inti=0;i<row;i++)//处理图两点之间的路径for(intj=0;j<row;j++){if(G[i][j]==0)G[i][j]=MAX;//没有路径的两个点之间的路径为默认最大if(i==j)G[i][j]=0;//本身的路径长度为0}for(inti=0;i<row;i++)//初始化为任意两点之间没有路径for(intj=0;j<row;j++)spot[i][j]=-1;for(inti=0;i<row;i++)//假设任意两点之间的没有路径onePath[i]=-1;for(intv=0;v<row;++v)for(intw=0;w<row;++w)length[v][w]=G[v][w];for(intu=0;u<row;++u)for(intv=0;v<row;++v)for(intw=0;w<row;++w)if(length[v][w]>length[v][u]+length[u][w]){length[v][w]=length[v][u]+length[u][w];//如果存在更短路径则取更短路径spot[v][w]=u;//把经过的点加入}for(inti=0;i<row;i++){//求出所有的路径int[]point=newint[1];for(intj=0;j<row;j++){point[0]=0;onePath[point[0]++]=i;outputPath(spot,i,j,onePath,point);path[i][j]=newint[point[0]];for(ints=0;s<point[0];s++)path[i][j][s]=onePath[s];}}}voidoutputPath(int[][]spot,inti,intj,int[]onePath,int[]point){//输出i//到j//的路径的实际代码，point[]记录一条路径的长度if(i==j)return;if(spot[i][j]==-1)onePath[point[0]++]=j;//System.out.print(+j+);else{outputPath(spot,i,spot[i][j],onePath,point);outputPath(spot,spot[i][j],j,onePath,point);}}publicstaticvoidmain(String[]args){intdata[][]={{0,27,44,17,11,27,42,0,0,0,20,25,21,21,18,27,0},//x1{27,0,31,27,49,0,0,0,0,0,0,0,52,21,41,0,0},//1{44,31,0,19,0,27,32,0,0,0,47,0,0,0,32,0,0},//2{17,27,19,0,14,0,0,0,0,0,30,0,0,0,31,0,0},//3{11,49,0,14,0,13,20,0,0,28,15,0,0,0,15,25,30},//4{27,0,27,0,13,0,9,21,0,26,26,0,0,0,28,29,0},//5{42,0,32,0,20,9,0,13,0,32,0,0,0,0,0,33,0},//6{0,0,0,0,0,21,13,0,19,0,0,0,0,0,0,0,0},//7{0,0,0,0,0,0,0,19,0,11,20,0,0,0,0,33,21},//8{0,0,0,0,28,26,32,0,11,0,10,20,0,0,29,14,13},//9{20,0,47,30,15,26,0,0,20,10,0,18,0,0,14,9,20},//10{25,0,0,0,0,0,0,0,0,20,18,0,23,0,0,14,0},//11{21,52,0,0,0,0,0,0,0,0,0,23,0,27,22,0,0},//12{21,21,0,0,0,0,0,0,0,0,0,0,27,0,0,0,0},//13{18,41,32,31,15,28,0,0,0,29,14,0,22,0,0,11,0},//14{27,0,0,0,25,29,33,0,33,14,9,14,0,0,11,0,9},//15{0,0,0,0,30,0,0,0,21,13,20,0,0,0,0,9,0}//16};for(inti=0;i<data.length;i++)for(intj=i;j<data.length;j++)if(data[i][j]!=data[j][i])return;FLOYDtest=newFLOYD(data);for(inti=0;i<data.length;i++)for(intj=i;j<data[i].length;j++){System.out.println();System.out.print(From+i+to+j+pathis:);for(intk=0;k<test.path[i][j].length;k++)System.out.print(test.path[i][j][k]+);System.out.println();System.out.println(From+i+to+j+length:+test.length[i][j]);}}}