归并排序:265 301127 751 863 937 694 742 301 438
记数排序:301 127937 438 742 751 76 265 863 694 以100为基距大小
二复杂度
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 1、时间复杂度 （1）时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 （2）时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n))为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 介绍
选择排序是说，每次从数列中找出一个最小的数放到最前面来，再从剩下的n-1个数中选择一个最小的，不断做下去。
插入排序是，每次从数列中取一个还没有取出过的数，并按照大小关系插入到已经取出的数中使得已经取出的数仍然有序。
冒泡排序分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的大小并在前面的那个数比紧接它后的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作.事实上，在第一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二
次只需要对前面n-1个数排序，这又将把这n-1个数中最大的数放到整个数列 的倒数第二个位置。这样下
去，冒泡排序第i趟结束后后面i个数都已经到位了，第i+1趟实际上只考虑前n-i个数.
我们来算一下最坏情况下三种算法各需要多少次比较和赋值操作。
选择排序在第i次选择时赋值和比较都需要n-i次（在n-i+1个数中选一个出来作为当前最小值，其余n-i个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n(n-1)/2次比较与n(n-1)/2+n次赋值。
插入排序在第i次寻找插入位置时需要最多i-1次比较（从后往前找到第一个比待插入的数小的数，最坏情况发生在这个数是所有已经取出的数中最小的一个的时候），在已有数列中给新的数腾出位置需要i-1次赋值操作来实现，还需要两次赋值借助临时变量把新取出的数搬进搬出。也就是说，最坏情况下比较需要n(n -1)/2次，赋值需要n(n-1)/2+2n次。
冒泡排序第i趟排序需要比较n-i次，n-1趟排序总共比较n(n-1)/2次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现，因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。
按照渐进复杂度理论，忽略所有的常数，三种排序的最坏情况下复杂度都是一样的O(n^2)。但实际应用中三种排序的效率并不相同。实践证明，插入排序是最快的，因为每一次插入时寻找插入的位置多数情况只需要与已有数的一部分进行比较。你或许会说冒泡排序也可以在半路上完成，还没有跑到第n-1趟就已经有序。但冒泡排序的交换操作更费时，而插入排序中找到了插入的位置后移动操作只需要用赋值就能完成（你可能知道这还能用move）。
但大家想过吗，这只是最坏情况下的。在很多时候，复杂度没有这么大，因为插入和冒泡在数列已经比较有序的情况下需要的操作远远低于n^2次（最好情况下甚至是线性的）。抛开选择排序不说（因为它的复杂度是“死”的，对于选择排序没有什么 “好”的情况），我们下面探讨插入排序和冒泡排序在特定数据和平均情况下的复杂度。
你会发现，如果把插入排序中的移动赋值操作看作是把当前取出的元素与前面取出的且比它大的数逐一交换，那插入排序和冒泡排序对数据的变动其实都是相邻元素的交换操作。下面我们说明，若只能对数列中相邻的数进行交换操作，如何计算使得n个数变得有序最少需要的交换次数。
我们定义逆序对的概念。假设我们要把数列从小到大排序，一个逆序对是指的在原数列中，左边的某个数比右边的大。也就是说，如果找到了某个i和j使得 i
若给出的n个数中有m个逆序对，插入排序的时间复杂度可以说是O(m+n)的，而冒泡排序不能这么说，因为冒泡排序有很多“无用”的比较（比较后没有交换），这些无用的比较超过了O(m+n)个。从这个意义上说，插入排序仍然更为优秀，因为冒泡排序的复杂度要受到它跑的趟数的制约。一个典型的例子是这样的数列：8, 2, 3, 4, 5, 6, 7, 1。在这样的输入数据下插入排序的优势非常明显，冒泡排序只能哭着喊上天不公。
然而，我们并不想计算排序算法对于某个特定数据的效率。我们真正关心的是，对于所有可能出现的数据，算法的平均复杂度是多少。不
用激动了，平均复杂度并不会低于平方。下面证明，两种算法的平均复杂度仍然是O(n^2)的。
我们仅仅证明算法需要的交换次数平均为O(n^2)就足够了。前面已经说过，它们需要的交换次数与逆序对的个数相同。我们将证明，n个
数的数列中逆序对个数平均O(n^2)个。
计算的方法是十分巧妙的。如果把给出的数列反过来（从后往前倒过来写），你会发现原来的逆序对现在变成顺序的了，而原来所有的非
逆序对现在都成逆序了。正 反两个数列的逆序对个数加起来正好就是数列所有数对的个数，它等于n(n-1)/2。于是，平均每个数列有n(n-1)/4
个逆序对。忽略常数，逆序对平 均个数O(n^2)。
上面的讨论启示我们，要想搞出一个复杂度低于平方级别的排序算法，我们需要想办法能把离得老远的两个数进行操作。
人们想啊想啊想啊，怎么都想不出怎样才能搞出复杂度低于平方的算法。后来，英雄出现了，Donald Shell发明了一种新的算法，我们将
证明它的复杂度最坏情况下也没有O(n^2) （似乎有人不喜欢研究正确性和复杂度的证明，我会用实例告诉大家，这些证明是非常有意思的）。
他把这种算法叫做Shell增量排序算法（大家常说的希尔排 序）。
Shell排序算法依赖一种称之为“排序增量”的数列，不同的增量将导致不同的效率。假如我们对20个数进行排序，使用的增量为1,3,7
。那么，我们首先对这20个数进行“7-排序”(7-sortedness)。所谓7-排序，就是按照位置除以7的余数分组进行排序。具体地 说，我们将把
在1、8、15三个位置上的数进行排序，将第2、9、16个数进行排序，依此类推。这样，对于任意一个数字k，单看A(k),A(k+7), A(k+14), …
这些数是有序的。7-排序后，我们接着又进行一趟3-排序（别忘了我们使用的排序增量为1,3,7）。最后进行1-排序（即普通的排序）后整个
Shell算法完成。看看我们的例子： 1 8 15
37 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 <-- 原数列
33 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2 <-- 7-排序后
00 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9 <-- 3-排序后
00 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 <-- 1-排序后（完成）
在每一趟、每一组的排序中我们总是使用插入排序。仔细观察上面的例子你会发现是什么导致了Shell排序的高效。对，每一趟排序将使
得数列部分有序，从而使得以后的插入排序很快找到插入位置。我们下面将紧紧围绕这一点来证明Shell排序算法的时间复杂度上界。
只要排序增量的第一个数是1，Shell排序算法就是正确的。但是不同的增量将导致不同的时间复杂度。我们上面例子中的增量(1, 3, 7,
15, 31, …, 2^k-1)是使用最广泛的增量序列之一，可以证明使用这个增量的时间复杂度为O(n√n)。这个证明很简单，大家可以参看一些其它
的资料，我们今天不证 明它。今天我们证明，使用增量1, 2, 3, 4, 6, 8, 9,12, 16, …, 2^p*3^q，时间复杂度为O(n*(log n)^2)。
很显然，任何一个大于1的正整数都可以表示为2x+3y，其中x和y是非负整数。于是，如果一个数列已经是2-排序的且是3 -排序的，那么
对于此时数列中的每一个数A(i)，它的左边比它大的只有可能是A(i-1)。A2绝对不可能比A12大，因为10可以表示为两个2和两个 3的和，则
A2
量中的2-排序也是O(n)，因为在2-排序之前，这个数列已经是4-排序且6-排序过的，只看数列的奇数项
或者 偶数项（即单看每一组）的话就又
成了刚才的样子。这个增量序列巧妙就巧妙在，如果我们要进行h-排序，那么它一定是2h-排序过且3h-排序过，于是处理 每个数A(i)的插入时
就只需要和A(i-h)进行比较。这个结论对于最开始几次（h值较大时）的h-排序同样成立，当2h、3h大于n时，按照定义，我 们也可以认为数列
是2h-排序和3h-排序的，这并不影响上述结论的正确性（你也可以认为h太大以致于排序时每一组里的数字不超过3个，属于常数级）。现 在，
这个增量中的每一趟排序都是O(n)的，我们只需要数一下一共跑了多少趟。也就是说，我们现在只需要知道小于n的数中有多少个数具有
2^p*3^q的形式。要想2^p*3^q不超过n，p的取值最多O(log n)个，q的取值最多也是O(log n)个，两两组合的话共有O(logn*logn)种情况。于
是，这样的增量排序需要跑O((logn)^2)趟，每一趟的复杂度O(n)，总的复杂度为O(n*(log n)^2)。早就说过了，证明时间复杂度其实很有意 思。
我们自然会想，有没有能使复杂度降到O(nlogn)甚至更低的增量序列。很遗憾，现在没有任何迹象表明存在O(nlogn)的增量排序。但事实
上，很多时候Shell排序的实际效率超过了O(nlogn)的排序算法。
对于O(nlogn)的排序算法，我们详细介绍归并排序并证明归并排序的时间复杂度，然后简单介绍堆排序，之后给出快速排 序的基本思想和复杂
度证明。最后我们将证明，O(nlogn)在理论上已经达到了最优。为了保持系列文章的完整性，我还是花时间写了一下。
首先考虑一个简单的问题：如何在线性的时间内将两个有序队列合并为一个有序队列（并输出）？
A队列：1 3 5 7 9