程序員堆排序演算法

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

分析如下：
冒泡排序：在最優情況下只需要經過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）
更多的自己研究一下。

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

⑵ 堆排序演算法的實現

#include<stdio.h>
#include<malloc.h>
#include<time.h>
#define LISTSIZE 100
#define MORESIZE 100
#define overflow -1
typedef struct
{
int data;
int fre;
}Cell;
typedef struct {
Cell *elem;
long int length;
unsigned long int count1;
unsigned long int count2;
long int listsize;
}SqList;
SqList L1;
clock_t start,end;
FILE *p,*w;
int main (void)
{
void assign(Cell *a,Cell *b);
int LT(int a,int b);
void HeapSort (SqList &H);
void HeapAdjust (SqList &H,int s , int m);
void exchange(Cell *a,Cell *b);

//讀入

int time=0;
while(time<4)
{
switch (time)
{
case 0:
p=fopen("data01.txt","r");
w=fopen("sorted01.txt","w");
break;
case 1:
p=fopen("data02.txt","r");
w=fopen("sorted02.txt","w");
break;
case 2:
p=fopen("data03.txt","r");
w=fopen("sorted03.txt","w");
break;
case 3:
p=fopen("data04.txt","r");
w=fopen("sorted04.txt","w");
break;
}

L1.count1=0;
L1.count2=0;

time++;
L1.elem=(Cell *)malloc((LISTSIZE+1)*sizeof(Cell));
L1.listsize=LISTSIZE;
L1.length=1;
Cell *newbase;
while(!feof(p))
{

if (L1.length>L1.listsize){
newbase=(Cell *)realloc(L1.elem,(L1.listsize+MORESIZE+1)*sizeof(Cell));
if (!newbase)
return overflow;
L1.elem=newbase;
L1.listsize+=MORESIZE;}
fscanf (p,"%d (%d)\n",&((L1.elem+L1.length)->data),&((L1.elem+L1.length)->fre));
L1.length++;
}
L1.length--;
printf ("listsize=%d length=%d\n",L1.listsize,L1.length);

//排序
start=clock();//開始計時
HeapSort(L1); //堆排序
end=clock(); //結束計時
printf ("Time: %lf\n",(double)(end-start)/CLOCKS_PER_SEC);//輸出時間
for (int i=1;i<L1.length+1;++i)
fprintf (w,"%d (%d)\n",(L1.elem+i)->data,(L1.elem+i)->fre);
fprintf (w,"比較次數%u,移動次數%u\n",L1.count1,L1.count2);
printf ("比較次數%u,移動次數%u\n",L1.count1,L1.count2);
fprintf (w,"Copyright Reserved,Cheng Xuntao,NWPU");
fclose(p);
fclose(w);
}

return 0;

}
int LT(int a,int b)//比較函數
{L1.count1++;<br/> if (a<b){<br/> <br/> return 1;}
else return 0;
}
void assign(Cell *a,Cell *b)//賦值函數
{
a->data=b->data;
a->fre=b->fre;
L1.count2++;
}
void exchange(Cell *a,Cell *b)//交換記錄
{
int temp;
temp=a->data;
a->data=b->data;
b->data=temp;
temp=a->fre;
a->fre=b->fre;
b->fre=temp;
L1.count2+=3; //+=3
}
void HeapAdjust (SqList &H,int s , int m)//調節其成為堆
{
Cell *rc;
rc=(Cell *)malloc(sizeof(Cell));
int j;
assign(rc,H.elem+s); //暫存
for (j=2*s;j<=m;j*=2){ //沿值較大的孩子節點向下篩選
if (j<m && LT((H.elem+j)->data,(H.elem+j+1)->data ))
j++; //j為值較大的記錄的下標
if (!LT(rc->data,(H.elem+j)->data))
break; //rc應插入在位置s上
assign((H.elem+s),(H.elem+j));
s=j;
}
assign((H.elem+s),rc); //插入
}//HeapAdjust
void HeapSort (SqList &H) //堆排序
{
int i;
for (i=H.length/2;i>0;--i) //把L.elem[1...H.length]建成堆
HeapAdjust(H,i,H.length);
for (i=H.length;i>1;--i)
{
exchange(H.elem+1,H.elem+i); //將堆頂記錄和當前未經排序的子序列L.elem[i...i]中最後一個記錄相互交換
HeapAdjust(H,1,i-1); //重新調整其為堆
}
}//HeapSort

⑶ 程序員必須掌握哪些演算法

一.基本演算法:

枚舉. (poj1753,poj2965)

貪心(poj1328,poj2109,poj2586)

遞歸和分治法.

遞推.

構造法.(poj3295)

模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.

最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)

二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)

最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.數據結構.

串 (poj1035,poj3080,poj1936)

排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)

簡單並查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)

堆

trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜索

深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

背包問題. (poj1837,poj1276)

型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學

組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.

幾何公式.

叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:
一.基本演算法:

C++的標准模版庫的應用. (poj3096,poj3007)

較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)

最小費用最大流(poj2516,poj2516,poj2195)

雙連通分量(poj2942)

強連通分支及其縮點.(poj2186)

圖的割邊和割點(poj3352)

最小割模型、網路流規約(poj3308)

三.數據結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

靜態二叉檢索樹. (poj2482,poj2352)

樹狀樹組(poj1195,poj3321)

RMQ. (poj3264,poj3368)

並查集的高級應用. (poj1703,2492)

KMP演算法. (poj1961,poj2406)

四.搜索

最優化剪枝和可行性剪枝

搜索的技巧和優化 (poj3411,poj1724)

記憶化搜索(poj3373,poj1691)

五.動態規劃

較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)

樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.

坐標離散化.

掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)

幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級（regional中等難度）:
一.基本演算法要求:

代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)

最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)

最小樹形圖(poj3164)

次小生成樹.

無向圖、有向圖的最小環

三.數據結構.

trie圖的建立和應用. (poj2778)

LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).

後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索

較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.

較難的狀態DP(poj3133)

六.數學

組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.

半平面求交(poj3384,poj2540)

可視圖的建立(poj2966)

點集最小圓覆蓋.

對踵點(poj2079)

⑷ 關於c語言排序問題

排 序：
程序員可以使用的基本排序演算法有5種：
·插入排序(insertionsort．)
·交換排序(exchangesOrt)
·選擇排序(selectionsort)
·歸並排序(mergesort)
·分布排序(distributionsort)

為了形象地解釋每種排序演算法是怎樣工作的，讓我們來看一看怎樣用這些方法對桌上一付亂序的牌進行排序。牌既要按花色排序(依次為梅花、方塊、紅桃和黑心)，還要按點數排序(從2到A)。
插入排序的過程為：從一堆牌的上面開始拿牌，每次拿一張牌，按排序原則把牌放到手中正確的位置。桌上的牌拿完後，手中的牌也就排好序了。
交換排序的過程為：
(1)先拿兩張牌放到手中。如果左邊的牌要排在右邊的牌的後面，就交換這兩張牌的位置。
(2)然後拿下一張牌，並比較最右邊兩張牌，如果有必要就交換這兩張牌的位置。
(3)重復第(2)步，直到把所有的牌都拿到手中。
(4)如果不再需要交換手中任何兩張牌的位置，就說明牌已經排好序了；否則，把手中的牌放到桌上，重復(1)至(4)步，直到手中的牌排好序。
選擇排序的過程為：在桌上的牌中找出最小的一張牌，拿在手中；重復這種操作，直到把所有牌都拿在手中。
歸並排序的過程為：把桌上的牌分為52堆，每堆為一張牌。因為每堆牌都是有序的(記住，此時每堆中只有一張牌)，所以如果把相鄰的兩堆牌合並為一堆，並對每堆牌進行排序，就可以得到26堆已排好序的牌，此時每一堆中有兩張牌。重復這種合並操作，就可以依次得到13堆牌(每一堆中有4張牌)，7堆牌(有6堆是8張牌，還有一堆是4張牌)，最後將得到52張的一堆牌。
分布排序(也被稱作radix sort，即基數排序)的過程為：先將牌按點數分成13堆，然後將這13堆牌按點數順序疊在一起；再將牌按花色分成4堆，然後將這4堆牌按花色順序疊在一起，牌就排好序了。
在選用排序演算法時，你還需要了解以下幾個術語：
(1)自然的(natural)
如果某種排序演算法對有序的數據排序速度較快(工作量變小)，對無序的數據排序速度卻較慢(工作變數大)，我們就稱這種排序演算法是自然的。如果數據已接近有序，就需要考慮選用自然的排序演算法。
(2)穩定的(stable)
如果某種排序演算法能保持它認為相等的數據的前後順序，我們就稱這種排序演算法是穩定的。
例如，現有以下名單：
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用穩定的排序演算法按姓對上述名單進行排序，那麼在排好序後"Mary Jones」和"Tom Jones」將保持原來的Jr順序，因為它們的姓是相同的。
穩定的排序演算法可按主、次關鍵字對數據進行排序，例如按姓和名排序(換句話說，主要按姓排序，但對姓相同的數據還要按名排序)。在具體實現時，就是先按次關鍵字排序，再按主關鍵字排序。
(3)內部排序(internal sort)和外部排序(external sort)
待排數據全部在內存中的排序方法被稱為內部排序，待排數據在磁碟、磁帶和其它外存中的排序方法被稱為外部排序。

查 找：
和排序演算法一樣，查找(searching)演算法也是計算機科學中研究得最多的問題之一。查找演算法和排序演算法是有聯系的，因為許多查找演算法依賴於要查找的數據集的有序程度。基本的查找演算法有以下4種：
·順序查找(sequential searching)。
·比較查找(comparison searching)
·基數查找(radix searching)
·哈希查找(hashing)
下面仍然以一付亂序的牌為例來描述這些演算法的工作過程。
順序查找的過程為：從第一張開始查看每一張牌，直到找到要找的牌。
比較查找(也被稱作binarysearching，即折半查找)要求牌已經排好序，其過程為：任意抽一張牌，如果這張牌正是要找的牌，則查找過程結束。如果抽出的這張牌比要找的牌大，則在它前面的牌中重復查找操作；反之，則在它後面的牌中重復查找操作，直到找到要找的牌。
基數查找的過程為：先將牌按點數分成13堆，或者按花色分成4堆。然後找出與要找的牌的點數或花色相同的那一堆牌，再在這堆牌中用任意一種查找演算法找到要找的牌。
哈希查找的過程為：
(1)在桌面上留出可以放若干堆牌的空間，並構造一個函數，使其能根據點數和花色將牌映射到特定的堆中(這個函數被稱為hashfunction，即哈希函數)。
(2)根據哈希函數將牌分成若干堆。
(3)根據哈希函數找到要找的牌所在的堆，然後在這一堆牌中找到要找的牌。
例如，可以構造這樣一個哈希函數：
pile=rank+suit
其中，rank是表示牌的點數的一個數值；suit是表示牌的花色的一個數值；pile表示堆值，它將決定一張牌歸入到哪一堆中。如果用1，2，……，13分別表示A，2，……．K，用0，1，2和3分別表示梅花、方塊、紅桃和黑桃，則pile的值將為1，2，……，16，這樣就可以把一付牌分成16堆。
哈希查找雖然看上去有些離譜，但它確實是一種非常實用的查找演算法。各種各樣的程序，從壓縮程序(如Stacker)到磁碟高速緩存程序(如SmartDrive)，幾乎都通過這種方法來提高查找速度，

排序或查找的性能：
有關排序和查找的一個主要問題就是速度。這個問題經常被人們忽視，因為與程序的其餘部分相比，排序或查找所花費的時間幾乎可以被忽略。然而，對大多數排序或查找應用來說，你不必一開始就花很多精力去編制一段演算法程序，而應該先在現成的演算法中選用一種最簡單的(見3．1和3．4)，當你發現所用的演算法使程序運行很慢時，再換用一種更好的演算法(請參見下文中的介紹)。
下面介紹一種判斷排序或查找演算法的速度的方法。
首先，引入一個演算法的復雜度的概念，它指的是在各種情況(最好的、最差的和平均的)下排序或查找需要完成的操作次數，通過它可以比較不同演算法的性能。
演算法的復雜度與排序或查找所針對的數據集的數據量有關，因此，引入一個基於數據集數據量的表達式來表示演算法的復雜度。
最快的演算法的復雜度O(1)，它表示演算法的操作次數與數據量無關。復雜度O(N)(N表示數據集的數據量)表示演算法的操作次數與數據量直接相關。復雜度O(logN)介於上述兩者之間，它表示演算法的操作次數與數據量的對數有關。復雜度為O(NlogN)(N乘以logN)的演算法比復雜度為O(N)的演算法要慢，而復雜度為O(N2)的演算法更慢。
注意：如果兩種演算法的復雜度都是O(logN)，那麼logN的基數較大的演算法的速度要快些，在本章的例子中，logN的基數均為10

⑸ 跪求一個使用C＋＋語言寫的堆排序演算法！！

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 10000
#define _cp(a,b) ((a)<(b))//最小堆，若要最大堆將'<'改為'>'
typedef int elem_t;

struct heap
{
elem_t h[MAXN];
int n,p,c;
void init(){n=0;}
void ins(elem_t e){//插入一個元素e
for (p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);//插入一個元素，並調整堆
h[p]=e;
}
int del(elem_t& e){//e賦值為堆頂元素，刪掉堆頂元素後並重建堆，堆空返回0，否則返回1
if (!n) return 0;
for (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[p]=h[c],p=c,c<<=1);//取堆頂元素並調整堆
h[p]=h[n--];
return 1;
}
void show()
{
printf("\n,堆中有%d個元素：\n他們是：",n);
int i;
for(i=1;i<=n;++i)
{
cout<<h[i]<<" ";
}
cout<<endl;
system("pause");
}
heap(){init();}
};

int main()
{
cout<<"輸入要讀入的元素個數n（0表示退出），和n個元素,之間用空格隔開\n";
int n;
while(cin>>n&&n)
{
heap oneheap;
int i,tmp;
for(i=0;i<n;++i)
{
cin>>tmp;
oneheap.ins(tmp);//將元素一個一個插入既是建堆
}
cout<<"排序後元素為：\n";
for(i=0;i<n;++i)
{
if(oneheap.del(tmp))cout<<tmp<<" ";//一個一個的刪除堆頂元素就是排序
else cout<<"堆空,無法刪除元素\n";
}
system("pause");
system("cls");
cout<<"\n輸入要讀入的元素個數n（0表示退出），和n個元素,之間用空格隔開\n";
}
return 0;
}
/*
編譯環境vc6.0
你注意heap裡面有個show()函數，在刪除一個元素，或插入一個元素後你可以show()一下， 既是重新建堆的結果。
主要的函數已經給出來了，原理自己都懂吧，程序你可以自己改改直到自己滿意！
*/

⑹ 計算機二級的中的「堆排序法」是怎麼排的

堆排序就是將所有待排序的元素組成一個堆，然後不斷彈出堆頂的元素並調用函數維持堆序，直到所有元素均被彈出後，排序完成。被彈出的元素序列即一個有序數列。

一般做法是這樣：

當一個節點被插入時，將該節點放在堆的末尾（這是為了保證堆是完全二叉樹）然後將該節點與它的父節點比較，看該節點是否大於（或小於）其父節點，即判斷當前的堆是否滿足堆序。如果不滿足，則將該節點與其父節點交換。

再將該節點與其新的父節點做比較，依此類推，直到該節點不再需要與其父節點交換為止。（即滿足堆序時停止） 當一個根節點被彈出（即被從堆中刪除）時，將堆最尾部的節點移動到頭結點的位置，然後將該節點不斷與其子節點比較，如果不符合堆序則交換，直到符合堆序為止。

(6)程序員堆排序演算法擴展閱讀：

堆的操作

堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：

最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點

創建最大堆（Build Max Heap）：將堆中的所有數據重新排序

堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

⑺ 數據結構 java開發中常用的排序演算法有哪些

排序演算法有很多，所以在特定情景中使用哪一種演算法很重要。為了選擇合適的演算法，可以按照建議的順序考慮以下標准：
（1）執行時間
（2）存儲空間
（3）編程工作
對於數據量較小的情形，（1）（2）差別不大，主要考慮（3）；而對於數據量大的，（1）為首要。

主要排序法有：
一、冒泡（Bubble）排序——相鄰交換
二、選擇排序——每次最小/大排在相應的位置
三、插入排序——將下一個插入已排好的序列中
四、殼（Shell）排序——縮小增量
五、歸並排序
六、快速排序
七、堆排序
八、拓撲排序

一、冒泡（Bubble）排序

----------------------------------Code 從小到大排序n個數------------------------------------
void BubbleSortArray()
{
for(int i=1;i<n;i++)
{
for(int j=0;i<n-i;j++)
{
if(a[j]>a[j+1])//比較交換相鄰元素
{
int temp;
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
-------------------------------------------------Code------------------------------------------------
效率 O（n²）,適用於排序小列表。

二、選擇排序
----------------------------------Code 從小到大排序n個數--------------------------------
void SelectSortArray()
{
int min_index;
for(int i=0;i<n-1;i++)
{
min_index=i;
for(int j=i+1;j<n;j++)//每次掃描選擇最小項
if(arr[j]<arr[min_index]) min_index=j;
if(min_index!=i)//找到最小項交換，即將這一項移到列表中的正確位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
-------------------------------------------------Code-----------------------------------------
效率O（n²），適用於排序小的列表。

三、插入排序
--------------------------------------------Code 從小到大排序n個數-------------------------------------
void InsertSortArray()
{
for(int i=1;i<n;i++)//循環從第二個數組元素開始，因為arr[0]作為最初已排序部分
{
int temp=arr[i];//temp標記為未排序第一個元素
int j=i-1;
while (j>=0 && arr[j]>temp)/*將temp與已排序元素從小到大比較，尋找temp應插入的位置*/
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
------------------------------Code--------------------------------------------------------------
最佳效率O（n）；最糟效率O（n²）與冒泡、選擇相同，適用於排序小列表
若列表基本有序，則插入排序比冒泡、選擇更有效率。

四、殼（Shell）排序——縮小增量排序
-------------------------------------Code 從小到大排序n個數-------------------------------------
void ShellSortArray()
{
for(int incr=3;incr<0;incr--)//增量遞減，以增量3，2，1為例
{
for(int L=0;L<(n-1)/incr;L++)//重復分成的每個子列表
{
for(int i=L+incr;i<n;i+=incr)//對每個子列表應用插入排序
{
int temp=arr[i];
int j=i-incr;
while(j>=0&&arr[j]>temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
--------------------------------------Code-------------------------------------------
適用於排序小列表。
效率估計O（nlog2^n）~O（n^1.5），取決於增量值的最初大小。建議使用質數作為增量值，因為如果增量值是2的冪，則在下一個通道中會再次比較相同的元素。
殼（Shell）排序改進了插入排序，減少了比較的次數。是不穩定的排序，因為排序過程中元素可能會前後跳躍。

五、歸並排序
----------------------------------------------Code 從小到大排序---------------------------------------
void MergeSort(int low,int high)
{
if(low>=high) return;//每個子列表中剩下一個元素時停止
else int mid=(low+high)/2;/*將列表劃分成相等的兩個子列表,若有奇數個元素，則在左邊子列表大於右側子列表*/
MergeSort(low,mid);//子列表進一步劃分
MergeSort(mid+1,high);
int [] B=new int [high-low+1];//新建一個數組，用於存放歸並的元素
for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*兩個子列表進行排序歸並，直到兩個子列表中的一個結束*/
{
if (arr[i]<=arr[j];)
{
B[k]=arr[i];
I++;
}
else
{ B[k]=arr[j]; j++; }
}
for( ;j<=high;j++,k++)//如果第二個子列表中仍然有元素，則追加到新列表
B[k]=arr[j];
for( ;i<=mid;i++,k++)//如果在第一個子列表中仍然有元素，則追加到新列表中
B[k]=arr[i];
for(int z=0;z<high-low+1;z++)//將排序的數組B的 所有元素復制到原始數組arr中
arr[z]=B[z];
}
-----------------------------------------------------Code---------------------------------------------------
效率O（nlogn），歸並的最佳、平均和最糟用例效率之間沒有差異。
適用於排序大列表，基於分治法。

六、快速排序
------------------------------------Code--------------------------------------------
/*快速排序的演算法思想：選定一個樞紐元素，對待排序序列進行分割，分割之後的序列一個部分小於樞紐元素，一個部分大於樞紐元素，再對這兩個分割好的子序列進行上述的過程。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low];//採用子序列的第一個元素作為樞紐元素
while (low < high)
{
//從後往前栽後半部分中尋找第一個小於樞紐元素的元素
while (low < high && arr[high] >= pivot)
{
--high;
}
//將這個比樞紐元素小的元素交換到前半部分
swap(arr[low], arr[high]);
//從前往後在前半部分中尋找第一個大於樞紐元素的元素
while (low <high &&arr [low ]<=pivot )
{
++low ;
}
swap (arr [low ],arr [high ]);//將這個樞紐元素大的元素交換到後半部分
}
return low ;//返回樞紐元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if (low <high )
{
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
----------------------------------------Code-------------------------------------
平均效率O（nlogn），適用於排序大列表。
此演算法的總時間取決於樞紐值的位置；選擇第一個元素作為樞紐，可能導致O（n²）的最糟用例效率。若數基本有序，效率反而最差。選項中間值作為樞紐，效率是O（nlogn）。
基於分治法。

七、堆排序
最大堆：後者任一非終端節點的關鍵字均大於或等於它的左、右孩子的關鍵字，此時位於堆頂的節點的關鍵字是整個序列中最大的。
思想：
(1)令i=l,並令temp＝ kl ;
(2)計算i的左孩子j=2i+1;
(3)若j<＝n－1，則轉(4),否則轉(6);
(4)比較kj和kj+1,若kj+1>kj,則令j＝j＋1，否則j不變；
(5)比較temp和kj，若kj>temp，則令ki等於kj，並令i=j,j=2i+1,並轉(3),否則轉(6)
(6)令ki等於temp，結束。
-----------------------------------------Code---------------------------
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]可能違反堆性質 } } ---------------------------------------Code--------------------------------------

堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。

堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。

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

八、拓撲排序
例 ：學生選修課排課先後順序
拓撲排序：把有向圖中各頂點按照它們相互之間的優先關系排列成一個線性序列的過程。
方法：
在有向圖中選一個沒有前驅的頂點且輸出
從圖中刪除該頂點和所有以它為尾的弧
重復上述兩步，直至全部頂點均已輸出（拓撲排序成功），或者當圖中不存在無前驅的頂點（圖中有迴路）為止。
---------------------------------------Code--------------------------------------
void TopologicalSort()/*輸出拓撲排序函數。若G無迴路，則輸出G的頂點的一個拓撲序列並返回OK，否則返回ERROR*/
{
int indegree[M];
int i,k,j;
char n;
int count=0;
Stack thestack;
FindInDegree(G,indegree);//對各頂點求入度indegree[0....num]
InitStack(thestack);//初始化棧
for(i=0;i<G.num;i++)
Console.WriteLine("結點"+G.vertices[i].data+"的入度為"+indegree[i]);
for(i=0;i<G.num;i++)
{
if(indegree[i]==0)
Push(thestack.vertices[i]);
}
Console.Write("拓撲排序輸出順序為：");
while(thestack.Peek()!=null)
{
Pop(thestack.Peek());
j=locatevex(G,n);
if (j==-2)
{
Console.WriteLine("發生錯誤，程序結束。");
exit();
}
Console.Write(G.vertices[j].data);
count++;
for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
{
k=p.adjvex;
if (!(--indegree[k]))
Push(G.vertices[k]);
}
}
if (count<G.num)
Cosole.WriteLine("該圖有環，出現錯誤，無法排序。");
else
Console.WriteLine("排序成功。");
}
----------------------------------------Code--------------------------------------
演算法的時間復雜度O（n+e）。

⑻ 作為程序員提高編程能力的幾個基礎演算法

一：快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序n個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(nlogn)演算法更快，因為它的內部循環（innerloop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divideandconquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。

演算法步驟：

1從數列中挑出一個元素，稱為「基準」（pivot），

2重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。

3遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

二：堆排序演算法

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

堆排序的平均時間復雜度為Ο(nlogn) 。

創建一個堆H[0..n-1]

把堆首（最大值）和堆尾互換

3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置

4.重復步驟2，直到堆的尺寸為1

三：歸並排序

歸並排序（Mergesort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（DivideandConquer）的一個非常典型的應用。

1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列

2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

3.比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置

4.重復步驟3直到某一指針達到序列尾

5.將另一序列剩下的所有元素直接復制到合並序列尾

四：二分查找演算法

二分查找演算法是一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半，時間復雜度為Ο(logn) 。

五：BFPRT(線性查找演算法)

BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間復雜度，五位演算法作者做了精妙的處理。

1.將n個元素每5個一組，分成n/5(上界)組。

2.取出每一組的中位數，任意排序方法，比如插入排序。

3.遞歸的調用selection演算法查找上一步中所有中位數的中位數，設為x，偶數個中位數的情況下設定為選取中間小的一個。

4.用x來分割數組，設小於等於x的個數為k，大於x的個數即為n-k。

5.若i==k，返回x；若i<k，在小於x的元素中遞歸查找第i小的元素；若i>k，在大於x的元素中遞歸查找第i-k小的元素。

終止條件：n=1時，返回的即是i小元素。

六：DFS（深度優先搜索）

深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。

深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。

深度優先遍歷圖演算法步驟：

1.訪問頂點v；

2.依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；

3.若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。

上述描述可能比較抽象，舉個實例：

DFS在訪問圖中某一起始頂點v後，由v出發，訪問它的任一鄰接頂點w1；再從w1出發，訪問與w1鄰接但還沒有訪問過的頂點w2；然後再從w2出發，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。

接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。

七：BFS(廣度優先搜索)

廣度優先搜索演算法（Breadth-First-Search），是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。

BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。

1.首先將根節點放入隊列中。

2.從隊列中取出第一個節點，並檢驗它是否為目標。

如果找到目標，則結束搜尋並回傳結果。

否則將它所有尚未檢驗過的直接子節點加入隊列中。

3.若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。

4.重復步驟2。

八：Dijkstra演算法

戴克斯特拉演算法（Dijkstra』salgorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

該演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E表示G中所有邊的集合，而邊的權重則由權重函數w:E→[0,∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。

1.初始時令S=,T=，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∞

2.從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3.對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

九：動態規劃演算法

動態規劃（Dynamicprogramming）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。

關於動態規劃最經典的問題當屬背包問題。

1.最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動態規劃演算法解決問題提供了重要線索。

2.子問題重疊性質。子問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。

十：樸素貝葉斯分類演算法

樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單概率分類演算法。貝葉斯分類的基礎是概率推理，就是在各種條件的存在不確定，僅知其出現概率的情況下，如何完成推理和決策任務。概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。

樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換言樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。

盡管是帶著這些樸素思想和過於簡單化的假設，但樸素貝葉斯分類器在很多復雜的現實情形中仍能夠取得相當好的效果。

通過掌握以上演算法，能夠幫你迅速提高編程能力，成為一名優秀的程序員。

⑼ 用一組｛14，15，30，28，5，10｝關鍵字序列，寫出初始建堆過程圖示，再根據初始堆寫出堆排序過程圖示。

起始序列為14，15，30，28，5，10，

(1)因此起始堆的情況如下：
14
15 30
28 5 10

(2)假設是打算得到一個從小到大的c，所以需要建大頂堆，起始狀態從下向上建堆：
第一步： 第二步：
14 30
28 30 28 14
25 5 10 25 5 10

(3)此時已經建立完了初始的堆。此時堆頂元素30即為最大元素，將堆頂元素與堆最後
一個元素進行交換，此時30是最大元素位於隊尾，因此無需繼續排序。所以堆如下圖
所示：10 28 14 25 5

(4)此時由於除被交換到堆頂的10以外其他的都基本有序，所以自上而下建堆得到的堆
如下：
28
25 14
10 5

(5)重復（3）和（4）步驟確定了28的位置並得到堆如下：
25
10 14
5

(6)重復（3）和（4）步驟確定了25的位置並得到堆如下：
14
10 5

(7)重復（3）和（4）步驟確定了14的位置並得到堆如下：
10
5

(8)重復（3）和（4）步驟確定了10的位置,此時只有一個數5也位於了堆的第一個位置，
因此排序完成。

(9)程序員堆排序演算法擴展閱讀：

建堆效率

n個結點的堆，高度d =log2n。根為第0層，則第i層結點個數為2^i，考慮一個元素在堆中向下移動的距離。大約一半的結點深度為d-1，不移動（葉）。四分之一的結點深度為d-2，而它們至多能向下移動一層。樹中每向上一層，結點的數目為前一層的一半，而子樹高度加一。

這種演算法時間代價為Ο（n)

由於堆有log n層深，插入結點、刪除普通元素和刪除最小元素的平均時間代價和時間復雜度都是

Ο（log n）。

操作實現

在程序中，堆用於動態分配和釋放程序所使用的對象。在以下情況中調用堆操作：

1.事先不知道程序所需對象的數量和大小。

2.對象太大，不適合使用堆棧分配器。

堆使用運行期間分配給代碼和堆棧以外的部分內存。

傳統上，操作系統和運行時庫隨附了堆實現。當進程開始時，操作系統創建稱為進程堆的默認堆。如果沒有使用其他堆，則使用進程堆分配塊。

語言運行時庫也可在一個進程內創建單獨的堆。（例如，C 運行時庫創建自己的堆。）除這些專用堆外，應用程序或許多載入的動態鏈接庫 (DLL) 之一也可以創建並使用單獨的堆。Win32 提供了一組豐富的API用於創建和使用專用堆。有關堆函數的優秀教程，請參閱 MSDN 平台 SDK 節點。

⑽ （c語言）利用堆排序演算法：實現數組下標為1到n的數的由小到大的輸出。求各種幫助

#include<stdio.h>
void main()
{
int a[100];
int i,j,m;
int temp;
printf("請問想輸入多少個數字:\n%d");
scanf("%d",&m);
printf("\n");
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<m;i++)
for(j=i+1;j<m;j++)
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
for(i=0;i<m;i++)
printf("%d\n",a[i]);
}