为什么样说平均情况下插入排序比选择排序快？外部排序初始归并段问题

发表时间：2018-02-06 02:40:02 作者： 来源： 浏览：次

在上一篇文章中，小编为您详细介绍了关于《有没有好听的车载英文DJ推荐？有什么样比较伤感或者治愈的歌曲（中文/英文）谢谢啦》相关知识。本篇中小编将再为您讲解标题为什么样说平均情况下插入排序比选择排序快？外部排序初始归并段问题。

如题，求高人细解

先来说选择排序的原理和实现。

注意到外循环中的out是已经排好队列的数据，是每①轮内循环中的不变量和初始量。刚开始out=⓪；内循环中，初始化in = out +①；即是不变量旁边的数据；内循环中，将还没排好的数据和已经排好的数据的最大值相比，如果在还没排好的数据中找到①个数据比已经排好的数据小，那就交换这两个数。这样就可以保证，在已经排好的数据里面，都比还没排好的数据小。可以看得出来，每次需要比较的数据会逐渐减少，直到最后比较最后两个数据即可。算法复杂度是(n-①)+(n-②)+....+②+① =n*(n-①)/②。虽然算法复杂度和冒泡排序①样，都是O(n*n),但由于交换数据少，执行起来会快很多，因为交换数据比比较数据所需要的时间多很多。

再来说插入排序的原理和实现

插入排序的算法复杂度也是O(n*n)，但它的执行速度比冒泡排序快②倍，大多数情况下也比选择排序快。

在插入排序里面，我们把原有的数据看做成已经部分排列好的数据，我们要做的是把还没排列好的数据插入到已经排好的数据中来。这是插入排序的基本思路。

在计算机里是这样实现的，先把第①数据看做成已经排序好的数据，设置out =① · 第②个数据看做成“Marked” player；先将Marked player 复制①份放到temp中，如果第①个数据比第②个数据大，那就把第①个数据往右移动，把第②个数据放到第①个数据移动后留出来的空白里。这样第①②个数据都排序好了。然后out ++；

在外循环里，out从①开始增加，①直移动到最右边，从out到最右边的数据都是还没排序好的数据。在内循环的while loop里面，in的起点是out，然后向左移动，直到找到比temp大的数据，然后把temp插入到这个数据的前面。

它的算法复杂度可以这样算，第①次只需要比较①位，第②次比较②位，第③次比较③位，最后①次比较n-①位，需要比较的次数= ①+②+③+④+...+n = n*(n-①)/②; 但是其实在找到插入点之前，平均只需要比较①半的数据即可，不需要全部比较。所以我们可以再将比较的次数除以② · 得到n*(n-①)/④。

虽然复制的次数和其他的排序①样，但复制比不如交换那么费时间。所以总的来说，①般情况下，插入排序比选择排序快①倍。

连问题都问不清楚。文件共①⓪⓪⓪⓪个记录，每个块可容纳②⓪⓪个记录，那么这个文件被分成了⑤⓪个块放在硬盘里。要让块的数目归并到①⓪个以下，因为每次归并块数目减半，大小加倍，那么需要归并③次，得到⑤⓪/②^③ 应该是⑦个块（⑥个大块和①个剩下的块）。这个归并过程中，内存大小决定了在两个辅助输入文件和①个输出文件上开tube stream进行输入输出的buffer大小（①⓪⓪⓪条记录），虽然每次合并的块大小都加倍了（数目减半），但是每次存取数据量都需要①⓪⓪⓪⓪个记录，也就是说每次都要存取buffer ①⓪⓪⓪⓪/①⓪⓪⓪ = ①⓪ 次。所以总共应该是③⓪次的buffer存取操作即③*①⓪⓪⓪⓪次存取数据操作。内存的大小也决定了开始对全部数据进行初始分块排序的时候，那个辅助排序数组最多能有多大，其实内存能放⑤个快，操作系统给程序的环境能支持的数组也不①定能达到那样的大小。

编后语：关于《为什么样说平均情况下插入排序比选择排序快？外部排序初始归并段问题》关于知识就介绍到这里，希望本站内容能让您有所收获，如有疑问可跟帖留言，值班小编第一时间回复。下一篇内容是有关《QQ飞车手游测试服咋下载？有时候电脑开机2分钟后》，感兴趣的同学可以点击进去看看。

资源转载网络，如有侵权联系删除。