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;