排序归并、快排、优先队列等

精选公文范文排序归并、快排、优先队列等各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢思想：首先，找到数组中最小的那个元素。其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。【图例】图中，x轴方向为数组的索引，y轴方向为待排序元素的值。选择排序有两个很鲜明的特点：运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点。数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了N次交换一一交换次数和数组的大精选公文范文1精选公文范文小是线性关系。【对于长度为N的数组，选择排序需要大约N2/2次比较和N次交换】思想：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序算法的运作如下：1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3、针对所有的元素重复以上的步骤，除了最后一个。4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。精选公文范文【图例】图中，x轴方向为数组的索引，y轴方向为待排序元素的值。由图中可看出，冒泡排序是从后到前，逐步有序的，最大的元素先沉到底部，接着是次大的void%20BubbleSort(Comparable%20a){%20%20%20%20//exchanged表示是否做过交换处理，一趟冒泡没有做过交换处理，即没有改变任何元素的位置，则停止冒泡。％20%20%20%20bool%20exchanged%20=%20false%20;%20%20%20%20%20int%20N%20=%%20;%20%20%20%20%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,%20a)%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%20;%20%20%20//标记有元素交换位置%20%20%20%20%20%20%20%20%20%20%20%20%20}%20%20%20%20%20%20%20%20}//for(j)%20%20%20%20}}特点：冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n2)次交换，而插入排序只要最多O(n)交换。冒泡排序的实现通常会对已经排序好的数列拙劣地执行O(n2)，而插入排序在这个例子只需要O(n)个运算。因此很多实现中避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一精选公文范文4精选公文范文个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。思想:将第i个元素与其左边的已经有序的元素一一比较，找到合适的位置，插入其中。为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。具体算法描述如下：1、从第一个元素开始，该元素可以认为已经被排序2、取出下一个元素，在已经排序的元素序列中从后向前扫描3、如果该元素大于新元素，将该元素移到下一位置4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置5、将新元素插入到该位置后6、重复步骤2~5与选择排序一样，当前索引左边的所有元素都是有序的。但它们的最终位精选公文范文精选公文范文置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。插入排序不会访问索引右侧的元素，而选择排序不会访问索引左侧的元素。和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。对一个其中的元素已经有序(或接近有序)的数组进行排序，将会比对随机顺序的数组或是逆序数组进行排序要快得多。【图例】使用插入排序为一列数字进行排序的过程。从前到后逐步有序。void%20sort(Comparable%20a){%20%20%20%20//将a按升序排列％20%20%20%20int%20N%20=%%20;%20%20%20%20for%20(int%20i%20=%201;%20i%20=1%20&&%20less(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次比较以及~N2/4次交换。】【当倒置(两元素颠倒)的数量很少时，插入排序很可能比其他任何排序算法都要快！】【插入排序对于部分有序的数组十分高效，也很适合小规模数组。它也是高级排序算法的中间过程。】【插曲】Knuth高爷爷说：“尽管第一个二分查找程序于1946年就已经公布了，但是第一个没有bug的二分查找程序在1962年才出现。”显然，我们上面的二分查找代码是精选公文范文7精选公文范文有bug的。%20至于二分查找，以后会再起一篇博文详细讨论。希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的：1、插入排序在对几乎已经排好序的数据操作时，效率高，%20即可以达到线性排序的效率2、对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。思想：使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为精选公文范文8精选公文范文实现更小的h有序创造方便。我们只需要在插入排序的代码中将移动元素的距离改为h即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。【图例】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=%201)%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%20=h%20&&%20less(a,%20a);%20j-=h)%20%20%20%20%20%20%20%20%20%20%20%20%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之间的数学性质。在实际应用中，使用3*h+1的递增序列基本就足够了。【在最坏情况下希尔排序的比较次数和成正比】希尔排序的代码量很小，且不需要使用额外的内存空间。如果你需要解决一个排序问题而又没有系统排序函数可用，可以先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。思想：要将一个数组排序，可以先将它分成两半分别排序，然后将结果归并起来。精选公文范文【图例】一个归并排序的例子:对一个随机点的链表进行排序。void%20Sort(Comparable%20a){%20%20%20%20aux%20=%20new%20Comparable%20;%20//分配辅助空间％20%20%20%20sort(a,%200,%%20-%201)%20;}void%20sort(Comparable%20a,%20int%20lo,%20int%20hi){%20%20%20%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%20%20%20%20%20%20%20else%20if%20(j%20>%20hi)%20%20%20%20%20%20%20%20%20%20%20%20a%20=%20aux%20;%20%20%20%20%20%20%20%20else%20if%20(aux%20改进：用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于精选公文范文精选公文范文频繁，所以改进对它们的处理方法就能改进整个算法。对排序来说，插入排序非常简单，因此很可能在小数组上比归并排序更快。使用插入排序处理小规模的子数组一般可以将归并排序的运行时间缩短10%〜15%。自底向上的归并排序递归实现的归并排序是算法设计中分治思想的典型应用。我们可以把递归方式写成迭代的一一先归并那些微型数组，然后再成对归并得到的子数组。排序首先我们进行的是两两归并，然后是四四归并，然后是八八归并，一直下去。void%20sort(Comparable%20a){%20%20%20%20aux%20=%20new%20Comparable%20;%20//分配辅助空间％20%20%20%20int%20N%20=%%20;%20%20%20%20%20%20%20%20for%2精选公文范文1精选公文范文0(int%20sz%20=%201;%20sz%20自底向上的归并排序比较适合用链表组织的数据。这种方法只需要重新组织链表链接就能将链表原地排序【归并排序是一种渐进最优的基于比较排序的算法】归并排序的缺点：它所需的额外空间和N成正比。思想：快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。一般策略是先随意地取a作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右端扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。如此继续，我们就可以保证左指针i的左侧元素都不大于切分元素，右指针j的右侧元素都不小于切分元素。当两个指针相遇时，我精选公文范文1精选公文范文们只需要将切分元素a和左子数组最右侧的元素(a)交换然后返回j即可。void%20%20sort(Comparable%20a,%20int%20lo,%20int%20hi){%20%20%20%20if%20(hi%20=%20j)%20%20%20%20%20%20%20%20%20%20%20%20break%20;%20%20%20%20%20%20%20%20exch(a,%20i,%20j)%20;%20%20%20%20}%20%20%20%20exch(a,lo,j);%20%20%20%20return%20j%20;}快速排序的特点是原地排序，且将长度为N的数组排序所需的时间和NlgN成正比。缺点：在切分不平衡时这个程序可能会极为低效。改进：切换到插入排序和大多数数组递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：对于小数组，快速排序比插入排序慢。精选公文范文因为递归，快速排序的sort()方法在小数组中也会调用自己。因此，在排序小数组时应该切换到插入排序。将%20sort()中的语句%20if%20(hi%20void%20sort(Comparable%20a,%20int%20lo.%20int%20hi){%20%20%20%20if%20(hi%20%20v)%20%20%20%20%20%20%20%20%20%20%20%20exch(a,%20i,%20gt--)%20;%20%20%20//a比v大%20把a值放入尾部%20%20%20%20%20%20%20%20else%20%20%20%20%20%20%20%20%20%20%20%20i++%20;%20%20%20%20}%20%20%20%20%20%20%20%20sort(a,%20lo,%20lt-1)%20;%20%20%20%20sort(a,%20gt+1,%20hi)%20;}这段排序代码的切分能够将和切分元素相等的元素归位，这样它们就不会被包含在递归调用处理的子数组之中。对于存在大量重复元素的数组，这种方法比标准的快速排序的效率高的多。精选公文范文精选公文范文许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次将它们排序。很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素，如此这般。在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。数据结构二叉堆能够很好地实现优先队列的基本操作。当一颗二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。我们使用完全二叉树来表达二叉堆，会变得特别方便。完全二叉树只用数组而不需要指针就可以表示。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3,而子结点的子结点则分别在位置4、5、6和7，以此类推。堆的算法我们用长度为N+1的私有数组pq精选公文范文来表示一个大小为N的堆，我们不会使用pq,堆元素放在pq至pq中。在有序化的过程中我们会遇到两种情况：当某个结点的优先级上升时，我们需要由下至上恢复堆的顺序。当某个结点的优先级下降时，我们需要由上至下恢复堆的顺序。•由下至上的堆有序化如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么我们就需要通过交换它和它的父结点来修复堆。交换后，这个结点比它的两个子结点都大，但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍地用同样的办法恢复秩序，将这个结点不断向上移动直到我们遇到了一个更大的父结点。void%20swim(int%20k){%20%20%20%20while%20(k%20>%201%20&&%20less(精选公文范文精选公文范文k/2,%20k))%20%20%20%20{%20%20%20%20%20%20%20%20exch(k/2,%20k)%20;%20%20%20%20%20%20%20%20k%20=%20k/2%20;%20%20%20%20}}•由上至下的堆有序化如果堆得有序状态因为某个结点变得比它的某子结点更小而被打破了，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。交换可能会在子结点处继续打破堆的有序状态，因此我们需要不断地用相同的方式将其修复，将结点向下移动直到它的子结点都比它更小或是到达了堆的底部。void%20sink(int%20k){%20%20%20%20while%20(2*k%20堆排序我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将它们按顺序删精选公文范文*精选公文范文去。堆的构造：由N个给定的元素构造一个堆，从右至左用sink()下沉函数构造子堆。开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为1的子堆，由此向前对每个结点sink()，直到我们在位置1上调用sink()方法，扫描结束。for%20(int%20k%20=%20N/2;%20k>=%201;%20k--)sink(a,%20k,%20N)%20;下沉排序：堆排序的主要工作都是在第二阶段完成的。这里我们将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。这个过程和选择排序有些类似，但所需的比较要少的多，因为堆提供了一种从未排序部分找到最大元素的有效方法。while%20(N%20>%201)精选公文范文---精选公文范文{exch(a,%201,%20N--)%20;%20//把堆尾结点与堆顶最大元素交换sink(a,%201,%20N)%20;%20//对改变后的堆顶结点下沉操作}堆排序总代码：void%20sort(Comparable%20a){%20%20%20%20int%20n%20=%%20;%20%20%20%20%20%20%20%20for%20(int%20k%20=%20N/2;%20k%20>=%201;%20k--)%20%20%20%20%20%20%20%20sink(a,%20k,%20N)%20;%20%20%20%20while%20(N%20>%201)%20%20%20%20{%20%20%20%20%20%20%20%20exch(a,%201,%20N--)%20;%20//把堆尾结点与堆顶