php歸並排序

Ⅰ 3. 用任意一種編程語言（C/C++/Java/C#/VB.NET）寫出任意一種你所知的排序演算法（比如：冒泡排序， 歸並排

#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int a[], const int first, const int last);//冒泡排序
void InsertSort(int a[], const int first, const int last);//插入排序
void SelectSort(int a[], const int first, const int last);//選擇排序
void MergeSort(int a[], const int p, const int r);//合並排序
void QuickSort(int a[],const int p,const int r);//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t);//希爾排序
void HeapSort(int a[],const int p, int r); //堆排序
void StoogeSort(int a[],const int p,const int r);//Stooge排序(不用)演算法復雜度沒算清楚

void main()
{
//插入排序演算法
int a[11] = {6,4,5,3,2,1};
int dlta[]={9,5,3,2,1};
//BubbleSort(a,0,5);
//InsertSort(a,0,5);
//SelectSort(a,0,5);
//MergeSort(a,0,5);
//QuickSort(a,0,5);
//ShellSort(a,0,5,dlta,5);
HeapSort(a,0,5);
//StoogeSort(a,0,5);

for(int i=0; i<=5;i++)
{
printf("%d ",a[i]);
}

}

/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//實現對數組a[]中a[first]到a[last]升序的「冒泡」排序
int i,j,temp;
for(i=first; i<=last; i++)
{
for(j=first; j< last-i; j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//實現對數組a[]中a[first]到a[last]升序的「插入」排序
//最壞情況為n的平方，，多用於小數組
int i,j,temp;
for(i=first+1; i<=last; i++)
{
temp = a[i];
j = i - 1;
while((j >= 0) && (a[j] > temp))
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}

/************************選擇排序***********************/
void SelectSort(int a[], int first, int last)
{
//實現對數組a[]中a[first]到a[last]升序的「選擇」排序
int i, j, temp, num;
for(i=first; i<last; i++)
{
num = i;
for(j=i+1; j<=last; j++)
{
if(a[j] < a[num])
{
num = j;
}
}
if(i != num)
{
temp = a[num];
a[num] = a[i];
a[i] = temp;
}
}
}

/************************合並排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合並排序演算法中的實現合並的子程序
int iLLength,iRLength;
int *L, *R, i, j, k;
iLLength = q - p + 1;
iRLength = r - q;
L = (int *)malloc(iLLength*sizeof(int)); //或者 C++中 new int[iLLength];
R = (int *)malloc(iRLength*sizeof(int)); //或者 C++中 new int[iRLength];
if(L == 0 || R== 0)
{
printf("內存分配失敗！！！");
return;
}
for(i=0; i<iLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; j<iRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k<=r; k++)
{
if((i<iLLength) && (j<iRLength) && (L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(j<iRLength)
{
a[k] = R[j];
j++;
}
}

free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合並排序演算法-主程序
//n*lg(n),系數較小
int q;
if(p<r)
{
q = (p+r)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}
}

/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge演算法
int temp, k;
if(a[p]>a[r])
{
temp = a[p];
a[p] = a[r];
a[r] = temp;
}
if((p+1) >= r)
{
return;
}
k = (r-p+1)/3;
StoogeSort(a,p,r-k);
StoogeSort(a,p+k,r);
StoogeSort(a,p,r-k);
}

/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(關鍵)分治過程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; j<r; j++)
{
if(a[j] <= x)
{
i = i + 1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序演算法-主程序
//與下面的「尾遞歸實現方法」比較，缺點：右邊數組的遞歸不是必須的，增加了運行堆棧深度和調用開銷
int q;
if(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序演算法-主程序
//「尾遞歸實現方法」是對上面的快速排序主程序實現的一種優化
//系數較小,常用大數組
int q;
while(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
p = q + 1;
}
}

/************************希爾排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希爾排序演算法的關鍵子程序-插入排序子程序
int i, j, temp;
for(i=p+dk; i<=r; i++)
{
if(a[i] < a[i-dk])
{
temp = a[i];
for(j=i-dk; ((j>=0) && (temp < a[j])); j -= dk)
{
a[j+dk] = a[j];
}
a[j+dk] = temp;
}
}
}

void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希爾排序演算法-主程序
//按增量序列dlta[]中的前t個增量，實現對數組a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最後一個值必須是1
//增量序列中的值沒有除1以外的因子， 其精確時間復雜度：數學上尚未解決的難題
int k;
for(k=0; k<t; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}

/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其來實現「優先順序隊列」
int Parent(int i)
{
return ((i+1)/2-1);
}

int Right(int i)
{
return (2*(i+1)-1);
}

int Left(int i)
{
return (2*(i+1));
}

void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp;
l = Left(i);
r = Right(i);
largest = ((l<=hplast) && (a[l]>a[i])) ? l:i;
if((r<=hplast) && (a[r]>a[largest]))
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(a,hplast,largest);
}

}

void Build_Max_Heap(int a[],const int p, const int r)
{
int i;
for(i = (p+r)/2; i>=p; i--)
{
Max_Heapify(a,r,i);
}
}

void HeapSort(int a[],const int p, int r)
{
int i,temp;
Build_Max_Heap(a,p,r);
for(i = r; i > p; i--)
{
temp = a[p];
a[p] = a[i];
a[i] = temp;
r -= 1;
Max_Heapify(a,r,0);
}
}

Ⅱ 運維工程師筆試題

網易網路運維工程師筆試題目
類型：Windows開發 | 試題：55道試題
Question 1. (單選)

或者當你的孩子變壞時你嚴厲地懲罰他，或者他長大後將成為罪犯。你的孩子已經學壞了，因此，你必須嚴厲地懲罰他。 除了哪項，以下諸項都能構成對上述論證的一個疑難？

1. 什麼是你所說的「學壞」的確切含義？

2. 你的第一個前提是否過於簡單化了？

3. 你的第二個前提的斷定有什麼事實根據？

4. 你的孩子是怎麼學壞的？

Question 2. (單選)

針對作弊屢禁不止的現象，某學院某班承諾，只要全班同學都在承諾書上簽字，那麼，假如全班有一人作弊，全班同學的考試成績都以不及格計。校方接受並實施了該班的這一承諾。結果班上還是有人作弊，但班長的考試成績是優秀。 以下哪項是從上述斷定邏輯地得出的結論？

1. 全班有人沒在承諾書上簽字

2. 全班沒有人在承諾書上簽字

3. 全班多數人沒有作弊

4. 作弊的就是班長本人

Question 3. (單選)

甲城賣出的報紙比乙城多。因此、甲城的居民比乙城的居民更了解天下大事。 以下各句假如為真，都能削弱上述結論，除了：

1. 甲城發行僅限於本地新聞報道的周報

2. 甲城報攤出售的報紙的平均價格低於乙城

3. 甲城人口比乙城多

4. 乙城的很多居民在甲城工作，所以就在甲城購買報紙

Question 4. (單選)

雄性園丁鳥構築裝飾精美的巢。同一種類的不同園丁烏群建築的巢具有不同的建築和裝飾風格。根據這一事實，研究人員認為園丁鳥的建築風格是一種後天習得的，而不是先天遺傳的特性。」 以下哪項假如為真，則最有助於加強研究者的結論？

1. 通過對園丁鳥的廣泛研究發現，它們的築巢風格中的共性多於差異

2. 年輕的雄性園丁鳥在開始築巢時是很笨拙的，很顯然是花了許多年來觀察年長者的巢才成為行家能手的

3. 園丁鳥只在新幾內亞和澳州被發現，很顯然，兩地之間的園丁鳥沒什麼聯系

4. 眾所周知，一些會唱歌的鳥的演唱語調是後天習得的，而不是先天遺傳的

Question 5. (單選)

在過去的20年中，美國黑人議員的數量增加了將近100％，而白人議員的數量則略有下降，這說明，在美國的權力機構中，黑人很快就可和白人擁有相等的政治權力。

以下哪項假如是真的，最有力地削弱了上述論證？

1. 20年來，美國議員的總額保持基本不變。

2. 20年前，白人議員的數量是黑人議員數量的近8倍。

3. 20年來，黑人中的議員競選者增加了將近200％，而白人中議員競選者的數量則基本不變。

4. 20年來，黑人參加政治競選。仍然受到各種非凡的限制。

Question 6. (單選)

人們一直認為治理者的決策都是逐步推理，而不是憑直覺。但是最近一項研究表明，高層治理者比中、基層治理者更多地使用直覺決策，這就證實了直覺其實比精心的、有條理的推理更有效。

以上結論是建立在以下哪項假設基礎之上的？

1. 有條理的、逐步的推理對於許多日常治理決策是不適用的

2. 高層治理者制定決策時，有能力憑直覺決策或者有條理、逐步分析推理決策

3. 高層治理者的決策比中、基層治理者的決策更有效

4. 高層治理者在多數情況下採用直覺決策

Question 7. (單選)

當被催眠者被告知自己是聾子後，再問他們能否聽見催眠者說話時，他們回答「聽不到」。一些學者試圖解釋這一現象，認為被催眠者的「自我」被分裂為各個零散的部分，聾了的那一部分和回答的那一部分是相互分裂的。

以下哪項質疑最能削弱以上解釋？

1. 為什麼回答的那一部分不答「能聽到」呢？

2. 為什麼觀察到的事實都必須有個特定的解釋呢？

3. 為什麼所有被催眠者在上述情況下都做出同樣的反應呢？

4. 為什麼所有被催眠者的自我的分裂部分都是一樣的呢？

Question 8. (單選)

去年電話機的銷售額大幅度上升。為了利用這一形勢，某電話公司預備擴大本公司型號的電話機生產量，同時繼續從事已經家喻戶曉的廣告宣傳工作。

以下哪項假如為真，則最有可能使得該公司採用以上計劃時不能增加銷售額？

1. 雖然去年生產的產品全部售出，但該公司的市場佔有率是下降的。

2. 該公司預備發運給零售商的電話機的庫存數去年有稍微下降。

3. 該公司的電話機是去年銷售額增加的三種品牌之一。

4. 盡管零售價格有所上升，該公司的銷售額去年是下降的。

Question 9. (單選)

有人向某市政府提議應該在所有新建的房屋內安裝一種起火時會自動激發的灑水器。但是一位房地產開發商認為，既然90％的房屋著火都是被家庭成員撲滅的，所以安裝室內自動灑水器對滅火意義不大。

以下哪項假如為真，則最能削弱房地產開發商的觀點？

1. 大多數人都沒有經過滅火技能的正規練習。

2. 住宅著火導致的大部分財產損失是因為起火時家人都不在場。

3. 在住宅內安裝煙霧探測器比安裝灑水器要便宜得多。

4. 該市消防隊奔赴火場的時間要比全國平均時間短。

Question 10. (單選)

以下哪項最適合接在下段文字後面？

人們在購買一種名牌產品時，實際上是花錢買身份。他們希望通過購買名牌產品拉大旗作虎皮，抬高自己。所以，名牌產品的銷售不應採用薄利多銷的策略，因為：

1. 如今出手闊綽的購買者越來越少。

2. 保持銷售額*的是保持名牌產品「獨一無二」的魅力。

3. 名牌產品的購買者對產品的質量和價格同樣關心。

4. 擴大市場范圍有助於提高盈利。

Question 11. (單選)
為什麼不將N e t B I O S用於網際網路互連

1. 它是不可路由的

2. 它是不安全

3. 它是不可*的

4. a和b

Question 12. (單選)

計算機網路分為區域網、城域網與廣域網，其劃分的依據是：

1. 數據傳輸所使用的介質

2. 網路的作用范圍

3. 網路的控制方式

4. 網路的拓撲結構

Question 13. (單選)

用於保存計算機輸入輸出數據的材料及其製品稱為

1. 輸入輸出媒體

2. 輸入輸出通道

3. 輸入輸出介面

4. 輸入輸出埠

Question 14. (單選)

某二*樹結點的對稱序序列為A、B、C、D、E、F、G，後序序列為B、D、C、A、F、G、E。該二*樹結點的前序序列為

1. E、G、F、A、C、D、B

2. E、A、C、B、D、G、F

3. E、A、G、C、F、B、D

4. E、G、A、C、D、F、B

Question 15. (單選)

某二*樹結點的對稱序序列為A、B、C、D、E、F、G，後序序列為B、D、C、A、F、G、E。該二*樹對應的樹林結點的層次次序序列為

1. E、G、F、A、C、D、B

2. E、A、C、B、D、G、F

3. E、A、G、C、F、B、D

4. E、G、A、C、D、F、B

Question 16. (單選)

在虛擬頁式存儲治理方案中,下面哪一部分完成將頁面調入內存的工作?

1. 缺頁中斷處理

2. 頁面淘汰過程

3. 工作集模型應用

4. 緊縮技術利用

Question 17. (單選)

對於下列文件的物理結構，哪一個只能採用順序存取方式？

1. 順序文件

2. 鏈接文件

3. 索引文件

4. Hash文件

Question 18. (單選)

對一個排好序的線性表，用二分法檢索表中的元素，被檢索的表應當採用哪種存儲表示？

1. 順序存儲

2. 鏈接存儲

3. 散列法存儲

4. 存儲表示不受限制

Question 19. (單選)

以下哪一個不是棧的基本運算

1. 刪除棧頂元素

2. 刪除棧底元素

3. 判定棧是否為空

4. 將棧置為空棧

Question 20. (單選)

設二*樹根結點的層次為0，一棵深度(高度)為k的滿二*樹和同樣深度的完全二*樹各有f個結點和c個結點，下列關系式不正確的是：

1. f>＝c

2. c>f

3. f=2k 1-1

4. C>2k-1

Question 21. (多選)

Windows socket編程中經常需要進行位元組序列的轉換，下列哪幾個函數是將網路位元組序列轉換為主機位元組序列

1. htons

2. ntohs

3. htonl

4. ntohl

5. WSAntohs

Question 22. (單選)

下面哪個協議運行在網路層

1. HTTP

2. SMTP

3. UDP

4. IP

Question 23. (多選)

DNS用於完成地址查找,是經常使用的網路服務，從OSI網路模型來看，下面哪些服務與其不在同一層上

1. HTTPS

2. TCP

3. SMTP

4. PING

5. TELNET

Question 24. (單選)

SMTP的主要功能是什麼

1. 提供有關網路設備的治理信息

2. 在路由器介面層監控安全邊界

3. 在主機間傳輸郵件

4. 提供埠利用信息

Question 25. (單選)

Internet網路層使用的四個重要協議是

1. IP、ICMP、ARP、UDP

2. IP、ICMP、ARP、RARP

3. TCP、UDP、ARP、RARP

Question 26. (多選)

以下關於動態規劃法的描述哪些是正確的

1. 將問題分解成多級或許多子問題，然後順序求解子問題。

2. 可以確保得到最佳解

3. 前一個子問題的解為後一個子問題的求解提供有用的信息。

4. 從問題某一初始或推測值出發，一步步的攀登給定目標。

5. 盡可能快的去逼近更好的解，當達到某一步不能繼續時終止。

Question 27. (多選)

演算法的特徵包括

1. 有窮性

2. 確定性

3. 輸入和輸出

4. 能行性或可行性

Question 28. (單選)

漢諾塔（Hanoi）問題中令h（n）為從A移動n個金片到C上所用的次數，則遞歸方程為

1. h（n）=2hn-1

2. h（n） = 2h（n-1） 1

3. h（n）=2^n-n*h-1

4. h（n）=2h*n-1

Question 29. (單選)

啟發式搜索一般是何種演算法的改進

1. 深度優先搜索

2. 廣度優先搜索

3. 動態規劃

4. 貪婪法

Question 30. (單選)

假設一棵二*樹的後序遍歷序列為 DGJHEBIFCA ，中序遍歷序列為 DBGEHJACIF ，則其前序遍歷序列為 ( ) 。

1. ABCDEFGHIJ

2. ABDEGHJCFI

3. ABDEGHJFIC

4. ABDEGJHCFI

Question 31. (單選)

完全二*樹共有700結點，該二*樹有多少個葉子結點：

1. 349

2. 350

3. 351

4. 352 5. 353

Question 32. (單選)

在下列排序方法中，空間復雜性為O(log2n)的方法為（ ）。

1. 直接選擇排序

2. 歸並排序

3. 堆排序

4. 快速排序

5. 冒泡排序 Question 33. (單選)

有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（????）

1. 5 4 3 6 1 2 2. 4 5 3 1 2 6

3. 4 3 5 2 1 6 4. 2 3 4 1 5 6

5. 3 4 6 5 2 1

Question 34. (單選)

散列函數有一個共同性質，即函數值應按（）取其值域的每一個值；

1. 最大概率

2. 最小概率

3. 同等概率

4. 平均概率

Question 35. (單選)

下面描述中正確的為：

1. 線性表的邏輯順序與物理順序總是一致的。

2. 線性表的順序存儲表示優於鏈式存儲表示。

3. 線性表若採用鏈式存儲表示時所有結點之間的存儲單元地址可連續可不連續。

4. 二維數組是其數組元素為線性表的線性表。

Question 36. (單選)

什麼情況下必須要並行開發（多分支開發）：

1. 同時開發多種功能

2. 同時開發多個版本

3. 多人同時開發

4. 多地域分布式開發

Question 37. (單選)
軟體測試類型按開發階段劃分是：

1. 需求測試、單元測試、集成測試、驗證測試

2. 單元測試、集成測試、確認測試、系統測試、驗收測試

3. 單元測試、集成測試、驗證測試、確認測試、驗收測試

4. 調試、單元測試、集成測試、用戶測試

Question 38. (單選)

可作為軟體測試結束標志的是：

1. 使用了特定的測試用例

2. 錯誤強度曲線下降到預定的水平

3. 查出了預定數目的錯誤

4. 按照測試計劃中所規定的時間進行了測試

Question 39. (多選)

測試設計員的職責有

1. 制定測試計劃

2. 設計測試用例

3. 設計測試過程、腳本

4. 評估測試活動

Question 40. (多選)

以下對樁（stub）函數的描述正確的是：

1. 在單元測試中調用其它模塊

2. 在單元測試中被其它模塊調用

3. 在自頂向下的集成過程中尤其有效

4. 在自底向上的集成過程中尤其有效

Question 41. (多選)

在一台2.4.x 內核的linux機器上，下列命令用於檢查ipv4的tcp埠監聽情況，哪個是對的？

1. netstat -ant|grep LISTEN

2. netstat -an |grep LIST

3. netstat -at | grep LISTEN

4. netstat -a |grep tcp|grep -i listen

5. netstat -a |grep tcp |grep -i li

Question 42. (多選)

在RH Linux觀察系統負載狀況的常用命令有：

1. top

2. vmstat

3. iostat

4. netstat

Question 43. (單選)

一塊硬碟最多可以有（）個主分區？

1. 1

2. 2

3. 3

4. 4

5. 5 Question 44. (單選)

php是一門：

1. 編譯語言 2. 解釋語言 3. 腳本語言

Question 45. (單選)

某應用通過 TCP 協議從客戶端連接伺服器端，但是總連接不上，那麼netstat 輸出的對應此應用的行的狀態最有可能的是：

1. LISTEN 2. ESTABLISHED

3. TIME_WAIT 4. SYN_SEND

5. CLOSE_WAIT

Question 46. (單選)

進行DeviceIoControl時，假如驅動程序看到的輸入緩沖區的地址為0x500000,輸出緩沖區地址為0x600000,則此次DeviceIoControl的緩沖區傳輸機制為

1. METHOD_BUFFERED

2. METHOD_IN_DIRECT

3. METHOD_OUT_DIRECT

4. METHOD_NEITHER

Question 47. (單選)

IDispatch介面主要在什麼地方使用?

1. 用於支持OLE自動化,延時綁定對象的屬性和方法.

2. 用於支持Windows SDK開發

3. 方便在IE和腳本語言里使用COM對象

4. 用於支持鏈接點

Question 48. (多選)

下面4句對Windows API TerminateProcess函數的描述，請問其中有幾句是對的

1. 任何線程都可以調用此函數來終止自己或另一個進程的運行

2. 只要調用過了此函數，則指定要退出的進程已經退出。

3. 只有當無法使用另一種方法來迫使進程退出時，才考慮使用此函數。

4. 用此函數退出進程，進程沒有機會將自己的數據存入硬碟，也無法釋放佔用的內存。

Question 49. (單選)

大量API中都需要一個SECURITY_ATTRIBUTES參數，多數情況下都傳NULL，請問NULL是什麼意思？如：HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, … … );

1. 用最低安全許可權創建對象

2. 用最高安全許可權創建對象

3. 用注冊表中設定的預設安全許可權創建對象

4. 用創建對象的用戶的預設安全屬性創建對象

Question 50. (單選)

調用CoCreateinstance函數創建COM對象時，函數內部首先要獲得以下哪個介面，才能實現COM對象的創建

1. IUnknown

2. IClassFactory

3. IDispatch

4. 以上三個都需要

Question 51. (單選)

Window98內核使用的字元集是

1. ANSI

2. UNICODE

3. ANSI和UNICODE

4. 以上都不對

Question 52. (單選)

使用Windows API 函數CreateFile可以打開的對象，下列哪項說法最准確？

1. 文件和目錄

2. 通信設備

3. 磁碟設備

4. 以上都可以打開

Question 53. (多選)

關於以下的代碼，哪些說法是錯的？ HWND hWnd = CreateWindow("#32770", pszName, WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, _hInstance, NULL); ShowWindow(hWnd, SW_HIDE);

1. 假如pszName 是NULL，則CreateWindow返回NULL

2. 假如 _hInstance參數是NULL，則CreateWindow一定返回NULL

3. 假如不調用ShowWindow並傳遞SW_HIDE，則該窗口將顯示在屏幕上

4. 在2000/XP下調用CreateWindow函數一定失敗，必須調用CreateWindowEx函數

Question 54. (單選)

當一個進程結束運行之後,下列說法正確的是

1. 所有資源都會被釋放

2. 未釋放的系統GDI資源不會被釋放

3. 多進程共享數據不會被釋放,如:內存映射文件.

4. 在堆中分配的內存不會釋放.

Question 55. (單選)

在Windows中，下列關於堆和棧的說法中錯誤的是

1. 堆都是動態分配的，沒有靜態分配的堆;棧有靜態分配和動態分配2種分配方式。

2. 堆的生長方向是向下的，即向著內存地址減小的方向增長；棧的生長方向是向上的，即向著內存地址增加的方向增長。

3. 對堆的頻繁new/delete會造成內存空間的不連續，從而造成大量的碎片;棧則不會存在這個問題

4. 棧是由編譯器自動治理；堆的釋放工作由程序員控制，輕易產生內存泄露。

這是第一輪的考試題。

Ⅲ 選擇排序法復雜度

穩定性比較
插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的。
選擇排序、希爾排序、快速排序、堆排序是不穩定的。

時間復雜性比較
插入排序、冒泡排序最優為O(n),最壞為O(n^2),平均O(n^2）；
快速排序最優為O(nlogn),最壞為O(n^2),平均O(nlogn);
堆排序最優為O(nlogn),最壞為O(nlogn),平均O(nlogn);
線形排序的時間復雜性為O(n)。

輔助空間的比較
線形排序、歸並排序的輔助空間為O(n),快速排序的輔助空間為O(logn),其它排序的輔助空間為O(1)。

其它比較
插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。
反而在這種情況下，快速排序反而慢了。當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。
若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許時用桶排序。
當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下宜用歸並排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。

演算法描述太長了。
binary seach 二分查找啊。

6 層排序 乘3加1 Shell Sort Times 3 plus 1

7 層排序 乘4 Shell Sort Times 4
層排序？ 看名字是 希爾排序吧。

還有上面的名字也翻譯錯了。。。
這些演算法都很容易搜到的。

給你個網址吧：

http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

不過是用PASCAL語言描述的，部分C++語言描述。

// 直接插入排序
void insertionSort( int *array )
{
int i, j;
int key;

for( i = 1; i < size; ++i )
{
key = array[i];
j = i - 1;
while( j >= 0 && array[j] > key )
{
array[j+1] = array[j];
--j;
}
array[j+1] = key;
}
}

// 折半插入排序
void binary_insertiont_sort( int *array )
{
for( int i = 1; i < size; ++i )
{
int key = array[i];
int low = 0;
int high = i - 1;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else
low = mid + 1;
}
for( int j = i - 1; j > high + 1; --j )
array[j+1] = array[j];
array[j] = key;
}
}

// 選擇排序
void selectSort( int *array )
{
int i, j, k;

for( i = 0; i < size - 1; ++i )
{
k = i;
for( j = i + 1; j < size; ++j )
if( array[k] > array[j] )
k = j;
if( k != i )
{
j = array[k];
array[k] = array[i];
array[i] = j;
}
}
}

// 二分查找法
void binarySeach( int *array, int key )
{
int low = 0;
int high = n - 1; // n是array的長度
int flag = 0;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else if( array[mid] < key )
low = mid + 1;
else
{
printf( "%d\n", mid+1 );
flag = 1;
break;
}
}
if( !flag )
printf( "NOFOUND!\n" );
}

其他的還沒寫。。

Ⅳ php 歸並排序，，對於兩次遞歸調用自身有點不理解，求大神指教，不太明白執行過程

可以考慮把變數名修改一下
$l => $start
$m => $mid
$r => $end
這樣的話兩次調用其實也就是把整個數組先拆分成兩部分，然後這兩部分各自做排序，之後再合並
遞歸處理，如果對代碼邏輯不能直接理解的話，可以考慮從實際數據著手來理解
比如假設數組中只有一個數，程序會怎樣執行，假設數組中只有兩個數，程序會怎樣執行。。。

Ⅳ 能不能幫我做一個常用排序演算法的設計呢 跪求啊 幫幫忙吧 我對這個一竅不通啊

常用的排序有：
1.直接插入排序
2.希爾排序（最小增量排序）
3.簡單選擇排序
4.堆排序
5.冒泡排序
6.快速排序
7.歸並排序
8.基數排序

Ⅵ 歸並排序的示例代碼

歸並排序原理
歸並排序具體工作原理如下（假設序列共有n個元素）：
將序列每相鄰兩個數字進行歸並操作（merge)，形成floor(n/2)個序列，排序後每個序列包含兩個元素
將上述序列再次歸並，形成floor(n/4)個序列，每個序列包含四個元素
重復步驟2，直到所有元素排序完畢
示例代碼
Go語言 funcmergeSort(r[]int)[]int{length:=len(r)iflength<=1{returnr}num:=length/2left:=mergeSort(r[:num])right:=mergeSort(r[num:])returnmerge(left,right)}funcmerge(left,right[]int)(result[]int){l,r:=0,0forl<len(left)&&r<len(right){ifleft[l]<right[r]{result=append(result,left[l])l++}else{result=append(result,right[r])r++}}result=append(result,left[l:]...)result=append(result,right[r:]...)return}Java語言 packagealgorithm;publicclassMergeSort{//privatestaticlongsum=0;/***<pre>*二路歸並*原理：將兩個有序表合並和一個有序表*</pre>**@parama*@params*第一個有序表的起始下標*@paramm*第二個有序表的起始下標*@paramt*第二個有序表的結束小標**/privatestaticvoidmerge(int[]a,ints,intm,intt){int[]tmp=newint[t-s+1];inti=s,j=m,k=0;while(i<m&&j<=t){if(a[i]<=a[j]){tmp[k]=a[i];k++;i++;}else{tmp[k]=a[j];j++;k++;}}while(i<m){tmp[k]=a[i];i++;k++;}while(j<=t){tmp[k]=a[j];j++;k++;}System.array(tmp,0,a,s,tmp.length);}/****@parama*@params*@paramlen*每次歸並的有序集合的長度*/publicstaticvoidmergeSort(int[]a,ints,intlen){intsize=a.length;intmid=size/(len<<1);intc=size&((len<<1)-1);//-------歸並到只剩一個有序集合的時候結束演算法-------//if(mid==0)return;//------進行一趟歸並排序-------//for(inti=0;i<mid;++i){s=i*2*len;merge(a,s,s+len,(len<<1)+s-1);}//-------將剩下的數和倒數一個有序集合歸並-------//if(c!=0)merge(a,size-c-2*len,size-c,size-1);//-------遞歸執行下一趟歸並排序------//mergeSort(a,0,2*len);}publicstaticvoidmain(String[]args){int[]a=newint[]{4,3,6,1,2,5};mergeSort(a,0,1);for(inti=0;i<a.length;++i){System.out.print(a[i]+);}}}Python語言 defMergeSort(lists):iflen(lists)<=1:returnlistsnum=int(len(lists)/2)left=MergeSort(lists[:num])right=MergeSort(lists[num:])returnMerge(left,right)defMerge(left,right):r,l=0,0result=[]whilel<len(left)andr<len(right):ifleft[l]<right[r]:result.append(left[l])l+=1else:result.append(right[r])r+=1result+=right[r:]result+=left[l:]returnresultprintMergeSort([1,2,3,4,5,6,7,90,21,23,45])C語言 #include<stdlib.h>#include<stdio.h>voidMerge(intsourceArr[],inttempArr[],intstartIndex,intmidIndex,intendIndex){inti=startIndex,j=midIndex+1,k=startIndex;while(i!=midIndex+1&&j!=endIndex+1){if(sourceArr[i]>=sourceArr[j])tempArr[k++]=sourceArr[j++];elsetempArr[k++]=sourceArr[i++];}while(i!=midIndex+1)tempArr[k++]=sourceArr[i++];while(j!=endIndex+1)tempArr[k++]=sourceArr[j++];for(i=startIndex;i<=endIndex;i++)sourceArr[i]=tempArr[i];}//內部使用遞歸voidMergeSort(intsourceArr[],inttempArr[],intstartIndex,intendIndex){intmidIndex;if(startIndex<endIndex){midIndex=(startIndex+endIndex)/2;MergeSort(sourceArr,tempArr,startIndex,midIndex);MergeSort(sourceArr,tempArr,midIndex+1,endIndex);Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);}}intmain(intargc,char*argv[]){inta[8]={50,10,20,30,70,40,80,60};inti,b[8];MergeSort(a,b,0,7);for(i=0;i<8;i++)printf(%d,a[i]);printf( );return0;}PHP語言 //merge函數將指定的兩個有序數組(arr1arr2,)合並並且排序//我們可以找到第三個數組,然後依次從兩個數組的開始取數據哪個數據小就先取哪個的,然後刪除掉剛剛取過///的數據functional_merge($arrA,$arrB){$arrC=array();while(count($arrA)&&count($arrB)){//這里不斷的判斷哪個值小,就將小的值給到arrC,但是到最後肯定要剩下幾個值,//不是剩下arrA裡面的就是剩下arrB裡面的而且這幾個有序的值,肯定比arrC裡面所有的值都大所以使用$arrC[]=$arrA['0']<$arrB['0']?array_shift($arrA):array_shift($arrB);}returnarray_merge($arrC,$arrA,$arrB);}//歸並排序主程序functional_merge_sort($arr){$len=count($arr);if($len<=1)return$arr;//遞歸結束條件,到達這步的時候,數組就只剩下一個元素了,也就是分離了數組$mid=intval($len/2);//取數組中間$left_arr=array_slice($arr,0,$mid);//拆分數組0-mid這部分給左邊left_arr$right_arr=array_slice($arr,$mid);//拆分數組mid-末尾這部分給右邊right_arr$left_arr=al_merge_sort($left_arr);//左邊拆分完後開始遞歸合並往上走$right_arr=al_merge_sort($right_arr);//右邊拆分完畢開始遞歸往上走$arr=al_merge($left_arr,$right_arr);//合並兩個數組,繼續遞歸return$arr;}$arr=array(12,5,4,7,8,3,4,2,6,4,9);print_r(al_merge_sort($arr));Pascal語言 programmergesort_1;constmaxn=7;typearr=array[1..maxn]ofinteger;vara,b,c:arr;i:integer;proceremerge(r:arr;l,m,n:integer;varr2:arr);vari,j,k,p:integer;begini:=l;j:=m+1;k:=l-1;while(i<=m)and(j<=n)dobegink:=k+1;ifr[i]<=r[j]thenbeginr2[k]:=r[i];i:=i+1endelsebeginr2[k]:=r[j];j:=j+1;endend;ifi<=mthenforp:=itomdobegink:=k+1;r2[k]:=r[p];end;ifj<=nthenforp:=jtondobegink:=k+1;r2[k]:=r[p];end;end;proceremergesort(varr,r1:arr;s,t:integer);vark:integer;c:arr;beginifs=tthenr1[s]:=r[s]elsebegink:=(s+t)div2;mergesort(r,c,s,k);mergesort(r,c,k+1,t);merge(c,s,k,t,r1)end;end;beginwrite('Enterdata:');fori:=1tomaxndoread(a[i]);mergesort(a,b,1,maxn);fori:=1tomaxndowrite(b[i]:9);writeln;end.//============================================programmergesort_2;constmax=100000;vara,r:array[1..max]oflongint;n,i:longint;proceremsort(s,t:longint);varm,i,j,k:longint;beginifs=tthenexit;m:=(s+t)div2;msort(s,m);msort(m+1,t);i:=s;j:=m+1;k:=s;while(i<=m)and(j<=t)dobeginifa[i]<a[j]thenbeginr[k]:=a[i];inc(i);inc(k);endelsebeginr[k]:=a[j];inc(j);inc(k);end;end;whilei<=mdobeginr[k]:=a[i];inc(i);inc(k);end;whilej<=tdobeginr[k]:=a[j];inc(j);inc(k);end;fori:=stotdoa[i]:=r[i];end;beginreadln(n);fori:=1tondoread(a[i]);msort(1,n);fori:=1tondowriteln(a[i]);end.Basic語言 SubMergeSort(Array()AsInteger,FirstAsInteger,LastAsInteger)DimmidAsInteger=0Iffirst<lastThenmid=(first+last)2MergeSort(Array,first,mid);MergeSort(Array,mid+1,last);Merge(Array,first,mid,last);EndIfEndSub/*以下示例代碼實現了歸並操作。array[]是元素序列，其中從索引p開始到q位置，按照升序排列，同時，從(q+1)到r也已經按照升序排列，merge()函數將把這兩個已經排序好的子序列合並成一個排序序列。結果放到array中。*//***0<=p<=q<r,subarrayarray[p..q]andarray[q+1..r]arealreadysorted.*themerge()functionmergesthetwosub-arraysintoonesortedarray.*/voidMerge(intarray[],intp,intq,intr){inti,k;intbegin1,end1,begin2,end2;int*temp=(int*)malloc((r-p+1)*sizeof(int));begin1=p;end1=q;begin2=q+1;end2=r;k=0;while((begin1<=end1)&&(begin2<=end2)){if(array[begin1]<=array[begin2]){temp[k]=array[begin1];begin1++;}else{temp[k]=array[begin2];begin2++;}k++;}while(begin1<=end1||begin2<=end2){if(begin1<=end1){temp[k++]=array[begin1++];}if(begin2<=end2){temp[k++]=array[begin2++];}}for(i=0;i<=(r-p);i++)array[p+i]=temp[i];free(temp);}JavaScript語言
使用遞歸的代碼如下。優點是描述演算法過程思路清晰，缺點是使用遞歸，mergeSort()函數頻繁地自我調用。長度為n的數組最終會調用mergeSort()函數 2n-1次，這意味著一個長度超過1500的數組會在Firefox上發生棧溢出錯誤。可以考慮使用迭代來實現同樣的功能。 functionmerge(left,right){varresult=[];while(left.length>0&&right.length>0){if(left[0]<right[0]){/*shift()方法用於把數組的第一個元素從其中刪除，並返回第一個元素的值。*/result.push(left.shift());}else{result.push(right.shift());}}returnresult.concat(left).concat(right);}functionmergeSort(items){if(items.length==1){returnitems;}varmiddle=Math.floor(items.length/2),left=items.slice(0,middle),right=items.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}非遞歸演算法（C++） #include<iostream>#include<ctime>#include<cstring>#include<cstdlib>usingnamespacestd;/**將a開頭的長為length的數組和b開頭長為right的數組合並n為數組長度，用於最後一組*/voidMerge(int*data,inta,intb,intlength,intn){intright;if(b+length-1>=n-1)right=n-b;elseright=length;int*temp=newint[length+right];inti=0,j=0;while(i<=length-1&&j<=right-1){if(data[a+i]<=data[b+j]){temp[i+j]=data[a+i];i++;}else{temp[i+j]=data[b+j];j++;}}if(j==right){//a中還有元素，且全都比b中的大,a[i]還未使用memcpy(temp+i+j,data+a+i,(length-i)*sizeof(int));}elseif(i==length){memcpy(temp+i+j,data+b+j,(right-j)*sizeof(int));}memcpy(data+a,temp,(right+length)*sizeof(int));delete[]temp;}voidMergeSort(int*data,intn){intstep=1;while(step<n){for(inti=0;i<=n-step-1;i+=2*step)Merge(data,i,i+step,step,n);//將i和i+step這兩個有序序列進行合並//序列長度為step//當i以後的長度小於或者等於step時，退出step*=2;//在按某一步長歸並序列之後，步長加倍}}intmain(){intn;cin>>n;int*data=newint[n];if(!data)exit(1);intk=n;while(k--){cin>>data[n-k-1];}clock_ts=clock();MergeSort(data,n);clock_te=clock();k=n;while(k--){cout<<data[n-k-1]<<'';}cout<<endl;cout<<thealgorithmused<<e-s<<miliseconds.<<endl;deletedata;return0;}二路歸並
ConstFI='in.txt';FO='out.txt';MaxN=10000;TypeTIndex=Longint;TDat=Array[0..MaxN]OfTIndex;VarN:TIndex;Dat:TDat;Tmp:TDat;ProcereMerge(L,Mid,R:TIndex);VarP1,P2:TIndex;E1,E2:TIndex;P:TIndex;I:TIndex;BeginP1:=L;P2:=Mid+1;P:=L;RepeatIf(Dat[P1]<=Dat[P2])ThenBeginTmp[P]:=Dat[P1];Inc(P1);Inc(P);EndElseBeginTmp[P]:=Dat[P2];Inc(P2);Inc(P);End;Until(P1=Mid+1)Or(P2=R+1);If(P1=Mid+1)ThenBeginE1:=P2;E2:=R;EndElseBeginE1:=P1;E2:=Mid;End;ForI:=E1ToE2DoBeginTmp[P]:=Dat[I];Inc(P);End;End;ProcereSort(L,R:TIndex);VarMid:TIndex=0;BeginMid:=(L+R)Shr1;If(L<Mid)ThenSort(L,Mid);If(Mid+1<R)ThenSort(Mid+1,R);Merge(L,Mid,R);ForMid:=LToRDoDat[Mid]:=Tmp[Mid];End;ProcereInit;VarI:TIndex;BeginFillChar(Dat,SizeOf(Dat),0);Readln(N);ForI:=1ToNDoRead(Dat[I]);End;ProcereMain;BeginSort(1,N);End;ProcereFinal;VarI:TIndex;BeginForI:=1ToNDoWrite(Dat[I],'');Writeln;End;BeginAssign(Input,FI);Assign(Output,FO);Reset(Input);Rewrite(Output);Init;Main;Final;Close(Input);Close(Output);End.
Delphi歸並排序完整源代碼例子： //合並子函數procereTForm1.MergePass(vardatas:arrayofInteger;left,mid,right:Integer);vartmpArr:arrayofInteger;arrLen:Integer;i,k:Integer;begin1,begin2,end1,end2:Integer;beginarrLen:=right-left+1;SetLength(tmpArr,arrLen);begin1:=left;end1:=mid;begin2:=mid+1;end2:=right;k:=0;while((begin1<=end1)and(begin2<=end2))dobeginif(datas[begin1]<datas[begin2])thenbegintmpArr[k]:=datas[begin1];Inc(begin1);endelsebegintmpArr[k]:=datas[begin2];Inc(begin2);end;inc(k);end;while(begin1<=end1)dobegintmpArr[k]:=datas[begin1];Inc(begin1);Inc(k);end;while(begin2<=end2)dobegintmpArr[k]:=datas[begin2];Inc(begin2);Inc(k);end;fori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i];end;end;//排序主函數，left是數組左下標，0開始。right是數組右下標。procereTForm1.MergeSort(vardatas:arrayofInteger;left,right:Integer);varmid:Integer;i:Integer;beginmid:=0;if(left<right)thenbeginmid:=(right+left)div2;showLog('中間索引：'+inttostr(mid));MergeSort(datas,left,mid);MergeSort(datas,mid+1,right);MergePass(datas,left,mid,right);showLog('--->'+getArrayString(datas));//顯示數組中間狀態end;end;//調用方法：procereTForm1.btn1Click(Sender:TObject);varinArr:array[0..9]ofInteger;beginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);showLog('輸入數據：'+getArrayString(inArr));MergeSort(inArr,0,High(inArr));showLog('輸出數據：'+getArrayString(inArr));end;