《排序归并、快排、优先队列等》由会员分享，可在线阅读，更多相关《排序归并、快排、优先队列等（28页珍藏版）》请在金锄头文库上搜索。
1、精选公文范文排序归并、快排、优 先队列等各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢思想：首先，找到数组中最小的那 个元素。其次，将它和数组的第一个元 素交换位置。再次，在剩下的元素中找 到最小的元素，将它与数组的第二个元 素交换位置。如此往复，直到将整个数 组排序。【图例】图中，x轴方向为数组的索引，y轴 方向为待排序元素的值。选择排序有两个很鲜明的特点：运行时间和输入无关。为了找出最 小的元素而扫描一遍数组并不能为下一 遍扫描提供什么信息。这种性质在某些 情况下是缺点。数据移动是最少的。每次交换都会 改变两个数组元素的值，因此选择排序 用了 N次交换一一交换次数和数组的大 精选公
2、文范文i精选公文范文 小是线性关系。【对于长度为N的数组，选择排序 需要大约N2/2次比较和N次交换】 思想：它重复地走访过要排序的数 列，一次比较两个元素，如果他们的顺 序错误就把他们交换过来。走访数列的 工作是重复地进行直到没有再需要交 换，也就是说该数列已经排序完成。这 个算法的名字由来是因为越小的元素会 经由交换慢慢“浮”到数列的顶端。冒泡排序算法的运作如下：1、比较相邻的元素。如果第一个比 第二个大，就交换他们两个。2、对每一对相邻元素作同样的工 作，从开始第一对到结尾的最后一对。 在这一点，最后的元素应该会是最大的 数。3、针对所有的元素重复以上的步 骤，除了最后一个。4、持续每次
3、对越来越少的元素重复 上面的步骤，直到没有任何一对数字需 要比较。【图例】图中，x轴方向为数组的索引，y轴 方向为待排序元素的值。由图中可看出，冒泡排序是从后到 前，逐步有序的，最大的元素先沉到底 部，接着是次大的void%20BubbleSort(Comparable%20a) %20%20%20%20/exchanged 表示是否做 过交换处理，一趟冒泡没有做过交换处 理，即没有改变任何元素的位置，则停 止冒泡。%20%20%20%20bool%20exchanged %20=%20false%20;%20%20%20%20%2 0int%20N%20=%20;%20%20%20%20 %
4、20%20%20%20最多n-1趟冒泡排序 (若发现某趟排序没有交换操作，则停止 冒泡)20%20%20%20%20for%20(int%20i %20=%201;%20i%20%20a)%20%20%20 %20%20%20%20%20%20%20%20%20 %20%20%20%20%20%20%20%20%20 精选公文范文3精选公文范文%20%20%20%20%20%20%20exch(a,%2 0a)%20;%20%20%20%20 交换 a、 a%20%20%20%20%20%20%20%20%20 %20%20%20%20%20%20%20exchanged%20=%20true
5、%20;%20%20%20/ 标记有 元 素 交 换 位 置 20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2 0%20%20%20/for(j)%20%20%20%20 特点：冒泡排序是与插入排序拥有相等的 执行时间，但是两种法在需要的交换次 数却很大地不同。在最坏的情况，冒泡 排序需要0(n2)次交换，而插入排序只要 最多O(n)交换。冒泡排序的实现通常会 对已经排序好的数列拙劣地执行0(n2), 而插入排序在这个例子只需要O(n)个运 算。因此很多实现中避免使用冒泡排 序，而用插入排序取代之。冒泡排序如 果能在内部循环第一次执行时，
6、使用一精选公文范文 个旗标来表示有无需要交换的可能，也 有可能把最好的复杂度降低到O(n)。在 这个情况，在已经排序好的数列就无交 换的需要。思想:将第i个元素与其左边的已经 有序的元素一一比较，找到合适的位置， 插入其中。为了给要插入的元素腾出空 间，我们需要将其余所有元素在插入之 前都向右移动一位。具体算法描述如下：1、从第一个元素开始，该元素可以 认为已经被排序2、取出下一个元素，在已经排序的 元素序列中从后向前扫描3、如果该元素大于新元素，将该元 素移到下一位置4、重复步骤3,直到找到已排序的 元素小于或者等于新元素的位置5、将新元素插入到该位置后6、重复步骤25与选择排序一样，当前索
7、引左边的 所有元素都是有序的。但它们的最终位 精选公文范文5精选公文范文置还不确定，为了给更小的元素腾出空 间，它们可能会被移动。但是当索引到 达数组的右端时，数组排序就完成了。 插入排序不会访问索引右侧的元素，而 选择排序不会访问索引左侧的元素。和选择排序不同的是，插入排序所 需的时间取决于输入中元素的初始顺 序。对一个其中的元素已经有序(或接近 有序)的数组进行排序，将会比对随机顺 序的数组或是逆序数组进行排序要快得 多。【图例】使用插入排序为一列数字进行排序 的过程。从前到后逐步有序。void%20sort(Comparable%20a)%20%20 %20%20将 a 按升序排 列 2
8、0%20%20%20int%20N%20=%20;%20%20%20%20for%20(int%20i%20=% 201;%20i%20=1%20&%201ess(a,%20a);%20j-)%20%20%20%20%20%20%20%精选公文范文6精选公文范文20%20%20%20%20exch(a,%20j,%20j-1) %20;%20%20%20%20在索引i由左向右变化的过程中， 它左侧的元素总是有序的,所以当i到达 数组的右端时排序就完成了。改进：要大幅提高插入排序的速度 并不难，只需要在内循环中将较大的元 素都向右移动而不总是交换两个元素。【平均情况下插入排序需要N2/4 次比较
9、以及N2/4次交换。】【当倒置(两元素颠倒)的数量很少 时，插入排序很可能比其他任何排序算 法都要快！】【插入排序对于部分有序的数组十 分高效，也很适合小规模数组。它也是 高级排序算法的中间过程。】【插曲】Knuth高爷爷说：“尽管第一个二分 查找程序于1946年就已经公布了，但是 第一个没有bug的二分查找程序在1962 年才出现。”显然，我们上面的二分查找代码是 精选公文范文7有 bug 的。20至于二分查找，以后会再起一篇博 文详细讨论。希尔排序，也称递减增量排序算法, 是插入排序的一种更高效的改进版本。希尔排序是基于插入排序的以下两 点性质而提出改进方法的：1、插入排序在对几乎已经排好
10、序的 数据操作时，效率高，%20即可以达到 线性排序的效率2、对于大规模乱序数组插入排序很 慢，因为它只会交换相邻的元素，因此 元素只能一点一点地从数组的一端移动 到另一端。希尔排序简单地改进了插入排序， 交换不相邻的元素以对数组的局部进行 排序，并最终用插入排序将局部有序的 数组排序。思想：使数组中任意间隔为h的元 素都是有序的。这样的数组被称为h有 序数组。在进行排序时，如果h很大， 我们就能将元素移动到很远的地方，为 精选公文范文8精选公文范文 实现更小的h有序创造方便。我们只需要在插入排序的代码中将 移动元素的距离改为h即可。这样，希 尔排序的实现就转化为了一个类似于插 入排序但使用不
11、同增量的过程。【图例】void%20sort(Comparable%20a)%20%20 %20%20将 a 按升序排 列 20%20%20%20int%20N%20=%20; %20%20%20%20int%20h%20=%201%20 ;%20%20%20%20%20%20%20%20 根 据数组长度%20选取适当的初始间隔 h%20%20%20%20while%20(h%20=%20 1)%20%20%20%20%20%20%20%20% 20%20%20%20将数组变为 h 有 序 %20%20%20%20%20%20%20%20for %20(int%20i%20=%20h;%20i
12、%20=h%20 &%201ess(a,%20a);%20j-=h)%20%20% 20%20%20%20%20%20%20%20%20%2 0%20%20%20%20exch(a,%20j,%20j-h)% 20;%20%20%20%20%20%20%20%20% 精选公文范文9精选公文范文20%20%20%20%20%20%20%20h%20= %20h/3%20;%20%20%20%20希尔排序更高效的原因是它权衡了 子数组的规模和有序性。排序之初，各 个子数组都很短，排序之后子数组都是 部分有序的，这两种情况都很适合插入 排序。希尔排序的算法性能不仅取决于h， 还取决于h之间的数学性质
13、。在实际应 用中，使用3*h+l的递增序列基本就足 够了。【在最坏情况下希尔排序的比较次 数和成正比】希尔排序的代码量很小，且不需要 使用额外的内存空间。如果你需要解决 一个排序问题而又没有系统排序函数可 用，可以先用希尔排序，然后再考虑是 否值得将它替换为更加复杂的排序算 法。思想：要将一个数组排序，可以先 将它分成两半分别排序，然后将结果归 并起来。精选公文范文 【图例】一个归并排序的例子:对一个随机点 的链表进行排序。void%20Sort(Comparable%20a)%20%20 %20%20aux%20=%20new%20Comparabl e%20;%20分 配 辅 助 空间 %
14、20%20%20%20sort(a,%200,%20-% 201)%20;void%20sort(Comparable%20a, %20int%201o,%20int%20hi)%20%20%2 0%20将 数 组 a 排序 20%20%20%20if%20(hi%20%20mid )%20%20%20%20%20%20%20%20%20 %20%20%20a%20=%20aux%20;%20%2 0%20%20%20%20%20%20else%20if%2 0(j%20%20hi)%20%20%20%20%20%2 0%20%20%20%20%20%20a%20=%20au x%20;%20
15、%20%20%20%20%20%20%20 else%20if%20(aux%20改进：用不同的方法处理小规模问题能改进大多数递归算法的性能，因为 递归会使小规模问题中方法的调用过于 精选公文范文精选公文范文频繁，所以改进对它们的处理方法就能 改进整个算法。对排序来说，插入排序非常简单，因此很可能在小数组上比归并排序更 快。使用插入排序处理小规模的子数组 一般可以将归并排序的运行时间缩短 10%15%。自底向上的归并排序递归实现的归并排序是算法设计中 分治思想的典型应用。我们可以把递归 方式写成迭代的一一先归并那些微型数 组，然后再成对归并得到的子数组。排 序首先我们进行的是两两归并，然后 是四四归并，然后是八八归并，一直下 去。void%20sort(Comparable%20a)%20%20 %20%20aux%20=%20new%20Comparabl e%20;%20 分 配 辅 助 空 间 %20%20%20%20int%20N%20=%20; %20%20%20%20%20%20%20%20for%2 精选公文范文i精选公文范文0(int%20sz%20=%201;%20sz%20
