排序方法

<div id="article_content" class="article_content clearfix csdn-tracking-statistics" data-pid="blog" data-mod="popu_307" data-dsm="post">
            <link rel="stylesheet" href="https://csdnimg.cn/release/phoenix/template/css/ck_htmledit_views-e2445db1a8.css">
<div class="htmledit_views">
                
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:'Times New Roman'"><span style="font-size:12px">作者：寒小陽<br>
</span></span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-size:12px"><span style="font-family:'Times New Roman'">時間：2013年9月。<br>
</span><span style="font-family:'Times New Roman'">出處：<a target="_blank" href="http://blog.csdn.net/han_xiaoyang/article/details/12118943" rel="nofollow" style="color:rgb(202,0,0); text-decoration:none"></a><a target="_blank" href="http://blog.csdn.net/han_xiaoyang/article/details/12163251" rel="nofollow" style="color:rgb(202,0,0); text-decoration:none">http://blog.csdn.net/han_xiaoyang/article/details/12163251</a>。<br>
</span><span style="font-family:'Times New Roman'">宣告：著作權所有，轉載請注明出處，謝謝。</span></span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<br>
</p>
<h1 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t0"></a><a target="_blank" name="t0" style="color:rgb(202,0,0)"></a><span style="font-size:14px"><span style="font-family:'Times New Roman'">0、前言 &nbsp; &nbsp;</span></span></h1>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:'Times New Roman'">&nbsp;從這一部分開始直接切入我們計算機互聯網筆試面試中的重頭戲演算法了，初始的想法是找一條主線，比如資料結構或者解題思路方法，將博主見過做過整理過的演算法題逐個分析一遍(博主當年自己學演算法就是用這種比較笨的刷題學的，囧)，不過又想了想，演算法這東西，博主自己學的程序中一直深感，基礎還是非常重要的，很多難題是基礎類資料結構和題目的思想綜合發散而來。比如說作為最基本的排序演算法就種類很多，而事實上筆試面試程序中發現掌握的程度很一般，有很多題目，包括很多演算法難題，其母題或者基本思想就是基于這些經典演算法的，比如說快排的partition演算法，比如說歸并排序中的思想，比如說桶排序中桶的思想。</span><br>
<span style="font-family:'Times New Roman'">&nbsp; &nbsp; &nbsp; &nbsp; 這里對筆試面試最常涉及到的12種排序演算法(包括</span><strong><span style="font-family:KaiTi_GB2312">插入排序、二分插入排序、希爾排序、選擇排序、冒泡排序、雞尾酒排序、快速排序、堆排序、歸并排序、桶排序、計數排序和基數排序</span></strong><span style="font-family:'Times New Roman'">)進行了詳解。每一種演算法都有</span><span style="font-family:FangSong_GB2312; color:rgb(255,0,0)">基本介紹、演算法原理分析、圖解/flash演示/視頻演示、演算法代碼、筆試面試重點分析、筆試面試題</span><span style="font-family:'Times New Roman'">等板塊，希望能幫助大家真正理解這些排序演算法，并能使用這些演算法的思想解決一些題。不多說了，下面就進入正題了。</span></p>
<h1 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t1"></a><a target="_blank" name="t1" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">一、插入排序</span></h1>
<h2 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t2"></a><a target="_blank" name="t2" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">1）演算法簡介</span></h2>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:'Times New Roman'">&nbsp; &nbsp; &nbsp; &nbsp; 插入排序（Insertion&nbsp;Sort）的演算法描述是一種簡單直觀的排序演算法。它的作業原理是通過</span><span style="font-family:KaiTi_GB2312; color:rgb(255,0,0)">構建有序序列，對于未排序資料，在已排序序列中從后向前掃描，找到相應位置并插入</span><span style="font-family:'Times New Roman'">。插入排序在實作上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描程序中，</span><span style="font-family:KaiTi_GB2312; color:rgb(255,0,0)">需要反復把已排序元素逐步向后挪位</span><span style="font-family:'Times New Roman'">，為最新元素提供插入空間。</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
</p>
<h2 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t3"></a><a target="_blank" name="t3" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">2）演算法描述和分析</span></h2>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;一般來說，插入排序都采用in-place在陣列上實作。具體演算法描述如下：</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:KaiTi_GB2312; color:rgb(51,51,255)">&nbsp;&nbsp;&nbsp;&nbsp;1、從第一個元素開始，該元素可以認為已經被排序</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:KaiTi_GB2312; color:rgb(51,51,255)">&nbsp;&nbsp;&nbsp;&nbsp;2、取出下一個元素，在已經排序的元素序列中從后向前掃描</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:KaiTi_GB2312; color:rgb(51,51,255)">&nbsp;&nbsp;&nbsp;&nbsp;3、如果該元素（已排序）大于新元素，將該元素移到下一位置</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:KaiTi_GB2312; color:rgb(51,51,255)">&nbsp;&nbsp;&nbsp;&nbsp;4、重復步驟3，直到找到已排序的元素小于或者等于新元素的位置</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:KaiTi_GB2312; color:rgb(51,51,255)">&nbsp;&nbsp;&nbsp;&nbsp;5、將新元素插入到該位置后</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:KaiTi_GB2312; color:rgb(51,51,255)">&nbsp; &nbsp; 6、重復步驟2~5</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
</p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:'Times New Roman'">&nbsp; &nbsp; &nbsp; &nbsp; 如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數減去(n-1)次。平均來說</span><span style="font-family:KaiTi_GB2312; color:rgb(255,0,0)">插入排序演算法復雜度為O(n^2)</span><span style="font-family:'Times New Roman'">。因而，插入排序不適合對于資料量比較大的排序應用。但是，如果需要排序的資料量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。&nbsp;插入排序在工業級庫中也有著廣泛的應用，在STL的sort演算法和stdlib的qsort演算法中，都將插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）。</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
</p>
<h2 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t4"></a><a target="_blank" name="t4" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">3）演算法圖解、flash演示、視頻演示</span></h2>
<h3 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t5"></a><a target="_blank" name="t5" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">圖解：</span></h3>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px; text-align:center">
<span style="font-family:'Times New Roman'"><img src="https://img-blog.csdn.net/20130929144225312?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGFuX3hpYW95YW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="" style="border:none; max-width:100%"><br>
</span></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
</p>
<h3 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t6"></a><a target="_blank" name="t6" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">Flash：</span></h3>
<div style="font-family:Arial; font-size:14px; line-height:26px"><span style="font-family:'Times New Roman'"><strong><a target="_blank" href="http://www.tjbpi.com/jpk/shujujiegou/flash/%B5%DA%CA%AE%D2%BB%D5%C2%20%C5%C5%D0%F2/%D6%B1%BD%D3%B2%E5%C8%EB%C5%C5%D0%F2.swf" rel="nofollow" style="color:rgb(202,0,0); text-decoration:none">http://www.tjbpi.com/jpk/shujujiegou/flash/%B5%DA%CA%AE%D2%BB%D5%C2%20%C5%C5%D0%F2/%D6%B1%BD%D3%B2%E5%C8%EB%C5%C5%D0%F2.swf</a><br>
</strong></span></div>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
</p>
<h3 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t7"></a><a target="_blank" name="t7" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">視頻：插入排序舞蹈</span></h3>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<a target="_blank" href="http://v.youku.com/v_show/id_XMjU4NTY5MzEy.html" rel="nofollow" style="color:rgb(202,0,0); text-decoration:none"><span style="color:rgb(0,0,255)"><span style="font-family:'Times New Roman'">http://v.youku.com/v_show/id_XMjU4NTY5MzEy.html</span></span></a></p>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
</p>
<h2 style="margin:0px; padding:0px; font-family:Arial; line-height:26px"><a name="t8"></a><a target="_blank" name="t8" style="color:rgb(202,0,0)"></a><span style="font-family:'Times New Roman'; font-size:14px">4）演算法代碼</span></h2>
<p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; font-family:Arial; font-size:14px; line-height:26px">
<span style="font-family:'Times New Roman'"></spa

uj5u.com熱心網友回復：

資料結構演算法 之 二分法折半查找 

http://www.verejava.com/?id=173042223942111

uj5u.com熱心網友回復：

寫的真不錯，請問可以轉載嗎！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247790.html

標籤：其他

上一篇：QGraphicsItemGroup用過的說下

下一篇：類似小猿搜題，作業幫這種手機app，里面的公式一般是用什么進行渲染的呢？