99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話:13121318867

登錄
首頁精彩閱讀數(shù)據(jù)結(jié)構(gòu)常見的八大排序算法
數(shù)據(jù)結(jié)構(gòu)常見的八大排序算法
2017-01-03
收藏

數(shù)據(jù)結(jié)構(gòu)常見的八大排序算法

八大排序,三大查找是《數(shù)據(jù)結(jié)構(gòu)》當(dāng)中非?;A(chǔ)的知識點(diǎn),在這里為了復(fù)習(xí)順帶總結(jié)了一下常見的八種排序算法。

常見的八大排序算法,他們之間關(guān)系如下:

排序算法

他們的性能比較:

性能比較

下面,利用Python分別將他們進(jìn)行實(shí)現(xiàn)。

直接插入排序

算法思想:

直接插入排序

直接插入排序的核心思想就是:將數(shù)組中的所有元素依次跟前面已經(jīng)排好的元素相比較,如果選擇的元素比已排序的元素小,則交換,直到全部元素都比較過。

因此,從上面的描述中我們可以發(fā)現(xiàn),直接插入排序可以用兩個(gè)循環(huán)完成:

第一層循環(huán):遍歷待比較的所有數(shù)組元素

第二層循環(huán):將本輪選擇的元素(selected)與已經(jīng)排好序的元素(ordered)相比較。

如果:selected>ordered,那么將二者交換

代碼實(shí)現(xiàn)

希爾排序

算法思想:

希爾排序

希爾排序的算法思想:將待排序數(shù)組按照步長gap進(jìn)行分組,然后將每組的元素利用直接插入排序的方法進(jìn)行排序;每次將gap折半減小,循環(huán)上述操作;當(dāng)gap=1時(shí),利用直接插入,完成排序。

同樣的:從上面的描述中我們可以發(fā)現(xiàn):希爾排序的總體實(shí)現(xiàn)應(yīng)該由三個(gè)循環(huán)完成:

第一層循環(huán):將gap依次折半,對序列進(jìn)行分組,直到gap=1

第二、三層循環(huán):也即直接插入排序所需要的兩次循環(huán)。具體描述見上。

代碼實(shí)現(xiàn):

簡單選擇排序

算法思想

簡單選擇排序

簡單選擇排序的基本思想:比較+交換。

從待排序序列中,找到關(guān)鍵字最小的元素;

如果最小元素不是待排序序列的第一個(gè)元素,將其和第一個(gè)元素互換;

從余下的N-1個(gè)元素中,找出關(guān)鍵字最小的元素,重復(fù)(1)、(2)步,直到排序結(jié)束。

因此我們可以發(fā)現(xiàn),簡單選擇排序也是通過兩層循環(huán)實(shí)現(xiàn)。

第一層循環(huán):依次遍歷序列當(dāng)中的每一個(gè)元素

第二層循環(huán):將遍歷得到的當(dāng)前元素依次與余下的元素進(jìn)行比較,符合最小元素的條件,則交換。

代碼實(shí)現(xiàn):

堆排序

堆的概念

堆:本質(zhì)是一種數(shù)組對象。特別重要的一點(diǎn)性質(zhì):任意的葉子節(jié)點(diǎn)小于(或大于)它所有的父節(jié)點(diǎn)。對此,又分為大頂堆和小頂堆,大頂堆要求節(jié)點(diǎn)的元素都要大于其孩子,小頂堆要求節(jié)點(diǎn)元素都小于其左右孩子,兩者對左右孩子的大小關(guān)系不做任何要求。

利用堆排序,就是基于大頂堆或者小頂堆的一種排序方法。下面,我們通過大頂堆來實(shí)現(xiàn)。

基本思想:

堆排序可以按照以下步驟來完成:

首先將序列構(gòu)建稱為大頂堆;

(這樣滿足了大頂堆那條性質(zhì):位于根節(jié)點(diǎn)的元素一定是當(dāng)前序列的最大值)

構(gòu)建大頂堆

取出當(dāng)前大頂堆的根節(jié)點(diǎn),將其與序列末尾元素進(jìn)行交換;

(此時(shí):序列末尾的元素為已排序的最大值;由于交換了元素,當(dāng)前位于根節(jié)點(diǎn)的堆并不一定滿足大頂堆的性質(zhì))

對交換后的n-1個(gè)序列元素進(jìn)行調(diào)整,使其滿足大頂堆的性質(zhì);

Paste_Image

重復(fù)2.3步驟,直至堆中只有1個(gè)元素為止

代碼實(shí)現(xiàn):

冒泡排序

基本思想

冒泡排序

冒泡排序思路比較簡單:

將序列當(dāng)中的左右元素,依次比較,保證右邊的元素始終大于左邊的元素;

(第一輪結(jié)束后,序列最后一個(gè)元素一定是當(dāng)前序列的最大值;)

對序列當(dāng)中剩下的n-1個(gè)元素再次執(zhí)行步驟1。

對于長度為n的序列,一共需要執(zhí)行n-1輪比較

(利用while循環(huán)可以減少執(zhí)行次數(shù))

*代碼實(shí)現(xiàn):

快速排序

算法思想:

快速排序

快速排序的基本思想:挖坑填數(shù)+分治法

從序列當(dāng)中選擇一個(gè)基準(zhǔn)數(shù)(pivot)

在這里我們選擇序列當(dāng)中第一個(gè)數(shù)最為基準(zhǔn)數(shù)

將序列當(dāng)中的所有數(shù)依次遍歷,比基準(zhǔn)數(shù)大的位于其右側(cè),比基準(zhǔn)數(shù)小的位于其左側(cè)

重復(fù)步驟1.2,直到所有子集當(dāng)中只有一個(gè)元素為止。

用偽代碼描述如下:

1.i=L;j=R;將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]。

2.j--由后向前找比它小的數(shù),找到后挖出此數(shù)填前一個(gè)坑a[i]中。

3.i++由前向后找比它大的數(shù),找到后也挖出此數(shù)填到前一個(gè)坑a[j]中。

4.再重復(fù)執(zhí)行2,3二步,直到i==j,將基準(zhǔn)數(shù)填入a[i]中

代碼實(shí)現(xiàn):

歸并排序

算法思想:

歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)典型的應(yīng)用。它的基本操作是:將已有的子序列合并,達(dá)到完全有序的序列;即先使每個(gè)子序列有序,再使子序列段間有序。

歸并排序其實(shí)要做兩件事:

分解----將序列每次折半拆分

合并----將劃分后的序列段兩兩排序合并

因此,歸并排序?qū)嶋H上就是兩個(gè)操作,拆分+合并

如何合并?

L[first...mid]為第一段,L[mid+1...last]為第二段,并且兩端已經(jīng)有序,現(xiàn)在我們要將兩端合成達(dá)到L[first...last]并且也有序。

首先依次從第一段與第二段中取出元素比較,將較小的元素賦值給temp[]

重復(fù)執(zhí)行上一步,當(dāng)某一段賦值結(jié)束,則將另一段剩下的元素賦值給temp[]

此時(shí)將temp[]中的元素復(fù)制給L[],則得到的L[first...last]有序

如何分解?

在這里,我們采用遞歸的方法,首先將待排序列分成A,B兩組;然后重復(fù)對A、B序列

分組;直到分組后組內(nèi)只有一個(gè)元素,此時(shí)我們認(rèn)為組內(nèi)所有元素有序,則分組結(jié)束。

代碼實(shí)現(xiàn):

基數(shù)排序

算法思想

基數(shù)排序:通過序列中各個(gè)元素的值,對排序的N個(gè)元素進(jìn)行若干趟的“分配”與“收集”來實(shí)現(xiàn)排序。

分配:我們將L[i]中的元素取出,首先確定其個(gè)位上的數(shù)字,根據(jù)該數(shù)字分配到與之序號相同的桶中

收集:當(dāng)序列中所有的元素都分配到對應(yīng)的桶中,再按照順序依次將桶中的元素收集形成新的一個(gè)待排序列L[]

對新形成的序列L[]重復(fù)執(zhí)行分配和收集元素中的十位、百位...直到分配完該序列中的最高位,則排序結(jié)束

根據(jù)上述“基數(shù)排序”的展示,我們可以清楚的看到整個(gè)實(shí)現(xiàn)的過程

代碼實(shí)現(xiàn)

后記

寫完之后運(yùn)行了一下時(shí)間比較:

1w個(gè)數(shù)據(jù)時(shí):


10w個(gè)數(shù)據(jù)時(shí):

從運(yùn)行結(jié)果上來看,堆排序、歸并排序、基數(shù)排序真的快。數(shù)據(jù)分析培訓(xùn)

對于快速排序迭代深度超過的問題,可以將考慮將快排通過非遞歸的方式進(jìn)行實(shí)現(xiàn)。

數(shù)據(jù)分析咨詢請掃描二維碼

若不方便掃碼,搜微信號:CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1:配置參數(shù) // 參數(shù)2:回調(diào),回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對象,之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須,不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺檢測極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式,包括:float,popup width: "280px", https: true // 更多配置參數(shù)說明請參見:http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請輸入'+oInput.attr('placeholder')+'!'; var errTxt = '請輸入正確的'+oInput.attr('placeholder')+'!'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }