算法的性能分析
① 急求排序算法性能分析程序
排序算法全集【附C++代码】
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N＊N)（因为没有使用word，所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。
现在，让我们开始吧：
一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include ＜iostream.h＞
void BubbleSort(int＊ pData，int Count)
{
int iTemp;
for(int i＝1;i＜Count;i++)
{
for(int j＝Count-1;j＞＝i;j--)
{
if(pData[j]＜pData[j-1])
{
iTemp ＝ pData[j-1];
pData[j-1] ＝ pData[j];
pData[j] ＝ iTemp;
}
}
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
BubbleSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞10，9，7，8-＞10，7，9，8-＞7，10，9，8(交换3次)
第二轮：7，10，9，8-＞7，10，8，9-＞7，8，10，9(交换2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9-＞8，10，7，9-＞8，7，10，9-＞7，8，10，9(交换2次)
第二轮：7，8，10，9-＞7，8，10，9-＞7，8，10，9(交换0次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2＊(n-1)＊n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n＞＝n0时，有f(n)＜＝K＊g(n)，则f(n) ＝ O(g(n))。（呵呵，不要说没
学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2＊(n-1)＊n，当K＝1/2，n0＝1，g(n)＝n＊n时，1/2＊(n-1)＊n＜＝1/2＊n＊n＝K＊g(n)。所以f(n)
＝O(g(n))＝O(n＊n)。所以我们程序循环的复杂度为O(n＊n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），
复杂度为O(n＊n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因，我们通常都是通过循环次数来对比算法。
2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include ＜iostream.h＞
void ExchangeSort(int＊ pData，int Count)
{
int iTemp;
for(int i＝0;i＜Count-1;i++)
{
for(int j＝i+1;j＜Count;j++)
{
if(pData[j]＜pData)
{
iTemp ＝ pData;
pData ＝ pData[j];
pData[j] ＝ iTemp;
}
}
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
ExchangeSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞9，10，8，7-＞8，10，9，7-＞7，10，9，8(交换3次)
第二轮：7，10，9，8-＞7，9，10，8-＞7，8，10，9(交换2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9-＞8，10，7，9-＞7，10，8，9-＞7，10，8，9(交换1次)
第二轮：7，10，8，9-＞7，8，10，9-＞7，8，10，9(交换1次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2＊(n-1)＊n，所以算法的复杂度仍然是O(n＊n)。由于我们无法给出所有的情况，所以
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。
3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中
选择最小的与第二个交换，这样往复下去。
#include ＜iostream.h＞
void SelectSort(int＊ pData，int Count)
{
int iTemp;
int iPos;
for(int i＝0;i＜Count-1;i++)
{
iTemp ＝ pData;
iPos ＝ i;
for(int j＝i+1;j＜Count;j++)
{
if(pData[j]＜iTemp)
{
iTemp ＝ pData[j];
iPos ＝ j;
}
}
pData[iPos] ＝ pData;
pData ＝ iTemp;
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
SelectSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞(iTemp＝9)10，9，8，7-＞(iTemp＝8)10，9，8，7-＞(iTemp＝7)7，9，8，10(交换1次)
第二轮：7，9，8，10-＞7，9，8，10(iTemp＝8)-＞(iTemp＝8)7，8，9，10(交换1次)
第一轮：7，8，9，10-＞(iTemp＝9)7，8，9，10(交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8，10，7，9-＞(iTemp＝8)8，10，7，9-＞(iTemp＝7)8，10，7，9-＞(iTemp＝7)7，10，8，9(交换1次)
第二轮：7，10，8，9-＞(iTemp＝8)7，10，8，9-＞(iTemp＝8)7，8，10，9(交换1次)
第一轮：7，8，10，9-＞(iTemp＝9)7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2＊(n-1)＊n。所以算法复杂度为O(n＊n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)＜＝n
所以我们有f(n)＝O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。
4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include ＜iostream.h＞
void InsertSort(int＊ pData，int Count)
{
int iTemp;
int iPos;
for(int i＝1;i＜Count;i++)
{
iTemp ＝ pData;
iPos ＝ i-1;
while((iPos＞＝0) && (iTemp＜pData[iPos]))
{
pData[iPos+1] ＝ pData[iPos];
iPos--;
}
pData[iPos+1] ＝ iTemp;
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
InsertSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
倒序(最糟情况)
第一轮：10，9，8，7-＞9，10，8，7(交换1次)(循环1次)
第二轮：9，10，8，7-＞8，9，10，7(交换1次)(循环2次)
第一轮：8，9，10，7-＞7，8，9，10(交换1次)(循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8，10，7，9-＞8，10，7，9(交换0次)(循环1次)
第二轮：8，10，7，9-＞7，8，10，9(交换1次)(循环2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)(循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)＜＝
1/2＊n＊(n-1)＜＝1/2＊n＊n。所以其复杂度仍为O(n＊n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘＝’操作。正常的一次交换我们需要三次‘＝’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。
二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：
#include ＜iostream.h＞
void run(int＊ pData，int left，int right)
{
int i，j;
int middle，iTemp;
i ＝ left;
j ＝ right;
middle ＝ pData[(left+right)/2]; //求中间值
do{
while((pData＜middle) && (i＜right))//从左扫描大于中值的数
i++;
while((pData[j]＞middle) && (j＞left))//从右扫描大于中值的数
j--;
if(i＜＝j)//找到了一对值
{
//交换
iTemp ＝ pData;
pData ＝ pData[j];
pData[j] ＝ iTemp;
i++;
j--;
}
}while(i＜＝j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left＜j)，递归左半边
if(left＜j)
run(pData，left，j);
//当右边部分有值(right＞i)，递归右半边
if(right＞i)
run(pData，i，right);
}
void QuickSort(int＊ pData，int Count)
{
run(pData，0，Count-1);
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
QuickSort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k＝log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2＊(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n＊(n/n) ＝ n+n+n+...+n＝k＊n＝log2(n)＊n
所以算法复杂度为O(log2(n)＊n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全
不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)＊n)算法，但是通常情况下速度要慢
于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include ＜iostream.h＞
void Bubble2Sort(int＊ pData，int Count)
{
int iTemp;
int left ＝ 1;
int right ＝Count -1;
int t;
do
{
//正向的部分
for(int i＝right;i＞＝left;i--)
{
if(pData＜pData[i-1])
{
iTemp ＝ pData;
pData ＝ pData[i-1];
pData[i-1] ＝ iTemp;
t ＝ i;
}
}
left ＝ t+1;
//反向的部分
for(i＝left;i＜right+1;i++)
{
if(pData＜pData[i-1])
{
iTemp ＝ pData;
pData ＝ pData[i-1];
pData[i-1] ＝ iTemp;
t ＝ i;
}
}
right ＝ t-1;
}while(left＜＝right);
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4};
Bubble2Sort(data，7);
for (int i＝0;i＜7;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include ＜iostream.h＞
void ShellSort(int＊ pData，int Count)
{
int step[4];
step[0] ＝ 9;
step[1] ＝ 5;
step[2] ＝ 3;
step[3] ＝ 1;
int iTemp;
int k，s，w;
for(int i＝0;i＜4;i++)
{
k ＝ step;
s ＝ -k;
for(int j＝k;j＜Count;j++)
{
iTemp ＝ pData[j];
w ＝ j-k;//求上step个元素的下标
if(s ＝＝0)
{
s ＝ -k;
s++;
pData[s] ＝ iTemp;
}
while((iTemp＜pData[w]) && (w＞＝0) && (w＜＝Count))
{
pData[w+k] ＝ pData[w];
w ＝ w-k;
}
pData[w+k] ＝ iTemp;
}
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4，3，2，1，-10，-1};
ShellSort(data，12);
for (int i＝0;i＜12;i++)
cout＜＜data＜＜” ”;
cout＜＜”＼n”;
}
呵呵，程序看起来有些头疼。不过也不是很难，把s＝＝0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。
四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char＊ strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char＊ GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator ＝(CMyData &SrcData);
bool operator ＜(CMyData& data );
bool operator ＞(CMyData& data );
private:
char＊ m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember !＝ NULL)
delete[] m_strDatamember;
m_strDatamember ＝ NULL;
}
CMyData::CMyData(int Index，char＊ strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize ＝ strlen(strData);
m_strDatamember ＝ new char[m_iDataSize+1];
strcpy(m_strDatamember，strData);
}
CMyData& CMyData::operator ＝(CMyData &SrcData)
{
m_iIndex ＝ SrcData.m_iIndex;
m_iDataSize ＝ SrcData.GetDataSize();
m_strDatamember ＝ new char[m_iDataSize+1];
strcpy(m_strDatamember，SrcData.GetData());
return ＊this;
}
bool CMyData::operator ＜(CMyData& data )
{
return m_iIndex＜data.m_iIndex;
}
bool CMyData::operator ＞(CMyData& data )
{
return m_iIndex＞data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include ＜iostream.h＞
#include ”MyData.h”
template ＜class T＞
void run(T＊ pData，int left，int right)
{
int i，j;
T middle，iTemp;
i ＝ left;
j ＝ right;
//下面的比较都调用我们重载的操作符函数
middle ＝ pData[(left+right)/2]; //求中间值
do{
while((pData＜middle) && (i＜right))//从左扫描大于中值的数
i++;
while((pData[j]＞middle) && (j＞left))//从右扫描大于中值的数
j--;
if(i＜＝j)//找到了一对值
{
//交换
iTemp ＝ pData;
pData ＝ pData[j];
pData[j] ＝ iTemp;
i++;
j--;
}
}while(i＜＝j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left＜j)，递归左半边
if(left＜j)
run(pData，left，j);
//当右边部分有值(right＞i)，递归右半边
if(right＞i)
run(pData，i，right);
}
template ＜class T＞
void QuickSort(T＊ pData，int Count)
{
run(pData，0，Count-1);
}
void main()
{
CMyData data[] ＝ {
CMyData(8，”xulion”)，
CMyData(7，”sanzoo”)，
CMyData(6，”wangjun”)，
CMyData(5，”VCKBASE”)，
CMyData(4，”jacky2000”)，
CMyData(3，”cwally”)，
CMyData(2，”VCUSER”)，
CMyData(1，”isdong”)
};
QuickSort(data，8);
for (int i＝0;i＜8;i++)
cout＜＜data.m_iIndex＜＜” ”＜＜data.GetData()＜＜”＼n”;
cout＜＜”＼n”;
② 怎么测试一个算法的性能，用什么软件
这个要从两个维度去考证：
一、测算指标，算法都是有数学理论基础的，在翻译成计算机程序后，算法的执行效率可以用赋值、比较、运算等操作次数，以及缓存、内存占用率等指标进行一定的估算，还应对算法效率进行计算，进行比较评估，包括迭代深度、循环/判断嵌套深度等指标。
二、实际测试，这个就是要把算法真的用计算机实现出来，将算法逻辑封装为函数、控件、组件等，可调用的独立环节（尽量减少非算法语句的干扰），然后进行实际调用，记录执行周期，分析实际性能。比如对比记录新旧算法单次执行的周期、固定数量多次执行的周期、执行期间资源占用率、多线程并发调用的执行效率等指标。
另外、对于实际测试，如果想用专业测试软件执行，可以用LoadRunner、Robot等专业软件测试工具执行相应操作，但是对于您的要求，我还是建议收集性能指标的程序最好自己写，其实并不复杂，就是调用您的算法组件，把执行时间等参数记下来。
③ 应该从哪些方面分析和评价算法的性能
评价算法的四个标准：
1.正确性
能正确地实现预定的功能，满足具体问题的需要。处理数据使用的算法是否得当，能不能得到预想的结果。
2.易读性
易于阅读、理解和交流，便于调试、修改和扩充。写出的算法，能不能让别人看明白，能不能让别人明白算法的逻辑？如果通俗易懂，在系统调试和修改或者功能扩充的时候，使系统维护更为便捷。
3.健壮性
输入非法数据，算法也能适当地做出反应后进行处理，不会产嫌或生预料不到的运行结果。数据的形式多种多样，算法可能面临着接受各种各样的数据，当算法接收到不适合算法处理的数据，算法本身该如何处理呢？如果算法能够处理异常数据，处理能力越强，健壮性越好。
4.时空性
算法的时空性是该算法的时间性能和空间性能。主要是说算法在执行过程中的时间长短和空间占用多少问题。
算法处理数据过程中，不同的算法耗费的时间和内存空间是不同的。
(3)算法的性能分析扩展阅读：
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。芹者伍此外，一个算法还具有下列5个重要的特性。
（1）、有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
（2）、确定性嫌圆
算法中每一条指令必须有明确的含义，读者理解时不会产生二义性。即对于相同的输入只能得到相同的输出。
（3）、可行性
一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
（4）、输入
一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
（5）、输出
一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。
④ 如何衡量一个时间算法的时间效率
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。
时间效率，一定生产时间内，机器实际运转时间与理论运转时间之比，通常用百分率表示。与设备自动化程度、速度、卷装尺寸、工人操作熟练程度及看台数有关。
(4)算法的性能分析扩展阅读：
点在空间中变化对点的描述称为被描述点相当于该点的时间【该点运动到某一位置时，被描述点都会有唯一的对应位置，称为此时被描述点的位置】。被描述点可以随时间变化位置不变，可知时间与被描述点的位置有函数关系。
空间使事物具有了变化性，即因为空间的存在，所以事物才可以发生变化。空间是没有能量的事物，即当事物能产生变化时，变化产生的能量已经和阻碍的能量相互抵消。
天文测时所依赖的是地球自转，而地球自转的不均匀性使得天文方法所得到的时间（世界时）精度只能达到10-9，无法满足二十世纪中叶社会经济各方面的需求。一种更为精确和稳定的时间标准应运而生，这就是“原子钟”。
世界各国都采用原子钟来产生和保持标准时间，这就是“时间基准”，然后，通过各种手段和媒介将时间信号送达用户，这些手段包括：短波、长波、电话网、互联网、卫星等。这一整个工序，就称为“授时系统”。
⑤ 如何度量算法的性能
算法是否高效决定你后面开发的效率和繁琐度。一般最好用博弈论测试下，核心算法不行的话最好推倒重建比较好些。
⑥ 重要的算法做出性能分析是什么意思
是说分析算法的时间复杂度和空间复杂度？
⑦ 用c语言完成：1.哈夫曼编码/译码器2.内部排序算法的性能分析
我把网上的程序修改了一下，并整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;
typedef struct
{
int weight;//结点权值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//动态分配数组存储哈夫曼编码表
typedef struct
{
int key; /*关键字*/
}RecordNode; /*排序节点的类型*/
typedef struct
{
RecordNode *record;
int n; /*排序对象的大小*/
}SortObject; //待排序序列
HUFFMANTREE huffmantree(int n,int weight[])//构建哈夫曼树
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼树中各结点的数据，没初始值的赋值为0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循环从森林中选择最小的两棵树组建成一颗新树
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;++i)//逐个字符求哈夫曼编码
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*从叶子结点到根结点求逆向编码*/
if(ht[father].lchild==child)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=(char*)malloc((n-start)*sizeof(char));//为i个字符编码分配空间
strcpy(hc[i],&cd[start]);//从cd复制哈夫曼编码串到hc
}
free(cd);//释放工作空间
for(i=1;i<=n;++i)
{
printf("\n%c的编码:",str[i]);
printf("%s\n",hc[i]);
}
}
void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);
printf("\n请输入字符(一次性连续输入所求的字符):");/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n请输入%c的权值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}
void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}
void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}
void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}
void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("请输入待排序的随机数个数：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比较如下");
for(j=0;j<5;j++)
{
printf("\n\n对%d个数进行排序，结果为：\n",k);
printf("1.插入排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.选择排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希尔排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回车继续\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n对%d个随机数进行5次排序，平均比较次数和平均移动次数为：\n",k);
printf("1.插入排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.选择排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希尔排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}
void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
main()
{
int i,j,k;
while(1)
{
printf("请选择要运行的功能：\n");
printf("1.哈夫曼编码译码器\n");
printf("2.内部排序性能分析\n");
printf("3.退出该程序\n\n");
printf("你的选择为：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}
⑧ 用java的知识解答内部排序算法的性能分析
第一蚂升隐题：
import java.math.* ;
import java.util.* ;
class TieZi{
private String name ;
private int num ;
public TieZi(String name,int num){
this.setName(name) ;
this.setNum(num) ;
}
public void setName(String name){
this.name = name ;
}
public String getName(){
return this.name ;
}
public void setNum(int num){
this.num = num ;
}
public int getNum(){
return this.num ;
}
}
public class TestOne{
private TieZi[] tz ;
public TestOne(int max){
this.tz = new TieZi[max] ;
for (int i = 0; i<max; i++){
this.tz[i] = new TieZi("跟贴_" + (i+1),this.getRandomNum()) ;
System.out.println (tz[i].getNum()) ;
}
this.getTop10(this.tz) ;
}
public int getRandomNum(){//产笑烂生100个0-99的随机数
return ((int)(Math.random()*100)) ;
}
public void getTop10(TieZi[] tz){//进行冒泡排序并且输出
TieZi temp2 = null ;
int num[] = new int[10] ;
for (int j = 0; j<tz.length; j++){
for (int i = 0; i<tz.length; i++){
if(tz[j].getNum() > tz[i].getNum()){
temp2 = tz[j] ;
tz[j] = tz[i] ;
tz[i] = temp2 ;
}
}
}
for (int i = 0; i<10; i++){
System.out.println ("贴子名: " + tz[i].getName() + "\t跟贴数: " + tz[i].getNum()) ;
}
}
public static void main(String[] args){
new TestOne(100) ;
}
}
第二题：闷厅
import java.math.* ;
import java.util.* ;
class User{
private String name ;
private double mark ;
public User(String name,double mark){
this.setName(name) ;
this.setMark(mark) ;
}
public void setName(String name){
this.name = name ;
}
public String getName(){
return this.name ;
}
public void setMark(double mark){
this.mark = mark ;
}
public double getMark(){
return this.mark ;
}
}
public class TestTwo{
private User[] tz ;
public TestTwo(int max){
this.tz = new User[max] ;
for (int i = 0; i<max; i++){
this.tz[i] = new User("用户名_" + (i+1),this.getRandomNum()) ;
System.out.println (tz[i].getMark()) ;
}
this.getTop10(this.tz) ;
}
public int getRandomNum(){//产生100个0-499的随机数
return ((int)(Math.random()*500)) ;
}
public void getTop10(User[] tz){//进行冒泡排序并且输出
User temp2 = null ;
int num[] = new int[3] ;
double jiangLi = 1.2 ;
for (int j = 0; j<tz.length; j++){
for (int i = 0; i<tz.length; i++){
if(tz[j].getMark() > tz[i].getMark()){
temp2 = tz[j] ;
tz[j] = tz[i] ;
tz[i] = temp2 ;
}
}
}
for (int i = 0; i<3; i++){
if(i == 1)
jiangLi = 1.15 ;
if(i == 2)
jiangLi = 1.1 ;
System.out.println ("用户名: " + tz[i].getName() + "\t分数: " + tz[i].getMark()*jiangLi) ;
}
}
public static void main(String[] args){
new TestTwo(100) ;
}
楼主看看吧。用的都是基础知识。选我啊
⑨ 内部排序算法的性能分析难吗
难。根据查询相关公开信息显示，内部排序的方法很多，就其全面性衡滚能而言，很难提出一种被认为是最好的仿侍方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。排序算法主要是内部排序，内部排序包括插入排序，交咐大余换排序，选择排序，归并排序，基数排序等。
⑩ 评价一个算法性能好坏的重要标准是
1、时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做宽咐。
3、正确性
算法的正滚旦确性是评价一个算法优劣的最重要的标准。
4、可读性
算法的可读性是指一个算法可供人们阅读的容易程度。
5、健壮性
健壮性是指一个算法对不合理数据输大巧扰入的反应能力和处理能力，也称为容错性。