工信部网站备案查询系统,wordpress小工具代码,中小微企业税收政策,wordpress添加php页面前言 在这一章#xff0c;我们讨论数组元素的排序问题。为简单起见#xff0c;假设在我们的例子中数组只包含整数#xff0c;虽然更复杂的结构显然也是可能的。对于本章的大部分内容#xff0c;我们还假设整个排序工作能够在主存中完成#xff0c;因此#xff0c;元素的个…前言 在这一章我们讨论数组元素的排序问题。为简单起见假设在我们的例子中数组只包含整数虽然更复杂的结构显然也是可能的。对于本章的大部分内容我们还假设整个排序工作能够在主存中完成因此元素的个数相对来说比较小(小于)。当然不能在主存中完成而必须在磁盘或磁带上完成的排序也相当重要。这种类型的排序叫作外部排序(external sorting)将在本章末尾讨论外部排序。 我们对内部排序的考察将指出
存在几种容易的算法以排序如插入排序。有一种算法叫作希尔排序(Shellsort)它的编程非常简单以运行并在实践中很有效。有一些稍微复杂的的排序算法。任何通用的排序算法均需要次比较。 本章的其余部分将描述和分析各种排序算法。这些算法包含一些有趣的、重要的代码优化和算法设计思想。可以对排序做出精确的分析。预先说明在适当的时候我们将尽可能地多做一些分析。
7.1 预备知识 我们描述的算法都将是可以互换的。每个算法都将接收一个含有元素的数组和一个包 含元素个数的整数。 我们将假设是传递到排序例程中的元素个数它已经被检查过是合法的。按照C 的约定对于所有的排序数据都将在位置0处开始。 我们还假设“”和“”运算符存在它们可以用于对输入进行一致的排序。除赋 值运算符外这两种运算是仅有的允许对输入数据进行的操作。在这些条件下的排序叫作基于比较的排序(comparison-based sorting)。
7.2 插入排序
7.2.1 算法 最简单的排序算法之一是插入排序(insertion sort)。插入排序由趟(pass)排序组成。对于趟到趟插入排序保证从位置0到位置上的元素为已排序状态。插入排序利用了这样的事实位置0到位置上的元素是已排过序的。图7-1显示一个简单的数组在每一趟插入排序后的情况。 图7-1表达了一般的方法。在第趟我们将位置上的元素向左移动到它在前个元素中的正确位置上。图7-2中的程序实现该想法。第25行实现数据移动而没有明显使用交换。将位置上的元素存于Tmp中而(在位置之前)所有更大的元素都向右移动一个位置。然后将Tmp置于正确的位置上。这种方法与实现二叉堆时所用到的技巧相同。 void InsertionSort(ElementType A[], int N)
{int j, P;ElementType Tmp;for (P 1; P N; P){Tmp A[P];for (j P; j 0 A[j - 1] Tmp; j--)A[j] A[j - 1];A[j] Tmp;}
} 7.2.2 插入排序的分析 由于嵌套循环每趟花费N次迭代因此插入排序为而且这个界是精确的因为以反序输入可以达到该界。精确计算指出对于的每一个值第4行的测试最多执行次。对所有的求和得到总数为 另一方面如果输入数据已预先排序那么运行时间为因为内层for循环的检测总是立即判定不成立而终止。事实上如果输入几乎已排序(该术语将在下一节更严格地定义)那么插入排序将运行得很快。由于这种变化差别很大因此值得我们去分析该算法平均情形的行为。实际上和各种其他排序算法一样插入排序的平均情形也是详见下节的分析。
7.3 一些简单排序算法的下界 数字数组的一个逆序(inversion)是指数组中具有但的序偶()。在上节的例子中输入数据34864513221有9个逆序即(348)(3432)(3421)(6451)(6432)(6421)(5132)(5121)(3221)。这正好是需要由插入排序(非直接)执行的交换次数。情况总是这样因为交换两个不按原序排列的相邻元素恰好消除一个逆序而一个排过序的数组没有逆序。由于算法中还有项其他的工作因此插入排序的运行时间是其中为原始数组中的逆序数。于是若逆序数是则插入排序以线性时间运行。 我们可以通过计算排列中的平均逆序数而得出插入排序平均运行时间的精确的界。如往常一样定义平均是一个困难的命题。我们将假设不存在重复元素(如果允许重复那么我们甚至连重复的平均次数究竟是什么都不清楚)。利用该假设我们可设输入数据是前个整数的某个排列(因为只有相对顺序才是重要的)并设所有的排列都是等可能的。在这些假设下我们有如下定理 定理 7.1 个互异数的数组的平均逆序数是。 证明对于含有任意的数的表考虑其反序表。上例中的反序表是21325164834。考虑该表中任意两个数的序偶(xy)且yx。显然恰是和之中的一个该序偶表示一个逆序。在表和它的反序表中序偶的总个数为。因此平均表有该量的一半即个逆序。 这个定理意味着插入排序平均是二次的同时也提供了只交换相邻元素的任何算法的一个很强的下界。 定理 7.2 通过交换相邻元素进行排序的任何算法平均需要时间。 证明初始的平均逆序数 是而每次交换只减少一个逆序因此需要次交换。 这是证明下界的一个例子它不仅对非显式地实施相邻元素的交换的插入排序有效而且对诸如冒泡排序和选择排序等其他一些简单算法也是有效的不过这些算法将不在这里描述。事实上它对一整类只进行相邻元素的交换的排序算法(包括那些未被发现的算法)都是有效的。正因为如此这个证明在经验上是不能被认可的。虽然这个下界的证明非常简单但是一般说来证明下界要比证明上界复杂得多。 这个下界告诉我们为了使一个排序算法以亚二次(subquadratic)或时间运行必须执行一些比较特别要对相距较远的元素进行交换。一个排序算法通过删除逆序得以向前进行而为了有效地运行它必须每次交换删除不止一个逆序。
7.4 希尔排序 希尔排序(Shellsort)的名称源于它的发明者Donald Shell该算法是冲破二次时间屏障的第一批算法之一不过从它的发现之日起又过了若干年后才证明了它的亚二次时间界。正如上节所提到的它通过比较相距一定间隔的元素来工作各趟比较所用的距离随着算法的进行而减小直到只比较相邻元素的最后一趟排序为止。由于这个原因希尔排序有时也叫作缩小增量排序(diminishing increment sort)。 希尔排序使用一个序列叫作增量序列(increment sequence)。只要任何增量序列都是可行的不过有些增量序列比另外一些增量序列更好(后面我们将讨论这个问题)。在使用增量的一趟排序之后对于每一个我们有(这里它是有意义的)所有相隔的元素都被排序。此时称文件是-排序的(-sorted)。例如图7-3显示了各趟排序后数组的情况。希尔排序的一个重要性质(我们只叙述而不证明)是一个-排序的文件(此后将是-排序的)保持它的-排序性。事实上假如情况不是这样的话那么该算法也就没什么意义了因为前面各趟排序的结果会被后面各趟排序给打乱。 -排序的一般做法是对于中的每一个位置把其上的元素放到中间的正确位置上。虽然这并不影响最终结果但是仔细的考察指出一趟-排序的作用就是对个独立的子数组执行一次插入排序。当我们分析希尔排序的运行时间时这个考察结果将是很重要的。 增量序列的一种流行(但是不好)的选择是使用Shell建议的序列和。图7-4包含一个使用该序列实现希尔排序的程序。后面我们将看到存在一些递增的序列它们对该算法的运行时间做出了重要的改进即使是一个小的改变都可能剧烈地影响算法的性能。
void ShellSort(ElementType A[], int N)
{int i, j, Increment;ElementType Tmp;for (Increment N / 2; Increment 0; Increment / 2)for(i Increment; i N; i){Tmp A[i];for (j i; j Increment; j - Increment)if(Tmp A[j - Increment])A[j] A[j - Increment];elsebreak;A[j] Tmp;}
} 希尔排序的最坏情形分析 虽然希尔排序编程简单但是其运行时间的分析则完全是另外一回事。希尔排序的运行时间依赖于增量序列的选择而证明可能相当复杂。希尔排序的平均情形分析除最平凡的一些增量序列外是一个长期未解决的问题。我们将证明在两个特别的增量序列下最坏情形的精确的界。 定理 7.3 使用希尔增量时希尔排序的最坏情形运行时间为。 证明证明不仅需要指出最坏情形运行时间的上界而且还需要指出存在某个输入实际上就花费时间运行。首先通过构造一个坏情形来证明下界。我们先选择是2的幂。这使得除最后一个增量是1外所有的增量都是偶数。现在我们给出一个数组Input-Data作为输入它的偶数位置上有个同为最大的数而在奇数位置上有个同为最小的数(对该证明第一个位置是位置1)。由于除最后一个增量外所有的增量都是偶数因此当我们进行最后一趟排序前个最大的元素仍然处在偶数位置上而个最小的元素也还是在奇数位置上。于是在最后一趟排序开始之前第个最小的数()在位置上。将第个元素恢复到其正确位置需要在数组中移动个间隔。这样仅仅将个最小的元素放到正确的位置上就至少需要的工作。举一个例子图7-5显示一个时的坏(但不是最坏)的输入。在2-排序后的逆序数一直恰好保持为123456728因此最后一趟排序将花费相当多的时间。 现在我们证明上界以结束本证明。前面已经观察到带有增量的一趟排序由个关于个元素的插入排序组成。由于插入排序是二次的因此一趟排序总的开销是。对所有各趟排序求和则给出总的界为。因为这些增量形成一个几何级数其公比为2而该级数中的最大项是因此。于是我们得到总的界。 希尔增量的问题在于这些增量对未必互素因此较小的增量可能影响很小。Hibbard提出一个稍微不同的增量序列它在实践中(并且理论上)给出更好的结果。他的增量形如。虽然这些增量几乎是相同的但关键的区别是相邻的增量没有公因子。现在我们就来分析使用这个增量序列的希尔排序的最坏情形运行时间这个证明相当复杂。 定理 7.4 使用Hibbard增量的希尔排序的最坏情形运行时间为。 证明我们只证明上界而将下界的证明留作练习。这个证明需要堆垒数论(additivenumber theory)中某些众所周知的结果。本章末提供了这些结果的参考资料。 和前面一样对于上界我们还是计算每一趟排序的运行时间的界然后对各趟求和。对于那些的增量我们将使用前一定理得到的界。虽然这个界对于其他增量也是成立的但是它太大用不上。直观地看我们必须利用这个增量序列是特殊的这样一个事实。我们需要证明的是对于位置上的任意元素当要执行-排序时只有少数元素在位置的左边且大于。 当对输入数组进行-排序时我们知道它已经是-排序和-排序的了。在-排序以前考虑位置和上的两个元素其中。如果是或的倍数那么显然。不仅如此如果可以表示为和的线性组合(以非负整数的形式)那么也有。例如当我们进行3-排序时文件已经是7-排序和 15-排序的了。52可以表示为7和15的线性组合521×73×15。因此A[100]不可能大于A[152]因为。 现在因此和没有公因子。在这种情形下可以证明至少和一样大的所有整数都可以表示为和的线性组合(见本章末尾的参考文献)。 这就告诉我们第4行的for循环体对于这些位置上的每一个最多执行次。于是我们得到每趟的界。 利用大约一半的增量满足的事实并假设是偶数那么总的运行时间为 因为两个和都是几何级数并且所以上式简化为 使用Hibbard增量的希尔排序平均情形运行时间基于模拟的结果被认为是但是没有人能够证明该结果。Pratt已经证明的界适用于广泛的增量序列。 Sedgewick 提出了几种增量序列其最坏情形运行时间(也是可以达到的)为。对于这些增量序列的平均运行时间猜测为。经验研究指出在实践中这些序列的运行要比Hibbard的好得多其中最好的是序列(151941109...)该序列中的项或者是或者是。通过将这些值放到一个数组中可以最容易地实现该算法。虽然有可能存在某个增量序列使得能够对希尔排序的运行时间做出重大改进但是这个增量在实践中还是最为人们称道的。 关于希尔排序还有几个其他结果它们需要数论和组合数学中一些艰深的定理而且主要是在理论上有用。希尔排序是算法非常简单又具有极其复杂的分析的一个好例子。 希尔排序的性能在实践中是完全可以接受的即使是对于数以万计的仍是如此。编程的简单特点使得它成为对较大的输入数据经常选用的算法。
7.5 堆排序
7.6 归并排序
7.7 快速排序
7.7.1 选取枢纽元
7.7.2 分割策略
7.7.3 小数组
7.7.4 实际的快速排序例程
7.7.5 快速排序的分析
7.7.6 选择的线性期望时间算法
7.8 大型结构的排序
7.9 排序的一般下界
7.10 桶式排序
7.11 外部排序
7.11.1 为什么需要新的算法
7.11.2 外部排序模型
7.11.3 简单算法
7.11.4 多路合并
7.11.5 多相合并
7.11.6 替换选择
