內部排序演算法的性能分析

❶ 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。

排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。

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)。

❷ 我想具體了解一下中國傳媒大學數字媒體藝術專業網路多媒體方向和數字媒體理論與實踐方向的區別

同學你查錯了吧？

工程碩士
計算機技術專業分成四個方向：

01網路多媒體技術

02傳媒信息安全

03數字娛樂與動畫技術

04游戲製作

你報考的是網路多媒體技術對嗎？那你初試要考四門課程，分別是：

①政治

②俄、日、英語（二）選一

③數學（二）

④程序設計

PS附上
中國傳媒大學專業學位研究生入學考試
《程序設計》考試大綱

一、考試的總體要求
本考試大綱適用於報考中國傳媒大學工程碩士的計算機技術領域全日制專業學位研究生入學考試。《程序設計》是計算機科學與技術及相關學科的重要基礎，主要考核內容包括基於數據結構的程序設計和基於操作系統的程序設計兩大部分。要求考生對計算機科學與技術學科的基本知識、基本理論、基本方法有較深入、系統的理解，掌握各種數據結構的定義和實現演算法，掌握操作系統所涉及的關鍵內容，對C語言的基本知識有較深入的了解，掌握程序設計的基本方法，並具有綜合運用所學知識分析問題和解決問題的能力。

二、考試的內容
（一） 程序設計基礎
1、C語言的基本數據類型、各種運算符和表達式、基本控制結構。
2、數組的定義、數組元素的引用、數組的初始化，掌握與字元串相關的庫函數。
3、函數的定義語法，函數調用中參數的傳遞機制；局部變數和全局變數的有效范圍。
4、結構體類型變數的定義、結構體變數的引用、結構體變數的初始化方法，結構體數組的定義、初始化和結構體數組的應用，共同體變數的定義和使用方法。
5、地址和指針的基本概念，如何使用指針來處理數組、字元串以及結構體，函數指針的基本概念以及使用。
6、FILE的定義以及對文件進行的各種操作的庫函數。
（二） 線性表
1、 線性表的定義和基本操作
2、 線性表的實現
（1）順序存儲結構：實現順序表的查找、插入、刪除、合並、分解等操作的程序設計。
（2）鏈式存儲結構：實現單鏈表、循環鏈表、雙向鏈表、雙向循環鏈表的生成、查找、插入、刪除、遍歷以及鏈表的分解和歸並等操作的程序設計。
3、線性表的應用：從時間復雜度和空間復雜度的角度綜合比較線性表在順序和鏈式兩種存儲結構下的特點，即其各自適用的場合。運用順序表和鏈表的特點解決復雜的應用問題。
（三）棧、隊列和數組
1、棧和隊列的基本概念
2、棧和隊列的順序存儲結構和鏈式存儲結構及應用
（1）棧與遞歸的關系。
用遞歸解決的幾類問題：問題的定義是遞歸的；數據結構是遞歸的；以及問題的解法是遞歸的。
典型遞歸問題的演算法以及如何將遞歸演算法轉換為非遞歸演算法。
（2）在程序設計中，常需要棧這樣的數據結構，使得與保存數據時相反順序來使用這些數據。在後續章節中多處有棧和隊列的應用，如二叉樹遍歷的遞歸和非遞歸演算法、圖的深度優先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優先遍歷等則用到隊列。
3、特殊矩陣的壓縮存儲：對稱矩陣、對角矩陣、三角矩陣在壓縮存儲時的下標變換公式。
（四）樹與二叉樹
1、二叉樹
（1）二叉樹的定義及其主要特徵：二叉樹的五個性質及證明方法，並把這種方法推廣到K叉樹。
（2）二叉樹的順序存儲結構和鏈式存儲結構：二叉樹的順序存儲結構和二叉鏈表、三叉鏈表存儲結構的各自優缺點及適用場合。
（3）二叉樹的遍歷
二叉樹的先序，中序和後序遍歷演算法以及按層次遍歷。遍歷是基礎，在基本遍歷演算法的基礎上實現二叉樹的其它演算法。
（4）線索二叉樹的基本概念和構造
線索化演算法，線索化後二叉樹的遍歷演算法，基本線索二叉樹的其它演算法問題（如：查找某一類線索二叉樹中指定結點的前驅或後繼結點）。
（5）二叉排序樹
二叉排序樹的建立、查找、插入和刪除演算法，以及判斷某棵二叉樹是否二叉排序樹的演算法。
2、樹、森林
（1）樹的概念和存儲結構
（2）森林與二叉樹的轉換
（3）樹和森林的遍歷
樹與森林的遍歷，有兩種遍歷演算法：先根與後根（對於森林而言稱作：先序與中序遍歷）。二者的先根與後根遍歷與二叉樹中的遍歷演算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而後根遍歷對應二叉樹的中序遍歷。
（五）圖
1、圖的概念、存儲及基本操作
（1）鄰接矩陣法
（2）鄰接表法
2、圖的遍歷
深度優先搜索和廣度優先搜索是圖的兩種基本的遍歷演算法以及基於這兩種基本的遍歷演算法的程序設計。
3、圖的基本應用及其復雜度分析
（1）最小（代價）生成樹
（2）最短路徑
（3）拓撲排序
（4）關鍵路徑
（六）查找
1、查找的基本概念
2、順序查找法、折半查找法
3、散列（Hash）表及其查找
4、查找演算法的分析及應用
（七）內部排序
1、 排序的基本概念
2、插入排序
3、冒泡排序
4、簡單選擇排序
5、希爾排序
6、快速排序
7、堆排序
8、二路歸並排序
9、各種內部排序演算法的比較
各種排序方法的演算法思想及程序設計、手工模擬排序過程、性能分析（包括時間復雜度、空間復雜度、穩定性）。
10、內部排序演算法的應用
（八）進程管理
1、進程概念、進程的狀態與轉換
2、進程同步
（1）進程同步的基本概念
（2）實現臨界區互斥的基本方法
（3）信號量：PV原語的含義
（4）經典同步問題：生產者-消費者問題；讀者-寫者問題；哲學家進餐問題。
重點掌握 PV 操作的概念、流程，以及 PV 操作在同步與互斥問題中的應用。
3、死鎖的概念及處理策略

三、考試的基本題型
本試卷滿分為150分，其中：基於數據結構的程序設計 120分、基於操作系統的程序設計 30分。
主要題型有：選擇題、綜合應用題、程序設計題等。

四、考試的形式及時間
筆試，不需要任何輔助工具。考試時間為三小時。
希望採納

❸ 急求排序演算法性能分析程序

排序演算法全集【附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」;

❹ 幾種常見的排序演算法的實現與性能分析(數據結構)的報告

可參考 ：
http://blog.csdn.net/stubbornpotatoes/article/details/7513509

http://hi..com/shismbwb/item/404c94898cfd2855850fab24

❺ 選擇排序，快速排序，冒泡排序，堆排序，插入排序，基排序的程序的運行速度

分析如下：
冒泡排序：在最優情況下只需要經過n-1次比較即可得出結果，（這個最優情況那就是序列己是正序，從100K的正序結果可以看出結果正是如此），但在最壞情況下，即倒序（或一個較小值在最後），下沉演算法將需要n(n-1)/2次比較。所以一般情況下，特別是在逆序時，它很不理想。它是對數據有序性非常敏感的排序演算法。

冒泡排序2：它是冒泡排序的改良（一次下沉再一次上浮），最優情況和最壞情況與冒泡排序差不多，但是一般情況下它要好過冒泡排序，它一次下沉，再一次上浮，這樣避免了因一個數的逆序，而造成巨大的比較。如（2,3,4,…,n-1,n,1），用冒泡排序需要n(n-1)/2次比較，而此排序只要3輪,共比較(n-1)+(n-2)+(n-3)次，第一輪1將上移一位，第二輪1將移到首位，第三輪將發現無數據交換，序列有序而結束。但它同樣是一個對數據有序性非常敏感的排序演算法，只適合於數據基本有序的排序。

快速排序：它同樣是冒泡排序的改進，它通過一次交換能消除多個逆序，這樣可以減少逆序時所消耗的掃描和數據交換次數。在最優情況下，它的排序時間復雜度為O(nlog2n)。即每次劃分序列時，能均勻分成兩個子串。但最差情況下它的時間復雜度將是O(n^2)。即每次劃分子串時，一串為空，另一串為m-1（程序中的100K正序和逆序就正是這樣，如果程序中採用每次取序列中部數據作為劃分點，那將在正序和逆時達到最優）。從100K中正序的結果上看「快速排序」會比「冒泡排序」更慢，這主要是「冒泡排序」中採用了提前結束排序的方法。有的書上這解釋「快速排序」，在理論上講，如果每次能均勻劃分序列，它將是最快的排序演算法，因此稱它作快速排序。雖然很難均勻劃分序列，但就平均性能而言，它仍是基於關鍵字比較的內部排序演算法中速度最快者。

直接選擇排序：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情況下將快於冒泡排序。

堆排序：由於它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數為O(nlog2n)。它是對數據的有序性不敏感的一種演算法。但堆排序將需要做兩個步驟：－是建堆，二是排序（調整堆）。所以一般在小規模的序列中不合適，但對於較大的序列，將表現出優越的性能。

直接插入排序：簡單的插入排序，每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種演算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

希爾排序：增量的選擇將影響希爾排序的效率。但是無論怎樣選擇增量，最後一定要使增量為1，進行一次直接插入排序。但它相對於直接插入排序，由於在子表中每進行一次比較，就可能移去整個經性表中的多個逆序，從而改善了整個排序性能。希爾排序算是一種基於插入排序的演算法，所以對數據有序敏感。

歸並排序：歸並排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸並，將有無比的優勢。其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數據的有序性不敏感。若數據節點數據量大，那將不適合。但可改造成索引操作，效果將非常出色。

基數排序：在程序中採用的是以數值的十進制位分解，然後對空間採用一次性分配，因此它需要較多的輔助空間(10*n+10), （但我們可以進行其它分解，如以一個位元組分解，空間採用鏈表將只需輔助空間n+256）。基數排序的時間是線性的(即O(n))。由此可見，基數排序非常吸引人，但它也不是就地排序，若節點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字元串這樣能分解，若是浮點型那就不行了。

按平均時間將排序分為類：
(1) 平方階(O(n2))排序
各類簡單排序，例如直接插入、直接選擇和冒泡排序；
(2) 線性對數階(O(nlog2n))排序
如快速排序、堆排序和歸並排序；
(3) O(n1+§))排序
§是介於0和1之間的常數。希爾排序便是一種；
(4) 線性階(O(n))排序
本程序中的基數排序，此外還有桶、箱排序。

排序方法的選擇

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法很重要
(1)若n較小，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好，它會比選擇更少的比較次數；
但當記錄規模較大時，因為直接選擇移動的記錄數少於直接插人，所以宜用選直接選擇排序。
這兩種都是穩定排序演算法。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜(這里的隨機是指基準取值的隨機，原因見上的快速排序分析)；這里快速排序演算法將不穩定。
(3)若n較大，則應採用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸並排序序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序雖不會出現快速排序可能出現的最壞情況。但它需要建堆的過程。這兩種排序都是不穩定的。
歸並排序是穩定的排序演算法，但它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然後再合並，在效率上將有所提高。
(4)特殊的箱排序、基數排序
它們都是一種穩定的排序演算法，但有一定的局限性：
1、關鍵字可分解。
2、記錄的關鍵字位數較少，如果密集更好
3、如果是數字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。
事實上各種排序方法個有優缺點適用於不同的場合：
排序（Sorting)
插入排序（insertion sort）:直接插入排序 希爾排序（shell's sort）(縮小增量排序Diminishing increment sort)
交換排序：冒泡排序（bubble sort）快速排序（quick sort）
選擇排序:直接選擇排序（straight selection sort），堆排序；
歸並排序（merge sort）：
分配排序：箱排序（Bin sort）,基數排序（radix sort）
更多的自己研究一下。

排序方法的選取主要考慮演算法的性能與資源佔用。也就是速度和佔用的存儲空間。
希望對你有所幫助！

❻ 用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");
}
}

❼ 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[i]<<" ";
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[i])
{
iTemp = pData[i];
pData[i] = 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[i]<<" ";
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[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
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[i];
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[i]<<" ";
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[i]<middle) && (i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = 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[i]<<" ";
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[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = 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[i]<<" ";
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[i];
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[i]<<" ";
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[i]<middle) && (i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = 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[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
cout<<"\n";
}

❽ 求助期末數據結構課設，

什麼時候截止？
我有《內排序演算法分析》的C++代碼和分析報告，分析九個內排序演算法的，當時大一寫的。你要的話，我去取。最好寬限幾天，這幾天比較忙。呵呵，其實吧，這東西還是在參考別人的基礎上自己寫好 ^_^
如果著急的話，我給你個C++的停車場的程序。這個問題簡單一點，代碼比較少，雖然可以實現全部功能，但代碼量可能達不到要求。。。
給個郵箱，我把工程文件全發給你，如果你需要的話。

❾ 急！ 內部堆排序演算法的實現！！！包括大根堆的實現和小根堆的實現！！！要完整的！！！

1、 堆排序定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。

2、大根堆和小根堆
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。
根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
注意：
①堆中任一子樹亦是堆。
②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。

3、堆排序特點
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。

4、堆排序與直接插入排序的區別
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重復執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。

5、堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。

（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。

（2）大根堆排序演算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。

（3）堆排序的演算法：
void HeapSort(SeqIAst R)
{ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i；
BuildHeap(R)； //將R[1-n]建成初始堆
for(i=n;i>1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最後一個記錄交換
Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質
} //endfor
} //HeapSort

（4） BuildHeap和Heapify函數的實現
因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現。
① Heapify函數思想方法
每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換後，新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外，其餘任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。
"篩選法"調整堆
R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。若R[low].key不小於這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整；否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換後又可能使結點R[large]違反堆性質，同樣由於該結點的兩棵子樹(若存在)仍然是堆，故可重復上述的調整過程，對以R[large]為根的樹進行調整。此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。
具體的演算法

②BuildHeap的實現
要將初始文件R[l..n]調整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結點為根的子樹都調整為堆。
顯然只有一個結點的樹是堆，而在完全二叉樹中，所有序號 的結點都是葉子，因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ， -1，…，1的結點作為根的子樹都調整為堆即可。
具體演算法。

5、大根堆排序實例
對於關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況參見。

6、 演算法分析
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1)，
它是不穩定的排序方法。

❿ 我是湖南邵陽職業技術學院的專科學生，學的是計算機科學與技術，然後明年升考吉首大學的 計算機科學與應用

《微機原理》考試大綱
第一章 概述
1.計算機中的數和編碼系統
（1）理解計算機中的數制的概念，會應用；（2）掌握二進制編碼的方法；
（3）掌握二進制運算的規則；（4）掌握帶符號數的表示方法及表示範圍；
2.了解計算機的硬體和軟體的劃分及功能
3.微型計算機的結構
（1）了解微型計算機的外部結構；
（2）了解微型計算機的內部結構；
4. Intel 8088的結構
（1）掌握8088的寄存器結構；（2）掌握8088的功能結構；
（3）掌握存儲器組織；
第二章 8088的指令系統
1.掌握8088的定址方式
（1）立即定址（2）直接定址（3）寄存器定址（4）寄存器間接定址（5）變址定址（6）基址加變址的定址方式
2.掌握8088標志寄存器中的9個標志位
3.掌握8088的指令系統
（1）數據傳送指令（2）算術運算指令（3）邏輯運算指令
第三章 匯編語言程序設計
1.正確掌握匯編語言的格式；
2.了解語句行的構成，會應用；
3.理解指示性語句，會正確使用；
4.掌握基本的匯編語言程序設計
（1）循環程序設計（2）參數傳送技術（3）子程序設計
第四章 8088的匯流排操作和時序
1.基本概念
（1）正確理解指令周期、匯流排周期和T狀態的概念；
（2）掌握CPU的時序和存儲器以及外設的時序概念；
2. 8088的匯流排
（1）掌握8088的兩種組態的區別；
3.掌握8088典型時序
（1）存儲器讀周期（2）存儲器寫周期（3）中斷響應周期
4.最大組態下的8088時序與最小組態的8088時序區別
5.計數器和定時器電路Intel 8253-PIT
（1）了解8253-PIT晶元的主要功能及內部結構；（2）會寫8253-PIT的控制字；（3）掌握8253-PIT的工作方式；（4）掌握8253-PIT編程步驟；
第五章 半導體存儲器
1.解半導體存儲器的分類
2.讀寫存儲器RAM
（1）了解基本存儲電路（2）理解RAM的結構(3)掌握RAM與CPU的連接要考慮的主要問題；會根據連接圖寫出定址范圍
第六章 輸入和輸出
1.了解輸入輸出的定址方式
2.掌握CPU與外設數據傳送的方式
（1）無條件傳送方式（2）查詢傳送方式（3）中斷傳送方式（4）直接數據通道傳送（DMA）
第七章 中斷
1.中斷的引入
（1）理解為什麼要用中斷（2）掌握中斷系統的功能
2.最簡單的中斷情況
（1）掌握CPU響應中斷的條件（2）掌握CPU對中斷的響應
4. 8088的中斷方式
（1）掌握兩條外部中斷請求線及使用
（2）掌握內部中斷類型號
（3）掌握8088中斷優先權次序
（4）掌握8088中斷向量表的大小、中斷向量的個數及中斷入口地址的求法
（5）掌握8088中的中斷響應和處理過程
第八章 並行介面片子
1.了解可編程的輸入輸出介面晶元8255A-5的功能和結構
2.掌握8255A各埠的工作方式及功能

教材：《微型計算機系統原理及應用》 周明德, 清華大學出版社
參考書：
1、《微型計算機原理與介面技術》李蘭友等編，南開大學出版社，2001年版�
2、《計算機電路基礎》王金剛編，南開大學出版社，2001年版�

考題類型及分數分布：
本課程考試試題類型填空題、分析程序題、簡答題、綜合應用題四種形式，其中填空題20分、分析程序題15分、簡答題20分，綜合應用題20分
《數據結構》考試大綱
第一章 緒論
一、學習目的和要求
本章的目的是介紹數據結構中常用的基本概念和術語以及學習數據結構的意義。
本章要了解數據的抽象類型定義。理解演算法在實際問題中的應用。重點掌握各種基本概念和術語、演算法描述和分析的方法。
二、課程內容
第一節 什麼是數據結構
第二節 基本概念和術語
第三節 抽象數據類型的表示與實現
第四節 演算法和演算法分析
三、考核知識點
1、 合適的數據結構在解決實際應用問題中的關鍵性；以及學習《數據結構》的意義。
2、 數據、數據元素、數據項、數據結構等基本概念。
3、 數據結構的四種邏輯結構和兩種存儲結構表示方法。
4、 抽象數據類型的表示和實現
5、 演算法的五個特點。
6、 演算法、演算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。
7、 演算法描述和演算法分析的方法，對於一般演算法能分析出時間復雜度。
四、考核要求
1. 識記
1) 數據結構的基本概念和術語。
2) 合適的數據結構在解決實際應用問題中的關鍵性，以及學習《數據結構》的意義。
3) 數據結構的四種邏輯結構和兩種存儲結構表示方法。
2. 領會
1) 演算法的描述和分析：演算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度
第二章 線性表
一、學習目的和要求
本章的目的是介紹線性表的邏輯結構和各種存儲表示方法，以及定義在邏輯結構上的各種基本運算及其在存儲結構上如何實現這些基本運算。要求在熟悉這些內容的基礎上，能夠針對具體應用問題的要求和性質，選擇合適的存儲結構設計出相應的有效演算法，解決與線性表相關的實際問題。
本章重點是熟練掌握順序表和單鏈表上實現的各種基本運算及相關的時間性能分析，難點是在循環鏈表和雙向鏈表存儲結構中各種基本運算的實現。
二、課程內容
第一節 線性表的類型定義
第二節 線性表的順序表示和實現
第三節 線性表的鏈式表示和實現
三、考核知識點
1、 線性表的類型定義
2、 順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析
3、 鏈式表示和實現，單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；
4、 單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。
5、 循環鏈表上尾指針取代頭指針的作用
6、 單循環鏈表上的演算法與單鏈表上相應演算法的異同點。
7、 雙向鏈表的定義和相關演算法。
8、 順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優的時空性能。
四、考核要求
1. 識記
1) 線性表的邏輯結構特徵；
2) 線性表上定義的基本運算，並利用基本運算構造出較復雜的運算。
2. 領會
1) 順序表和鏈表的比較，各自的優缺點。
2) 針對線性表上所需要執行的主要操作，知道選擇順序表還是鏈表作為其存儲結構才能取得較優的時空性能。
3. 綜合應用
1) 順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析。
2) 單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；
3) 單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。
4) 循環鏈表上尾指針取代頭指針的作用，
5) 單循環鏈表上的演算法與單鏈表上相應演算法的異同點。
6) 雙鏈表的定義和相關演算法。
第三章 棧和隊列
一、學習目的和要求
本章的目的是介紹棧和隊列的邏輯結構定義及在兩種存儲結構上如何實現棧和隊列的基本運算。要求在掌握棧和隊列的特點的基礎上，懂得在什麼樣的情況下使用棧或隊列。
本章重點是掌握棧和隊列在兩種存儲結構上實現的基本運算，難點是循環隊列中對邊界條件的處理
二、課程內容
第一節 棧
第二節 棧的應用舉例
第四節 隊列
三、考核知識點
1、 棧的抽象數據類型的定義
2、 棧的表示和實現
3、 棧的簡單應用
4、 抽象數據類型隊列的定義
5、 隊列的鏈式表示和實現
6、 隊列的順序表示和實現
四、考核要求
1. 領會
1) 棧和隊列的特點，棧和隊列各自的使用情況。
2. 綜合應用
1) 棧的邏輯結構特點，棧與線性表的異同。
2) 順序棧和鏈棧上實現進棧、退棧等基本演算法。
3) 利用棧解決簡單的實際問題。
4) 隊列邏輯結構特點，隊列與線性表的異同。
5) 順序隊列（主要是循環隊列）和鏈隊列上實現的入隊、出隊等基本演算法。
6) 順序隊列的「假溢出」現象及其採用循環隊列進行解決的方法。
第四章 串
一、學習目的和要求
本章的目的是介紹串的邏輯結構、存儲結構及其串上的基本運算。本章重點是掌握串的基本概念和三種表示方法，這也是難點。
二、課程內容
第一節 串類型的定義
第二節 串的表示和實現
三、考核知識點
1、 串的定義、空串、空格串、子串、主串、串相等。
2、 串的基本操作。
3、 串的順序存儲結構及在順序存儲結構下基本操作的實現。
4、 串的堆分配存儲表示及其在堆分配存儲結構下基本操作的實現。
5、 串的鏈式存儲表示
四、考核要求
1. 領會
1) 串的有關概念及其基本運算
2. 簡單應用
1) 串的三種存儲表示
2) 使用串解決與串相關的簡單的應用問題
第五章 數組和廣義表
一、學習目的和要求
本章的目的是介紹多維數組的邏輯結構特徵及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，要求熟悉這些內容。
本章重點是熟悉多維數組的存儲方式、矩陣的壓縮存儲方式、廣義表的定義及其表頭表尾的運算，難點是稀疏矩陣的壓縮存儲表示下轉置運算。
二、課程內容
第一節 數組的定義
第二節 數組的順序表示和實現
第三節 矩陣的壓縮存儲
第四節 廣義表的定義
第五節 廣義表的存儲結構
三、考核知識點
1、 數組的順序存儲結構。
2、 二維數組的按行存儲及按列存儲和計算數組元素的地址計算公式。
3、 矩陣的壓縮存儲、特殊矩陣的表示。
4、 廣義表的定義和操作(HEAD和TAIL)
5、 廣義表的2種存儲結構
四、考核要求
1. 領會
1) 多維數組的邏輯結構特徵
2) 多維數組的順序存儲結構及其地址計算方式
3) 特殊矩陣和稀疏矩陣的概念
4) 稀疏矩陣的壓縮存儲方式——三元組表
5) 稀疏矩陣的兩種轉置運算演算法
6) 廣義表的概念、廣義表和線性表的聯系
7) 廣義表表頭和表尾的概念及廣義表兩個特殊的基本運算，取表頭和取表尾。
8) 廣義表的兩種存儲結構
第六章 樹和二叉樹
一、學習目的和要求
本章的目的是介紹二叉樹的定義、性質、存儲結構、遍歷、線索化，樹的定義、存儲結構、遍歷、樹和森林的轉換及赫夫曼樹及其赫夫曼編碼等內容。本章重點是掌握二叉樹及其二叉樹的遍歷。難點是掌握與樹有關的簡單應用。
二、課程內容
第一節 樹的定義和基本術語
第二節 二叉樹
第三節 遍歷二叉樹和線索二叉樹
第四節 樹和森林
第六節 赫夫曼樹及其應用
三、考核知識點
1、 樹的定義和術語。
2、 二叉樹(完全二叉樹、滿二叉樹)的定義和性質(結論)、二叉樹的存儲結構——順序表示法和鏈表表示法。
3、 二叉樹的三種遍歷方法及相應的遞歸演算法。
4、 二叉樹線索化的目的及其實質。
5、 樹的存儲表示法——孩子表示法、雙親表示法、孩子兄弟表示法。
6、 樹和森林及二叉樹的轉換方法。
7、 樹和森林的遍歷
8、 樹的路徑長度、樹的帶權路徑長度、赫夫曼樹（最優二叉樹）的構造方法。
9、 赫夫曼編碼方法
四、考核要求
1. 領會
1) 樹的邏輯結構特徵
2) 樹的不同表示方法
3) 樹的常用術語及含義
4) 二叉樹線索化的目的及實質
5) 在中序線索樹中查找給定結點的中序前驅和中序後繼的方法
6) 樹和森林與二叉樹之間的轉換方法
7) 樹的各種存儲結構及其特點
8) 樹的遍歷方法
2. 簡單應用
1) 二叉樹的定義及樹與二叉樹的差別
2) 二叉樹的性質，了解相應的證明方法
3) 二叉樹的兩種存儲結構、特點及適用范圍
4) 最優二叉樹和前綴編碼的概念及特點
5) 赫夫曼演算法的思想
6) 根據給定的葉結點及其權值構造出相應的最優二叉樹
7) 根據最優二叉樹構造對應的赫夫曼編碼
3. 綜合應用
1) 二叉樹的三種遍歷演算法，理解其執行過程
2) 根據不同的遍歷方法，應能得出其相應的結點訪問次序
3) 以遍歷演算法為基礎，設計有關演算法解決簡單的應用問題
第七章 圖
一、學習目的和要求
本章的目的是介紹圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用演算法。本章重點是掌握圖的兩種存儲結構上實現的遍歷演算法。難點是圖的應用演算法：最小生成樹，求最短路徑以及拓撲排序。只要求掌握這些演算法的基本思想及時間性能。
二、課程內容
第一節 圖的定義和術語
第二節 圖的存儲結構
第三節 圖的遍歷
第四節 圖的連通性問題
第五節 有向無環圖及其應用
第六節 最短路徑
三、考核知識點
1、 圖的邏輯結構特徵
2、 圖的常用術語及含義
3、 圖的鄰接矩陣表示法存儲結構
4、 鄰接表表示法
5、 圖的深度優先遍歷
6、 圖的廣度優先遍歷
7、 生成樹和最小生成樹
8、 構造最小生成樹的PRIM演算法思想和時間性能
9、 構造最小生成樹的Kruskal演算法思想和時間性能
10、 拓撲排序
11、 關鍵路徑
12、 關於最短路徑的演算法——Dijkstra演算法思想
四、考核要求
1. 領會
1) 圖的邏輯結構及特徵
2) 圖的常用術語及含義
3) 生成樹和最小生成樹的概念
4) 對給定的圖遍歷，畫出深度優先和廣度優先生成樹或森林
5) Prim和 Kruskal演算法的基本思想、時間性能及這兩種演算法各自的特點
6) 要求對給定的連通圖，根據Prim和Kruskal演算法構造最小生成樹
7) 最短路徑的含義
8) 求單源點的最短路徑問題的Dijkstra演算法的基本思想和時間性能
9) 拓撲排序的基本思想和步驟
10) 拓撲排序不成功的原因
11) 對給定的有向圖，若拓撲序列存在，則要求寫出一個或多個拓撲序列
2. 簡單應用
1) 圖的鄰接矩陣表示法和鄰接表表示法
2) 根據應用問題的特點選擇合適的存儲結構
3) 連通圖及非連通圖的深度優先搜索和廣度優先搜索兩種遍歷演算法。
4) 確定兩種遍歷的頂點訪問序列
5) 圖的兩種遍歷和樹的遍歷之間的關系
6) 兩種遍歷演算法分別使用的數據結構（棧和隊列）
7) 利用圖的遍歷解決簡單的應用問題
第九章 查找
一、學習目的和要求
本章的目的是介紹線性表、樹和哈希表的查找方法、演算法實現以及各種查找方法的時間性能（平均查找長度）分析。重點掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和演算法實現。難點是二叉排序樹上的刪除演算法。
二、課程內容
第一節 靜態查找表
第二節 動態查找表
第三節 哈希表
二、 考核知識點
1、 查找的定義關鍵字、查找、平均查找長度
2、 靜態查找表的查找演算法（順序查找、折半查找、分塊查找(索引順序表的查找)） 及其效率(最壞和平均長度)。
3、 二叉排序樹的查找演算法及其效率。
4、 平衡二叉樹的定義。
5、 哈希法的特點
6、 哈希函數和散列地址。
7、 構造哈希函數的幾種方法。直接定址法、除留余數法、平方取中法、折疊法、數字分析法。
8、 處理沖突的方法：開放定址法和鏈地址法。開放定址法又分為線性探測再散列、二次探測再散列和偽隨機探測再散列。
四、考核要求
1. 識記
1) 查找在數據處理中的重要性
2) 查找成功、不成功的含義
2. 簡單應用
1) 順序查找、折半查找、分塊查找的基本思想、演算法實現和查找效率分析
2) 順序查找中「監視哨」的作用
3) 比較線性表上三種查找方法的優缺點，能根據實際問題的要求和特點，選擇出 合適的查找方法
4) 二叉排序樹和二叉平衡樹的定義、特點
5) 二叉排序樹的插入、刪除、建樹和查找演算法及時間性能
6) 建立一棵二叉排序樹的過程就是對輸入序列的排序過程，輸入序列對所建立的二叉排序樹形態的影響
7) 哈希表、哈希函數、哈希地址（散列地址）、裝填因子等有關概念
8) 哈希函數的構造方法和解決沖突的方法
9) 哈希表和其它表的本質區別
第十章 內部排序
一、學習目的和要求
本章的目的是介紹五類內部排序方法的基本思想、排序過程、演算法實現、時間和空間性能的分析以及各種排序方法的比較和選擇。重點掌握快速排序、堆排序、歸並排序和基數排序的基本思想和排序過程。難點是這四類排序演算法的實現。
二、課程內容
第一節 概述
第二節 插入排序
第三節 快速排序
第四節 選擇排序
第五節 歸並排序
第六節 基數排序
第七節 各種內部排序方法的比較討論
三、 考核知識點
1、 排序的目的、分類和排序方法的穩定性的定義。
2、 插入排序：直接插入排序的演算法、折半插入排序的演算法、希爾排序的思想。
3、 選擇排序的思想
4、 堆排序的方法、堆的定義、初始堆的建立。
5、 起泡排序的思想。
6、 快速排序的演算法、快速排序的最壞情況時間復雜度的分析。
7、 歸並排序的思想。
8、 基數排序的思想及特點。
四、考核要求
1. 識記
1) 排序在數據處理中的重要性
2) 排序方法穩定性的含義
3) 排序方法的分類及演算法好壞的評判標准
2. 領會
1) 歸並排序的基本思想和演算法實現，以及時間性能分析
2) 針對給定的輸入序列，能寫出歸並排序的排序過程
3) 基數排序的基本思想
4) 分配排序和其它幾類排序方法的區別
3. 簡單應用
1) 堆、極小堆、極大堆、堆頂等有關概念和定義
2) 堆的性質及堆與完全二叉樹的關系
3) 直接選擇排序和堆排序的基本思想和演算法實現，以及時間性能分析
4) 針對給定的輸入序列，寫出堆排序的排序過程
5) 比較各種排序演算法的優缺點
6) 根據實際問題的特點和要求選擇合適的排序方法
4. 綜合應用
1) 直接插入排序的基本思想和演算法實現，以及在最好、最壞和平均情況下的時間性能分析
2) 直接插入排序中「監視哨」的作用
3) 針對給定的輸入序列，要能寫出直接插入排序的排序過程
4) 起泡排序的基本思想
5) 快速排序的基本思想和演算法實現，以及在最好、最壞和平均情況下的時間性能分析，了解演算法的穩定性
6) 樞軸元素的選擇對排序的影響
7) 針對給定的輸入序列，能寫出快速排序的排序過程
第十二章 文 件
一、學習目的和要求
本章的目的是介紹存儲在外存上的數據結構（文件）的有關概念、各種文件及其特點、組織方式及其查詢和更新操作，要求對這些內容做一般性的了解，本章不是重點。。
二、課程內容
第一節 有關文件的基本概念
第二節 順序文件
第三節 索引文件
第四節 ISAM文件和VSAM文件
第五節 直接存取文件
第六節 多關鍵字文件
三、考核知識點
9、 文件的基本概念
10、 常用的文件組織方式：順序文件、索引文件、散列文件和多關鍵字文件
11、 順序文件的特點及查找方法
12、 索引文件的組織方式
13、 索引順序文件常用的有兩種：ISAM文件和VSAM文件
14、 散列文件（直接存取文件）的特點及優點
15、 兩種多關鍵字文件的組織方法：多重表文件和倒排表
四、考核要求
1. 識記
1) 文件的基本概念
2) 常用的文件組織方式：順序文件、索引文件、散列文件和多關鍵字文件
3) 順序文件的特點及查找方法
4) 索引文件的組織方式
5) 索引順序文件常用的有兩種：ISAM文件和VSAM文件
6) 散列文件（直接存取文件）的特點及優點
7) 兩種多關鍵字文件的組織方法：多重表文件和倒排表

教材：《數據結構》（C語言版）嚴蔚敏 吳偉民 編著，清華大學出版社1996年版。

考題類型及分數分布：
本課程考試試題類型填空題、問答題、綜合應用題三種形式，其中填空題20分、問答題25分，綜合應用題30分。
這是2010考試的考綱，我想2011年考綱不會有太大的變化