兴义市住房城乡建设局网站,免费网站服务器2020,百度热点榜单,公司网站免费申请七大排序的个人总结#xff08;二#xff09; 归并排序#xff08;Merge 归并排序#xff08;Merge Sort#xff09;: 归并排序是一个相当“稳定”的算法对于其它排序算法#xff0c;比如希尔排序#xff0c;快速排序和堆排序而言#xff0c;这些算法有所谓的最好与最…七大排序的个人总结二 归并排序Merge 归并排序Merge Sort: 归并排序是一个相当“稳定”的算法对于其它排序算法比如希尔排序快速排序和堆排序而言这些算法有所谓的最好与最坏情况。而归并排序的时间复杂度是固定的它是怎么做到的 两个有序数组的合并 首先来看归并排序要解决的第一个问题两个有序的数组怎样合成一个新的有序数组 比如数组1 3578 数组2为 14910 首先那肯定是创建一个长度为8的新数组咯然后就是分别从左到右比较两个数组中哪一个值比较小然后复制进新的数组中比如我们这个例子 3578 14910 一开始新数组是空的。 然后两个指针分别指向第一个元素进行比较显然1比3小所以把1复制进新数组中 3578 14910 1 第二个数组的指针后移再进行比较这次是3比较小 3578 14910 13 同理我们一直比较到两个数组中有某一个先到末尾为止在我们的例子中第一个数组先用完。 3578 14910 134578 最后把第二个数组中的元素复制进新数组即可。 134578910 由于前提是这个两个数组都是有序的所以这整个过程是很快的我们可以看出对于一对长度为N的数组进行合并所需要的比较次数最多为2 * N -1这里多谢园友icyjiang的提醒。 这其实就是归并排序的最主要想法和实现归并排序的做法是: 将一个数组一直对半分问题的规模就减小了再重复进行这个过程直到元素的个数为一个时一个元素就相当于是排好顺序的。 接下来就是合并的过程了合并的过程如同前面的描述。一开始合成两个元素然后合并4个8个这样进行。 所以可以看到归并排序是“分治”算法的一个经典运用。 我们可以通过代码来看看归并算法的实现 public static int[] sort(int[] array, int left, int right) {if (left right) {return new int[] { array[left] };}int mid (right left) / 2;int[] l sort(array, left, mid);int[] r sort(array, mid 1, right);return merge(l, r);}// 将两个数组合并成一个public static int[] merge(int[] l, int[] r) {int[] result new int[l.length r.length];int p 0;int lp 0;int rp 0;while (lp l.length rp r.length) {result[p] l[lp] r[rp] ? l[lp] : r[rp];}while (lp l.length) {result[p] l[lp];}while (rp r.length) {result[p] r[rp];}return result;} 代码量其实也并不多主要的工作都在合并两个数组上。从代码上看 if (left right) {return new int[] { array[left] };} 这个是递归的基准base case也就是结束的条件是当元素的个数只有一个时。 int mid (right left) / 2;int[] l sort(array, left, mid);int[] r sort(array, mid 1, right); 这一部分显然就是分divide将一个大问题分成小的问题。 最后也就是治conquer了将两个子问题的解合并可以得到较大问题的解。 所以可以说归并排序是说明递归和分治算法的经典例子。 然后就又要回到比较原始的问题了归并排序它为什么会快呢 想回答这个问题可以先想一下之前说过的提高排序速度的两个重要的途径一个是减少比较次数一个是减少交换次数。 对于归并排序而言我们来从之前的例子应该可以看到两个数组的合并过程是线性时间的也就是说我们每一次比较都可以确定出一个元素的位置。这是一个重要的性质。 我们来看一个可以用一个例子来体会一下假如有这样一个数组 37251046 冒泡和选择排序的比较次数是25次。 直接插入排序用了15次。 而归并排序的次数是相对稳定的由我们上面提到的比较次数的计算方法我们的例子要合并4对长度为1的2对长度为2的和1对长度为4的。 归并排序的最多的比较次数为4 * 1 2 * 3 7 17次。感谢icyjiang的提醒 再次说明一下这个例子依然只是为了好理解不能作为典型例子来看。 因为元素的随机性直接插入排序也可能是相当悲剧的。但我们应该从中看到的是归并排序在比较次数上的优势。 至于在种优势是怎么来的我个人不成熟的总结一下就是尽量的让上一次操作的结果为下一次操作服务。 我们每一次合并出来的数组是不是就是为下一次合并做准备的。因为两个要合并的数组是有序的我们才可能高效地进行合并。 快速排序Quick Sort 这个算法的霸气程度从它的名字就可以看出来了。快速排序的应用也是非常广的的各种类库都可以看到他的身影。这当然与它的“快”是有联系的正所谓天下武功唯快不破。 快速排序的一个特点是对数组的一次遍历可以找到一个枢纽元pivot确定位置还可以把这个数组以这个枢纽元分成两个部分左边的元素值都比枢纽元小右边的都比枢纽元大。我们递归地解决这两个子数组即可。 我们还是通过一个特殊的例子来看一下快速排序的原理 我们假设有这样一个数组 4732815 对于快速排序来说第一步就是找出一个枢纽元而对于枢纽元的寻找是对整个算法的时间性能影响很大的因为搞不好快速排序会退化成选择排序那样。 对于这个不具有代表性的例子我们选择的是第一个元素做为枢纽元。 pivot 4 4732815 其中红色为左指针蓝色为右指针。一开始我们从右边开始找到第一个比pivot小的数。停止然后将该值赋给左指针同样左指针向右移动。 也就是说我们第一次得到的的结果是这样的 1732815 同样的道理我们在左边找到一个比pivot大的值赋值给右指针同时右指针左移一步。 得到的结果应该是这样的 1732875 请注意我们的这个移动过程的前提都是左指针不能超过右指针的前提下进行的。 这两个过程交替进行其实就是在对元素进行筛选。这一次得到的结果是 1232875 黄色高亮表示两个指针重叠了这时候我们也就找到了枢纽元的位置了将我们的枢纽元的值插入。 也就是说我们接下来的工作就是以这个枢纽元为分割对左右两个数组进行同样的排序工作。 来看看具体的代码是怎么实现的 public static void sort(int[] array, int start, int end) {if (start end) {return;}int left start;int right end;int temp array[left];while (left right) {while (left right temp array[right]) {right--;}if (left right) {array[left] array[right];left;}while (left right temp array[left]) {left;}if (left right) {array[right] array[left];right--;}}array[left] temp;sort(array, start, left - 1);sort(array, left 1, end);} 接下来还是同样的问题快速排序为什么会快呢如果没有足够的强大那不是“浪得虚名”吗 首先还是看看前面的例子。 首先可以比较容易感受到的就是元素的移动效率高了。比如说例子中的1一下子就移动到了前面去。 这也是我个人的一点感受只是觉得可以这样理解比较高效的排序算法的特性 高效的排序算法对元素的移动效率都是比较高的。 它不像冒泡直接插入那样每次可能都是步进一步而是比较快速的移动到“感觉是正确”的位置。 想想希尔排序不就是这么做的吗后面的堆排序也是这个原理。 其次快速排序也符合我们前面说的“让上一个操作的结果为下一次操作服务”。 很明显在枢纽元左边的元素都比枢纽元要小右边的都比枢纽元大。显然数据的范围小了数据的移动的准确性就高了。 但是快速排序的一个隐患就是枢纽元的选择我提供的代码中是选第一个元素做枢纽元这是一种很冒险的做法。 比如我们对一个数组 98765 想通过快速排序来变成从小到大的排序。如果还是选择以第一个元素为枢纽元的话快速排序就变成选择排序了。 所以在实际应用中如果数据都是是随机数据那么选择第一个做枢纽元并没有什么不妥。因为这个本来就是看“人品”的。 但是如果是对于一些比较有规律的数据我们的“人品”可能就不会太好的。所以常见的有两种选择策略 一种是使用随机数来做选择。呵呵听天由命。 另一种是取数组中的第一个最后一个和中间一个选择数值介于最大和最小之间的。 这一种又叫做“三数中值分割法”。理论上这两种选择策略还是可能很悲剧的。但概率要小太多了。 堆排序用文字太难看懂了想画一些图来帮助理解求各位大大推荐可以比较方便画二叉树的工具。 分类: 数据结构 转载于:https://www.cnblogs.com/wangprince2017/p/7663457.html
