演算法的性能分析
① 急求排序演算法性能分析程序
排序演算法全集【附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、健壯性
健壯性是指一個演算法對不合理數據輸大巧擾入的反應能力和處理能力，也稱為容錯性。