排序不等式

排序不等式（通用6篇）

篇1：排序不等式

2013年高中数学IB模块选修4-5专题测试

（一）试题内容：柯西不等式与排序不等式 试卷总分：120分考试时间：60分钟

一、选择题（共8小题，每题5分，共40分）

1、a,b,c,dR，不等式ab



2

c2d2acbd取等号的条件是（）



2A．abdc0B．adbc0C．adbc0D．acbd0

2、设a1a2a3,b1b2b3，下列最小的是（）

A．a1b3a2b2a3b1B．a1b1a2b2a3b3C．a1b2a2b1a3b3D．a1b1a2b3a3b23、若四个实数a1,a2,a3,a4满足a2a1a3a2a4a31，则a3a4a1a2的最大值为（）

A．1B

C．2D4、a,b是非零实数，ab1，x1,x2R,Max1bx2bx1ax2,Nx1x2，则M与N的大小关



222

系为（）

A．MNB．MNC．MND．MN5、若实数x,y满足(x5)(y12)14，则xy的最小值是（）

A．2B．1C

D6、x,y,zR，且x2y2z5，(x5)(y1)(z3)的最小值是（）

A．20B．25C．36D．477、已知a,b,c,dR，且满足abcd

625（）

A．25B．50C．

22222

2222



5D．625

28、已知0a,b,c1，且abc2，则abc的取值范围是（）

A．,B．,2C．,2D．,2

333

3二、填空题（共5小题，每题4分，共20分）

9、x,y

0,1

4444的最大值是

10、设x,y,R，那么xy

11、设

14

的最小值是xy

2，那么x1,x2,x3,xn0,a1,a2,a3,an0,x1x2x3x1taxaxn1122

a3x32anxn2的最小值是

12、设2x3y4z22,(x,y,z0)，则

三、解答题（共5小题，每题60分）

239

的最小值是，此时xyz.xyz

b4c4c4a4a4b413、（本小题10分）设a,b,cR，利用排序不等式证明：abc 

2a2b2c



33314、（本小题10分）设x1,x2,x3是不同的自然数，求s

15、（本小题10分）设nN,n

2，利用柯西不等式证明：

16、（本小题10分）求函数y

x1x2x

3的最小值。149

41111。

7n1n22n12nsinx3cosx的值域

sinx2cosx

117、（本小题20分）（2012浙江考试院样卷）题号：03“数学史与不等式选讲”模块

（1）设a，b，c为实数，求证：a＋b＋c≥ab＋bc＋ca；（2）若正实数a，b，c满足abc＝1，求

a4b(ac)



b4c(ab)



c4a(bc)的最小值．

2013年高中数学IB模块选修4-5专题测试

（一）┄┄┄⊙

中学班级姓名 学号考号答 题 卷

一、选择题（每小题4分，共40分）

16.（本小题共12分）

17.（本小题20分）

2013年高中数学IB模块选修4-5专题测试

（一）参 考 答 案

1.C2.A3.B4.A5.D6.C7.B8.C9.110.911.11

112.,2,2,3.11112a1a2a3an

13证明：不妨设0abc,则abc,111

，cba

a4b4c4a4b4c

4abc（逆序和）

abccaba4b4c4a4b4c4

abc（逆序和）

abcbca

b4c4c4a4a4b4

abc

2a2b2c

14解：不妨设1x12x23，由排序不等式，s15.证明：由柯西不等式得

x1x2x312311

。1491496

1111

2n1n2nnnn1n22n12n

11112n4n1n22n12n3n17

1111

n1n22n12n111

又：





1111

2222

2n1

2nn1n2

111

nn1n1n22n12n

16、原式可化为

ysinx2cosx1sinx3cosx 即y(y1)sinx(2x3)cosx

利用柯西不等式及sin2xcos21可得

y2(y1)sinx(2x3)cosxsin2xcos2xy12y3



2

即y2y12y3 化简得

2y27y50

5

所以函数值域为（-，1），

2

2217、“数学史与不等式选讲”模块

(1)证明1：因为a2＋b2≥2ab，b2＋c2≥2bc，c2＋a2≥2ca，三式相加并除以2得a2＋b2＋c2≥ab＋bc＋ca．

(1)证明2：因为a2＋b2＋c2－ab－bc－ca＝[(a－b)2＋(b－c)2＋(c－a)2]≥0，222

所以 a＋b＋c≥ab＋bc＋ca．…………5分

(2)解：由(1)及柯西不等式，均值不等式知

a4b(ac)



b4c(a



b)

≥

a(b)c2(abbcca)

c4(a2b2c2)2

≥

(a2＋b2＋c2)

a4b(ac)

32，当且仅当a＝b＝c＝1时等号成立，所以



b4c(ab)



c4a(bc)的最小值为

…………10分

篇2：排序不等式

柯西不等式和排序不等式的多种证明方法（课本延伸课题18）——2010.4 数学研究性学习撰写人 陈点

柯西不等式的一般式：

适用范围：证明不等式、解三角形、求函数最值、解方程等问题。接下来我将以几种较为主流的证明方法来证明： 求证：(∑ai^2)(∑bi^2)≥(∑ai〃bi)^2证法一（代数证明，运用二次函数，最主流证法）：

当a1=a2=…=an=0或b1=b2=…=bn=0时，一般形式显然成立 令A=∑ai^2 B=∑ai〃bi C=∑bi^2

当a1，a2，…，an中至少有一个不是零时，可知A＞0 构造二次函数f(x)=Ax^2＋2Bx＋C，f(x)＝∑(ai^2〃x^2＋2ai〃bi〃x＋bi^2)＝∑(ai〃x＋bi)^2≥0f(x)的判别式△＝4B^2－4AC≤0，移项得AC≥B^2，证毕。

证法二（其中几个特殊情况，为2与3时即向量公式）

n=1时，a1^2〃b1^2≥(a1b1)^2（这个…不解释）a1=a2=a3=…=an,b1=b2=b3=…=bn时同此证

n=2时，即为(a1^2+a2^2)(b1^2+b2^2)≥(a1b1+a2b2)^2

即(a1b1)^2+(a1b2)^2+(a2b1)^2+(a2b2)^2≥(a1b1)^2+(a2b2)^2+2a1b1a2b2 即(a1b2)^2+(a2b1)^2≥2a1b1a2b2

因为a2≥a1，b2≥b1，乱序和≥倒序和

故一定成立（呵呵，还一不小心把排序不等式引出来了）

证法三（这个是网上找的很权威的数学归纳法，因为我想出来的证法二是其铺垫，故引用说明。数学归纳法也是一种非常常见且正规的证明方法。）（1）当n1时左式=a1b1右式=a1b1 显然左式=右式

2当 n2时，右式 a12a2b12b22a1b1a2b2a22b12a12b22

⑴

⑵

a1b1a2b22a1a2b1b2a1b2a2b2右式

222

仅当即 a2b1a1b2 即

a1a2

时等号成立 b1b2

故n1,2时 不等式成立

（2）假设nkk,k2时，不等式成立

2kak即 a1b1a2b2akbka12a2b12b22bkk

当 bikai，k为常数，i1,2n 或a1a2ak0时等号成立

222

bk2 ak设a12a2b12b2

Ca1b1a2b2akbk

则ak21bk21bk21ak1bk1 22C22Cak1bk1ak1bk1Cak1bk1 2222222

akaka12a21b1b2bkbk1

a1b1a2b2akbkak1bk1

当 bikai，k为常数，i1,2n 或a1a2ak0时等号成立

即nk1时不等式成立

综合（1）（2）可知不等式成立

其实还有很多证明的方法，证明柯西不等式还可以利用比值法，归纳法，归纳法与综合法，归纳法与平均值不等式，排序不等式，参数平均值不等式，行列式，内积（向量）法，构造单调数列，凹凸函数法（来自奥数老师）……再者，拉格朗日恒等式也相当简单，在此不一一说明，可见证明此式方法之多。

柯西不等式是一个非常重要的不等式，灵活巧妙的应用运用它，可以使一些较为困难的问题迎刃而解，这个不等式结构和谐，应用灵活广泛，利用柯西不等式可处理以下问题： 1）证明相关命题 2）证明不等式 3）解三角形的相关问题 4）求最值

5）利用柯西不等式解方程

6）用柯西不等式解释样本线性相关系数（这个完全不理解，不过有这么一说）

排序不等式（又称）

简单来说，就是：反序和≤乱序和≤同序和

即a1b1a2b2anbna1c1a2c2ancna1bna2bn1anb1

⑶

其中，Cn为乱序数列。

证明：1.证乱序和小于正序和，以下证明中原式为乱序和

从第一个起，将a1b?与a?b1转变为a1b1与a?b?，设其为x，y，则有

a1b1+axby-a1bx+ayb1≧0（因为x，y≧1，根据等式的性质可得），然后

再往下，第二个a2bw与azb2…… 以此类推，到最后得出的式子为正序和，因为每步的过程均使原式减小或不变，故终式不小于原式2.证乱序和大于倒序和

从第一个起，将a1b?与a?bn转变为a1bn与a?b?, 设其为x，y，则有a1b1+axby-a1bx+ayb1≦0(因为x≧1,y≦n)故成立，基本上同理

排序不等式证明的关键在于有顺序的变化，每次变化使式子朝一个方向发展，这样就可轻易推出最终的结论。

应用：

1.排序不等式的基本应用。排序不等式在解决一些常见不等式时，具有简单直观的特点

2.证明不等式时两次或多次运用排序不等式，将结果相加，也是常见方法。3．经过适当变形后再运用排序不等式的问题，常见于一些比较难的习题或竞赛题

拓展：

排序不等式的另一种表述形式 设

a1a2an,b1b2bn

c,c,,cnb1,b2bn

为两组实数，12是的任一排

列，则三个矩阵

a1a2ana1a2ana1a2anbbbbbbccc

12n12nnn11A：B：C：

我们称A为顺序矩阵，B为乱序矩阵，C为反序矩阵 它们的列积和（同列相乘再相加）：

a1b1a2b2anbna1c1a2c2ancna1bna2bn1anb1

即：顺序和乱序和反序和

在此，我们没必要知道矩阵的更多知识，而只是利用它这种形式。因为它更直观，便于在解题中寻找数列

b1,b2,bn的一个我们需要的乱序，更易掌握和应用。

⑴柯西不等式的向量说法：|α||β|≥|α〃β|，α=(a1,a2,…,an)，β=(b1,b2,…,bn)（n∈N，n≥2）

等号成立条件：β为零向量，或α=λβ（λ∈R）。⑵数学归纳法（这里说的是第一数学归纳法）：

即一般地，证明一个与正整数n有关的命题，有如下步骤：1）证明当n取第一个值时命题成立；

2）假设当n=k（k≥n的第一个值，k为自然数）时命题成立，证明当n=k+1时命题也成立。

篇3：排序不等式

当且仅当a1=a2=…=an或b1=b2=…=bn时等号成立.

即 反序和≤乱序和≤顺序和.

探究发现, 可用排序不等式证明的对称不等式有以下几种常见的类型:

类型1已知a, b, c为正数, m, n∈N+, 利用排序不等式证明:

证明不妨设a≥b≥c, 则

由排序原理:顺序和≥乱序和得

类型2已知a, b, c为正数, m, n∈N+, 利用排序不等式证明:

注该类不等式证明需要两次利用排序原理.

类型4已知a, b, c为正数, m, n∈N+, 利用排序不等式证明:

证明不妨设a≥b≥c, 则

由排序原理:顺序和≥乱序和得

篇4：准确排序 语义连贯

高考语文卷常以排序题形式来考查语言的“连贯”，下面就以试题为例，看看如何解答排序题。

一、理顺关系，明确句间条理

一个语段内，句与句之间常常会存在时间顺序、空间顺序或者逻辑顺序，这种顺序不可随意更改。所以，读懂每句话表达的意思，理顺句子间的关系是正确排序的基础。

例1 语意连贯的语段，排序最恰当的一项是______

①使用语言，不仅要用得对，在语法上不出毛病，而且要力求用得好，要有艺术性，有感染力，这就要讲究运用语言的艺术，也就是要讲究一点修辞。

②有意用不符合语法常规的办法取得某种修辞效果是许可的，然而这只是偶一为之，并且要有些特定的条件。

③如果语言不符合语法，说都说不通，就没有什么好的修辞可言。

④语言是用来传递信息、交流思想、表达情感的。

⑤好的修辞，必然是符合语法规律的。

A. ④①⑤③②B. ④③⑤①②

C. ⑤②①④③D. ⑤③④①②

解析： 这五个句子的主要意思分别是：①使用语言要讲究修辞，②特定条件下的修辞，③不好的修辞，④语言的作用，⑤好的修辞。由此可见，这个语段的结构应该是“总分”形式，“总”是指“运用语言要讲究修辞”，“分”即分别论述不同种类的修辞。按照这样的逻辑关系以及上下句的衔接词语，可以判断五个句子的正确顺序为④①⑤③②，答案选A。

二、统揽全局，抓住中心论点

遇到议论性的语段，先抓住中心论点，再分析其他句子是如何围绕论点进行论述的，会使排序变得容易很多。

例2 把下列带序号的句子组合成语意连贯的一段话并填入横线处。（只填序号）

理学家为什么崇古抑律·______古体与律体之辨跟诗歌史联系起来，就是古体的典范——汉魏晋诗与律体的典范——唐诗之辨。

①那么，为什么讲求声律、对偶等形式技巧就是品格低呢·

②他们认为，诗歌的审美方面、形式技巧方面对于人的道德修养没有正面的价值。

③以这种价值观去看诗歌的题材样式，古体诗就高于律诗。

④既然诗歌的审美方面没有价值，本来可以不讲，但是如果要进入到诗歌领域去谈诗的话，那么，在形式方面人为的工巧因素越多，其价值就越低。

⑤抛开诗歌的内容不论，单从形式上看，近体诗要讲求声律、对偶等，这些讲求在理学家看来，是其在品格上低于古体诗的重要原因。

解析：语段开头抛出“理学家为什么崇古抑律”的问题，接下来的句子自然与之有因果联系，我们不难找到⑤，这就构成了语段的中心论点——“理学家崇古抑律，因为从形式上看，古体诗的品格高于律诗”。既然理学家有这样的观点，自然要论证“为什么讲求声律、对偶等形式使近体诗的品格低”，所以⑤后紧跟过渡句①，然后再回答①提出的问题。句子②从“对道德修养的价值”角度出发，说明诗歌的形式技巧价值低，句子④具体分析句子②的观点，句子③得出结论。可见，正确的排序是⑤①②④③。

三、读懂句意，分析陈述角度

在描述某一事物时，语段内前后句子的陈述角度应该一致，首尾相贯。所以，在读懂句意的基础上，可以分析句子的陈述角度，以此为依据进行排序。

例3 依次填入下面一段文字横线处的语句，衔接最恰当的一组是

今天的日子很短，正在自己的脚下悄悄地流逝。______ 。

______，______ 。______ ，______ ，______，经营好每一个今天就等于经营好昨天和明天。

①今天的事应该今天完成，不能推到明天

②脚踏实地，全身心地经营好今天，才会有一个个实在的昨天

③因此，面对今天，我们不要太多地怀念过去

④接力棒交得好，才能走向辉煌的明天

⑤如果总是站在今天望明天，结果明天也会悄悄地溜走

⑥今天是昨天和明天的接力处

A. ⑤①⑥②④③ B. ⑤⑥①④③②

C. ⑥④③②①⑤ D. ⑥②③①④⑤

解析：这是一个议论性语段。句子②⑥讲“今天”与“昨天”及“明天”的关系，句子①③④⑤讲如何处理好“今天”与“昨天”“明天”的关系。语段以“今天”为话题开头，能与之衔接的只能是以“今天”为主语的①或⑥，选项中没有以①开头的，所以可以把答案锁定在C、D之中。我们只需分析句子④②哪一个接在句子⑥后更合适即可。句子④以“接力棒”开头，显然承接了句子⑥最后提出的“接力处”这一概念，所以，应该选C。

四、分析语言，注意整体协调

整体协调指的是句式结构和音韵节奏的协调。句式上，应注意上下文之间整句与散句、长句与短句、主动句与被动句、肯定句与否定句等的对应；音韵上，要关注节奏与押韵。

例4 填入下列句子空白处最恰当的一项是

埋伏和照应需要惨淡经营。埋伏处要能轻轻一笔，若不经意，______。要使读者看不出斧凿痕迹，只觉得

______ ，如一丛花，如一棵菜。虽由人力，却似天成。如果看出来这里是埋伏，那里是照应，______ 。

①照应处要顺理成章，水到渠成

②照应处要水到渠成，顺理成章

③清清爽爽，简简单单

④自自然然，完完整整

⑤便成死症

⑥便太浅显

A. ①④⑤ B. ①③⑥

C. ②③⑤ D. ②④⑥

解析：本题从音韵和谐的角度分析，很容易选择A，因为不难看出句末“成”“整”“症”等字押韵。再结合文段验证一下，首先，从逻辑看，“水到渠成”是“顺理成章”的结果，句子①②中应选择①。其次，语段中把“看不出斧凿痕迹”给人的感觉比做“一丛花”“一棵菜”，意在“天然、自然”，因此，不难选择句子④“自自然然，完完整整”。所以A选项是正确的。

篇5：排序不等式

包括冒泡排序、并归排序、插入排序、选择排序、快速排序、堆排序、Shell排序 ——————sort_all.h文件—————————————————— #include using namespace std;/****************************************/ class sort_all { public: void swap_i(int &a, int &b;void disp_array(int *array, int len;void disp_num(;void sort_maopao(int *array, int len;void sort_quick(int *array, int start, int end;void sort_merge(int * array, int start, int end;void sort_heap(int *array, int len;void sort_select(int *array, int len;void sort_insert(int *array, int len;void sort_shell(int *array, int len;};——————————————————————————————————————

————————sort_real.cpp文件——————————————————————

#include “sort_all.h”

void sort_all::disp_array(int *array, int len { for(int i=0;i { cout << array[i] << “ ”;} cout << endl;} void sort_all::swap_i(int &a, int &b { int temp;temp = a;a = b;b = temp;} void sort_all::disp_num({ cout << “---冒泡排序，输入1---” << “n”;cout << “---并归排序，输入2---” << “n”;cout << “---插入排序，输入3---” << “n”;cout << “---选择排序，输入4---” << “n”;cout << “---快速排序，输入5---” << “n”;cout << “----堆排序，输入6----” << “n”;cout << “--Shell排序，输入7---” << “n”;cout << “-----结束，输入0-----” << “n”;

} /**************************************************/ /**************堆排序 ******************************/ /**************************************************/ void heap_adj(int *array, int i, int len { int nTemp;int nChild;for(nTemp = array[i];2*i+1 { nChild = 2*i+1;if(nChild nChild ++;if(nChild < len-1 && array[nChild]>nTemp array[i] = array[nChild];else break;array[nChild] = nTemp;} } void heap_create(int *array, int len { for(int i=len/2;i>=0;i--heap_adj(array,i, len;}

void sort_all::sort_heap(int *array, int len { heap_create(array, len;for(int i=len-1;i>0;i--{ swap_i(array[0], array[i];heap_adj(array, 0, i;} } /*******************************************************/ /******************插入排序*****************************/ /*******************************************************/ void sort_all::sort_insert(int *array, int len { int i,j;int temp;for(i=1;i { temp = array[i];for(j=i;j>0 && array[j-1] > temp;j--array[j] = array[j-1];array[j] = temp;} } /********************************************************/

/*************冒泡排序***********************************/ /********************************************************/ void sort_all::sort_maopao(int *array, int len { int i,j;for(i=0;i { for(j=len-1;j>=i;j--{ if(array[j] > array[j+1] swap_i(array[j],array[j+1];} } } /**********************************************/ /**************并归排序************************/ /**********************************************/ void merge(int * array, int start, int mid, int end { int len_A = midmid;int *A = new int[len_A];int *B = new int[len_B];int i,j;for(i=0;i

A[i] = array[i +start];for(i=0;i B[i] = array[i + mid+1];i=0;j=0;int temp;int k=start;while(i { if(A[i] > B[j] { temp = A[i];i++;} else { temp = B[j];j++;} array[k++] = temp;} while(i { array[k++] = A[i++];}

while(j { array[k++] = B[j++];} } void sort_all::sort_merge(int * array, int start, int end { if(start == end return;else { int mid =(start+end/2;sort_merge(array, start, mid;sort_merge(array, mid+1, end;merge(array, start, mid, end;} } /********************快速排序******************************/ /**********************************************************/ void sort_all::sort_quick(int *array, int start, int end { int key = array[start];int i = start;int j = end;if(i>=j

return;while(i { while(i j--;array[i] = array[j];while(i = array[i] i++;array[j] = array[i];} array[i] = key;sort_quick(array, start, i-1;sort_quick(array, i+1, end;} /****************************************************/ /****************选择排序****************************/ /****************************************************/ void sort_all::sort_select(int *array, int len { int i,j;int ntemp;int key;for(i=0;i { key = array[i];

ntemp = i;for(j=i+1;j { if(array[j] < key && array[ntemp] > array[j] ntemp = j;} swap_i(array[i], array[ntemp];} } /*****************************************/ /**************** Shell排序****************/ /*****************************************/ void sort_all::sort_shell(int *array, int len { int step = len;int i;while(step >1 { step =(step+1/2;for(i=0;i { if(array[i+step] < array[i] swap_i(array[i+step], array[i];} }

} ————————————————————————————————————————————————————sort_main.cpp文件————————————————— #include “sort_all.h” int main({ int input[] = {2,4,5,1,5,8,10,-2,4};int len = sizeof(input/sizeof(int;int N;sort_all instance;while(1 { instance.disp_num(;cout << “请输入: ”;cin >> N;if(N==0 break;cout << “-” << “n”;cout<< “原始数据：” << “n”;instance.disp_array(input, len;switch(N { case 1: instance.sort_maopao(input, len;cout << “冒泡排序结果：” << “n”;

break;case 2: instance.sort_merge(input, 0, len-1;cout << “并归排序结果：” << “n”;break;case 3: instance.sort_insert(input, len;cout << “插入排序结果：” << “n”;break;case 4: instance.sort_select(input, len;cout << “选择排序结果：” << “n”;break;case 5: instance.sort_quick(input, 0, len-1;cout << “快速排序结果：” << “n”;break;case 6: instance.sort_heap(input, len;cout << “堆排序结果：” << “n”;break;case 7: instance.sort_shell(input, len;cout << “Shell排序结果：” << “n”;default:

篇6：排序不等式

在IT届有一道百算不厌其烦的题，俗称排序，不管是你参加BAT等高端笔试，亦或是藏匿于街头小巷的草根笔试，都会经常见到这样一道百年难得一解的问题。

今天LZ有幸与各位分享一下算法届的草根明星，排序届的领衔大神——插入排序以及归并排序。最后，在头脑风暴下，LZ又有幸认识了一位新朋友，名叫并行归并排序。接下来，咱们就一一认识一下，并且在最后来一次“算林大会”吧。

插入排序简介

插入排序，算林称最亲民的排序算法，插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素，并且将每一个循环到的元素插入到相应的位置，从而实现排序的目的。

插入排序的代码展示

使用Java代码描述插入排序，可以用以下的代码。

package algorithm;

/**

* @author zuoxiaolong

*

*/

public abstract class InsertSort {

public static void sort(int[] numbers){

for (int i = 1; i < numbers.length; i++) {

int currentNumber = numbers[i];

int j = i - 1;

while (j >= 0 && numbers[j] > currentNumber) {

numbers[j + 1] = numbers[j];

j--;

}

numbers[j + 1] = currentNumber;

}

}

}

复制代码

这个算法从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。

插入排序理解起来比较简单，因此LZ就不过多的解释它的实现原理了，尚未理解的猿友可以自行研究。

插入排序的性能分析

接下来，咱们来简单分析一下插入排序的性能。首先，插入排序当中有两个循环，假设数组的大小为n，则第一个循环是n－1次，第二个while循环在最坏的情况下是1到n－1次。因此插入排序的时间复杂度大约为如下形式。

1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）

时间复杂度为输入规模的2次函数，可见插入排序的时间复杂度是比较高的。这是原理上的简单分析，最后在“算林大会”中，各位可以清楚的看到插入排序随着输入规模的增长，时间会指数倍的上升。

归并排序简介

归并排序，算林届的新秀，引领着分治法的潮流。归并排序将排序问题拆分，比如分成两个较小的数组，然后对拆分后的数组分别进行排序，最后再将排序后的较小数组进行合并。

这种思想是一种算法设计的思想，很多问题都可以采用这种方式解决。映射到编程领域，其实就是递归的思想。因此在归并排序的算法中，将会出现递归调用。

归并排序的代码展示

归并排序主要由两个方法组成，一个是用于合并两个已经排序的数组的方法，一个则是递归方法，用于将问题无限拆分。接下来咱们一起看看归并排序的Java代码展示，如下所示。

package algorithm;

/**

* @author zuoxiaolong

*

*/

public abstract class MergeSort {

public static void sort(int[] numbers){

sort(numbers, 0, numbers.length);

}

public static void sort(int[] numbers,int pos,int end){

if ((end - pos) > 1) {

int ffset = (end + pos) / 2;

sort(numbers, pos, offset);

sort(numbers, offset, end);

merge(numbers, pos, offset, end);

}

}

public static void merge(int[] numbers,int pos,int offset,int end){

int[] array1 = new int[offset - pos];

int[] array2 = new int[end - offset];

System.arraycopy(numbers, pos, array1, 0, array1.length);

System.arraycopy(numbers, offset, array2, 0, array2.length);

for (int i = pos,j=0,k=0; i < end ; i++) {

if (j == array1.length) {

System.arraycopy(array2, k, numbers, i, array2.length - k);

break;

}

if (k == array2.length) {

System.arraycopy(array1, j, numbers, i, array1.length - j);

break;

}

if (array1[j] <= array2[k]) {

numbers[i] = array1[j++];

} else {

numbers[i] = array2[k++];

}

}

}

}

可以看到，归并排序将一个长度为n的数组平均分为两个n/2的数组分别进行处理，因此，在sort方法中又调用了两次sort方法自身。当数组大小为1时，则认为该数组为已经为排好序的数组。因此在sort方法中，需要end与pos相差大于2时，才需要进一步拆分，这也是递归的终止条件。

此外，在代码中，使用了Java提供的arraycory函数进行数组复制，这种直接复制内存区域的方式，将会比循环赋值的方式速度更快。有些算法实现会给merge方法中的两个临时数组设置哨兵，目的是为了防止merge中for循环的前两个if判断。为了方便理解，LZ这里没有设置哨兵，当某一个数组的元素消耗完时，将直接使用arraycopy方法把另外一个数组copy到numbers当中。

归并排序的性能分析

与插入排序一样，咱们来简单分析一下归并排序的时间复杂度。咱们假设数组的大小为n，sort方法的时间复杂度为f（end－pos）。简单的分析merge方法的复杂度，不难发现为（end－pos）＊2，这个结果的前提是咱们认为arraycopy方法的复杂度为length参数。

基于以上的假设，由于end－pos的初始值为n，因此归并排序的复杂度大约为如下形式。

2＊f（n/2） ＋ 2＊n ＝ 2＊（2＊f（n/4）＋2＊（n/2）） ＋ 2＊n＝4＊f（n/4） ＋ 2＊n ＋ 2＊n ＝ n ＊f（1） ＋ 2＊n ＋...＋2＊n

其中f（1）的时间复杂度为常量，假设f（1）＝c，而2＊n将有log2n个。因此咱们得到归并排序的最终时间复杂度为如下形式。

cn ＋ 2n＊log2n ＝ O（n＊log2n）

归并排序的时间复杂度与插入排序相比，已经降低了很多，这一点在数组的输入规模较大时将会非常明显，因为log函数的增加速度将远远低于n的增加速度。

并行归并排序简介

并行归并排序是LZ在学习归并排序时意淫出来的，最近LZ正在研究Java的并发编程，恰好归并排序的子问题有一定的并行度与独立性，因此LZ版的并发归并排序就这样诞生了。事后，LZ也人肉过并行归并排序这个家伙，发现早已众所周知，不过在不知道的情况下自己能够想到是不是也应该窃喜一下呢。

并行归并排序与普通的归并排序没有多大区别，只是利用现在计算机多核的优势，在有可能的情况下，让两个或多个子问题的处理一起进行。这样一来，在效率上，并行归并排序将会比归并排序更胜一筹。

并行归并排序的代码展示

并行归并排序主要对sort方法进行了修改，基础的merge方法与普通的归并排序是一样的。因此在进行并行归并排序时，引用了归并排序的一些方法，具体的代码如下所示。

package algorithm;

import java.util.concurrent.CountDownLatch;

/**

* @author zuoxiaolong

*

*/

public abstract class MergeParallelSort {

private static final int maxAsynDepth = (int)(Math.log(Runtime.getRuntime.availableProcessors())/Math.log(2));

public static void sort(int[] numbers) {

sort(numbers, maxAsynDepth);

}

public static void sort(int[] numbers,Integer asynDepth) {

sortParallel(numbers, 0, numbers.length, asynDepth > maxAsynDepth ? maxAsynDepth : asynDepth, 1);

}

public static void sortParallel(final int[] numbers,final int pos,final int end,final int asynDepth,final int depth){

if ((end - pos) > 1) {

final CountDownLatch mergeSignal = new CountDownLatch(2);

final int ffset = (end + pos) / 2;

Thread thread1 = new SortThread(depth, asynDepth, numbers, mergeSignal, pos, offset);

Thread thread2 = new SortThread(depth, asynDepth, numbers, mergeSignal, offset, end);

thread1.start();

thread2.start();

try {

mergeSignal.await();

} catch (InterruptedException e) {}

MergeSort.merge(numbers, pos, offset, end);

}

}

static class SortThread extends Thread {

private int depth;

private int asynDepth;

private int[] numbers;

private CountDownLatch mergeSignal;

private int pos;

private int end;

/**

* @param depth

* @param asynDepth

* @param numbers

* @param mergeSignal

* @param pos

* @param end

*/

public SortThread(int depth, int asynDepth, int[] numbers, CountDownLatch mergeSignal, int pos, int end) {

super();

this.depth = depth;

this.asynDepth = asynDepth;

this.numbers = numbers;

this.mergeSignal = mergeSignal;

this.pos = pos;

this.end = end;

}

@Override

public void run() {

if (depth < asynDepth) {

sortParallel(numbers,pos,end,asynDepth,(depth + 1));

} else {

MergeSort.sort(numbers, pos, end);

}

mergeSignal.countDown();

}

}

}

在这段代码中，有几点是比较特殊的，LZ简单的说明一下，

1，分解后的问题采用了并行的方式处理，并且咱们设定了一个参数asynDepth去控制并行的深度，通常情况下，深度为(log2CPU核数)即可。

2，当子问题不进行并行处理时，并行归并排序调用了普通归并排序的方法，比如MergeSort.sort和MergeSort.merge。

3，因为合并操作依赖于两个子问题的完成，因此咱们设定了一个合并信号（mergeSignal），当信号发出时，才进行合并操作。

并行归并排序在原理上与普通的归并排序是一样的，只是对于子问题的处理采用了一定程度上的并行，因此如果猿友们理解归并排序，那么并行归并排序并不难理解。

并行归并排序的性能分析

并行归并排序只是将普通归并排序中一些可并行的操作进行了并行处理，因此在总体的时间复杂度上并没有质的变化，都是O（n＊log2n）。

由于并行归并排序将某些排序操作并行操作，因此在性能上一定是快于普通归并排序算法的。不过这也不是一定的，当数组规模太小时，并行带来的性能提高可能会小于线程创建和销毁的开销，此时并行归并排序的性能可能会低于普通归并排序。

算林大会

接下来，就是一周一度的算林大会了，本次算林大会主要由以上三种算法参加，胜者将会成为本周度最受欢迎算法。接下来是算林大会的代码，请各位猿友过目。

package algorithm;

import java.io.File;

import java.lang.reflect.Method;

import java.util.Random;

/**

* @author zuoxiaolong

*

*/

public class SortTests {

public static void main(String[] args) {

testAllSortIsCorrect();

testComputeTime(“MergeParallelSort”, 40000, 5);

testComputeTime(“MergeSort”, 40000, 5);

testComputeTime(“InsertSort”, 400, 5);

}

public static void testAllSortIsCorrect() {

File classpath = new File(SortTests.class.getResource(“”).getFile());

File[] classesFiles = classpath.listFiles();

for (int i = 0; i < classesFiles.length; i++) {

if (classesFiles[i].getName().endsWith(“Sort.class”)) {

System.out.println(“---测试” + classesFiles[i].getName() + “是否有效---”);

testSortIsCorrect(classesFiles[i].getName().split(“.”)[0]);

}

}

}

public static void testSortIsCorrect(String className){

for (int i = 1; i < 50; i++) {

int[] numbers = getRandomIntegerArray(1000 * i);

invoke(numbers, className);

for (int j = 1; j < numbers.length; j++) {

if (numbers[j] < numbers[j-1]) {

throw new RuntimeException(className + “ sort is error because ” + numbers[j] + “<” + numbers[j-1]);

}

}

}

System.out.println(“---” + className + “经测试有效---”);

}

public static void testComputeTime(String className,int initNumber,int times,Object... arguments) {

long[] timeArray = new long[times];

for (int i = initNumber,j = 0; j < times; i = i * 10,j++) {

timeArray[j] = computeTime(i, className, arguments);

}

System.out.print(className + “时间增加比例：”);

for (int i = 1; i < timeArray.length ; i++) {

System.out.print((float)timeArray[i]/timeArray[i - 1]);

if (i < timeArray.length - 1) {

System.out.print(“,”);

}

}

System.out.println();

}

public static long computeTime(int length,String className,Object... arguments){

int[] numbers = getRandomIntegerArray(length);

long start = System.currentTimeMillis();

System.out.print(“开始计算长度为”+numbers.length+“方法为”+className+“参数为[”);

for (int i = 0; i < arguments.length; i++) {

System.out.print(arguments[i]);

if (i < arguments.length - 1) {

System.out.print(“,”);

}

}

System.out.print(“]，时间为”);

invoke(numbers, className, arguments);

long time = System.currentTimeMillis()-start;

System.out.println(time + “ms”);

return time;

}

public static int[] getRandomIntegerArray(int length){

int[] numbers = new int[length];

for (int i = 0; i < numbers.length; i++) {

numbers[i] = new Random().nextInt(length);

}

return numbers;

}

public static void invoke(int[] numbers,String className,Object... arguments){

try {

Class

Class

parameterTypes[0] = int[].class;

for (int i = 0; i < arguments.length; i++) {

parameterTypes[i + 1] = arguments[i].getClass();

}

Method method = clazz.getDeclaredMethod(“sort”, parameterTypes);

Object[] parameters = new Object[parameterTypes.length];

parameters[0] = numbers;

for (int i = 0; i < arguments.length; i++) {

parameters[i + 1] = arguments[i];

}

method.invoke(null, parameters);

} catch (Exception e) {

throw new RuntimeException(e);

}

}

}

以上代码testAllSortIsCorrect方法首先验证了三种算法的正确性，也就是说经过sort方法后，数组是否已经升序排列。需要一提的是，由于插入排序的性能太低，因此插入排序测试的最大规模为400万，而归并排序测试的最大规模为4亿。

接下来，大家就一起看看运行结果吧。以下是在LZ的mac pro上的运行结果，硬件配置为16G内存，4核i7。这种配置下，异步深度（asynDepth）默认为log24=2。

---测试InsertSort.class是否有效---

---InsertSort经测试有效---

---测试MergeParallelSort.class是否有效---

---MergeParallelSort经测试有效---

---测试MergeSort.class是否有效---

---MergeSort经测试有效---

开始计算长度为40000方法为MergeParallelSort参数为[]，时间为6ms

开始计算长度为400000方法为MergeParallelSort参数为[]，时间为44ms

开始计算长度为4000000方法为MergeParallelSort参数为[]，时间为390ms

开始计算长度为40000000方法为MergeParallelSort参数为[]，时间为3872ms

开始计算长度为400000000方法为MergeParallelSort参数为[]，时间为47168ms

MergeParallelSort时间增加比例：7.3333335,8.863636,9.9282055,12.181818

开始计算长度为40000方法为MergeSort参数为[]，时间为7ms

开始计算长度为400000方法为MergeSort参数为[]，时间为81ms

开始计算长度为4000000方法为MergeSort参数为[]，时间为839ms

开始计算长度为40000000方法为MergeSort参数为[]，时间为9517ms

开始计算长度为400000000方法为MergeSort参数为[]，时间为104760ms

MergeSort时间增加比例：11.571428,10.358025,11.343266,11.00767

开始计算长度为400方法为InsertSort参数为[]，时间为0ms

开始计算长度为4000方法为InsertSort参数为[]，时间为3ms

开始计算长度为40000方法为InsertSort参数为[]，时间为245ms

开始计算长度为400000方法为InsertSort参数为[]，时间为23509ms

开始计算长度为4000000方法为InsertSort参数为[]，时间为3309180ms

InsertSort时间增加比例：Infinity,81.666664,95.9551,140.76227

复制代码

首先可以看到，三种算法都是运行正确的。接下来，咱们可以对比一下三种算法的性能。

根据输出结果，规模为400万时的区别是最明显与直观的。并行归并排序仅需要390ms就完成了400万规模的排序，而普通的归并排序则需要839ms才可以，至于插入排序，简直是不可理喻，竟然需要300多万ms，大约50分钟。

咱们再来看三者的时间增长趋势。两种归并排序基本上与规模的增长趋势相似，每当规模增加10倍时，时间也基本上增加10倍，而插入排序则几乎是以100倍的速度在增加，刚好是数组规模增长速度的平方。其中的Infinity是因为当数组规模为400时，毫秒级别的计时为0ms，因此当除数为0时，结果就为Infinity。