㈠ 內部排序演算法的性能分析
fgh
㈡ 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。
排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。
1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；
學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。
排序（sort）或分類
所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。
2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。
排序的穩定性
當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。
排序方法的分類
1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。
2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。
排序演算法分析
1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。
2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）
（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；
（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。
3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度
（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。
（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。
文件的順序存儲結構表示
#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。
按平均時間將排序分為四類：
（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；
（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；
（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；
（4）線性階(O(n))排序
如桶、箱和基數排序。
各種排序方法比較
簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。
影響排序效果的因素
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。
不同條件下，排序方法的選擇
(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。
4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。
㈢ 內部排序演算法的性能分析
起泡排序O(N^2)
直接排序O(N^2)
簡單選擇排序O(N^2)
快速排序O(Nlog2N)
堆排序O(Nlog2N)
㈣ 內部排序演算法的性能分析
沒時間幫你寫程序需說個思路就閃人了 你先把3種排序的書上的例子抄下來 寫成3個函數， 每個函數裡面開頭和結尾取一次系統時間 最後相減得出開銷時間 在列印出來
㈤ 幾種常見的排序演算法的實現與性能分析(數據結構)的報告
可參考 ：
http://blog.csdn.net/stubbornpotatoes/article/details/7513509
http://hi..com/shismbwb/item/404c94898cfd2855850fab24
㈥ 急求排序演算法性能分析程序
排序演算法全集【附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」;
㈦ 求助期末數據結構課設，
什麼時候截止？
我有《內排序演算法分析》的C++代碼和分析報告，分析九個內排序演算法的，當時大一寫的。你要的話，我去取。最好寬限幾天，這幾天比較忙。呵呵，其實吧，這東西還是在參考別人的基礎上自己寫好 ^_^
如果著急的話，我給你個C++的停車場的程序。這個問題簡單一點，代碼比較少，雖然可以實現全部功能，但代碼量可能達不到要求。。。
給個郵箱，我把工程文件全發給你，如果你需要的話。
㈧ 用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) ;
}
樓主看看吧。用的都是基礎知識。選我啊
㈨ 用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");
}
}
㈩ 1． 排序演算法性能分析（95分） 編程實現希爾、快速、堆排序、歸並排序演算法，並計算每種排序演算法的比較、交
貌似有點難