西安网站空间,wordpress 多网址,在线视频网站 一级做爰片,网站 成本排序#xff0c;也称为排序算法#xff0c;可以说是我们学习算法的过程中遇到的第一个门槛#xff0c;也是实际应用中使用得较为频繁的算法#xff0c;我将自己对所学的排序算法进行一个归纳总结与分享#xff0c;如有错误#xff0c;欢迎指正#xff01;排序算法学习分…排序也称为排序算法可以说是我们学习算法的过程中遇到的第一个门槛也是实际应用中使用得较为频繁的算法我将自己对所学的排序算法进行一个归纳总结与分享如有错误欢迎指正排序算法学习分享一选择排序排序算法学习分享二交换排序---冒泡排序与快速排序排序算法学习分享三插入排序一排序的分类排序算法主要分为内部排序与外部排序当数据量大时数据无法全部加载到内存中因此需要接抓外部存储文件、磁盘等进行排序。而内部排序则是指将要处理的所有数据加载到内部存储器中并在内存中就完成排序。本文针对的为内部排序。二内部排序4 希尔排序前文我介绍了插入排序但是插入排序会出现一个问题。如果我们拿到的是一个较小的数进行插入排序那么元素后移的次数会明显增加那么就会严重影响整个排序的效率。接下来介绍的希尔排序就是经典的对插入排序的一种优化。希尔排序也称递减增量排序是插入排序的一种更高效的改进版本。我们都知道插入排序对已经有序的或者是有序程度高的序列排序是非常快的但一般情况下由于插入排序每插入一个元素都只能一个一个元素地进行移动因此它的效率是十分低下的。显然要优化插入排序的移动是很困难的而希尔排序取巧地不去优化它的移动希尔排序的思想我用一句话去概括尽可能的在数组进行下一轮的排序时提高数组的有序程度。先记住一点在序列的排序中元素越少需要交换的次数越少排序越快。那么怎么去提高一个数组的有序程度呢用一个很有趣的东西——增量。这类似于分治思想但它又不是。希尔排序利用增量这一个东西去将序列分割成若干个子序列再将每个子序列分别排好。 那么究竟什么是增量又要怎么利用增量增量就是一个等差数列的差值比如1,3,5,7,9。它们的增量是2。一开始尽可能使用一个大的增量使得每个子序列中的元素少比如第一轮就尽量使得一个子序列的元素只有两个。增量越大那么分的组就会越多每个组中的元素数目就会小。每一轮都比上一轮的增量按照一定的规律递减那么分的组就会比上一轮的分的组少而每个组中的元素就要比上一轮的元素要多当增量一直减到1的时候我们就会发现只有一个组了而这个组中的元素就是整个序列的所有元素这就是递减增量。利用增量这样子分割序列是为了什么呢是为了使下一轮的有序程度变高。为什么我说希尔排序是一种取巧呢就是因为它耍赖皮有序程度低的时候增量就大分组就多组内元素就少排序就快。当这一轮排序完成的时候全体序列的有序程度一定是要比上一轮的有序程度要高的有一些特殊情况严谨地应该说是不低于。增量每一次发生递减那么序列的有序程度就提高了那么一点当增量递减到1的时候序列的有序程度就已经很高的这时再进行一轮插入排序就很快了。这么将还是有些抽象我们举一个实例上一些图来说明。这是一个原始数组可以看到它的有序程度并不高。我们对它进行第一次增量分组使得每组中的元素尽可能少。最少的话是一个元素一个组但是如果组中只有一个元素那么组内的排序根本没有意义因此第一次的这个尽可能少就是两两一组。此时的增量为4。我们对每个子数组内进行排序。由于每个子数组内的元素很少因此排序很快排序完如下我们已经可以看到只是经过简单的几个交换后数组的有序程度就已经显著提升了那么接下来就是进入到下一轮。递减增量直接使增量减半(希尔增量)新的增量为4 / 2 2将2作为新的增量重新进行分组分组如下。我们对每个分组内进行排序因为经过了上一轮的排序可以看到每个组内的有序程度比上一轮如果也按照这个增量分组的有序程度要高。这就达到了希尔排序的目的就是每一轮都要比上一轮的有序程度要高这很像我们做产品时候的不断迭代。排序好后如下这一轮结束后增量再递减就变成1了最后再进行一轮插入排序即可此时需要移动的数仅仅就是5和38和9。有序程度比原数组高到不知道哪里去了。再来一轮插入排序就完成啦其实递减增量的规则有很多种不止折半这一种有时候根据需求改变递减增量的方式会取得更优的性能。下面尝试用代码实现希尔排序:希尔排序使用的增量是折半的方式递减的这种方式的增量叫做希尔增量。希尔排序利用增量分组粗调一般情况下是减少了插入排序的工作量使得插入排序的时间复杂度低于O(n²)。但是在一种极端的情况下希尔排序所做的粗略调整不但没有减少插入排序的工作量反而增大的插入排序的工作量。举一个例子我们利用希尔增量来分组当增量为4时分组为27165938。我们可以看到它在组内是有序的再折半减少增量为2分组为25791368还是有序的经过两轮增量排序它的有序程度并没有提高比起直接插入排序反而还增加分组排序的这一个步骤增加了工作量。会出现这种情况的原因在于希尔增量希尔增量之间是等比的这代表着等比之间是可以出现一定的盲区的就像上面这个例子就完美地处在了希尔增量之间的盲区。那么才能使得增量之间没有盲区呢最好的方式就是使得每一轮彼此的增量“互质”。而增量的方式很多最为典型的就是Hibbard增量和Sedgewick增量。因为本文讲的是希尔排序就不继续往下介绍了。希尔排序是一个不稳定的排序算法是因为在分组的过程中两个元素的交换的跨度有时候是会很大的。比如m i j k而原数组是( i j k m )那么第一轮希尔排序后i 就到 j 后面了。希尔排序的介绍就到这里啦希尔排序的中心思想就是: 尽可能的在数组进行下一轮的排序前提高数组的有序程度。即每一轮都比上一轮时候的有序程度要高。
