JavaScript實(shí)現(xiàn)的選擇排序算法實(shí)例分析
本文實(shí)例講述了JavaScript實(shí)現(xiàn)的選擇排序算法。分享給大家供大家參考,具體如下:
簡(jiǎn)單選擇排序是人們最熟悉的比較方式,其算法思想為:從數(shù)組的開頭開始,將第一個(gè)元素和其他元素進(jìn)行比較。檢查完所有元素后,最小的元素會(huì)被放到數(shù)組的第一個(gè)位置,然后算法會(huì)從第二個(gè)位置繼續(xù)。這個(gè)過程會(huì)一直進(jìn)行,當(dāng)進(jìn)行到數(shù)組的倒數(shù)第二個(gè)位置時(shí),所有的數(shù)據(jù)便完成了排序。
代碼如下:
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>JavaScript選擇排序</title> </head> <body> <script type="text/javascript"> function selectSort(nums){//選擇排序 var min;//最小值 for(var outer=0;outer<nums.length-1;outer++){//外循環(huán)選中元素 min=outer; for(var inner=outer+1;inner<=nums.length;++inner){ if(nums[inner]<nums[min]){//如果內(nèi)循環(huán)中元素比選中元素小 min=inner;//將其標(biāo)為最小元素 }//直到每次外循環(huán)的最小元素 swap(nums,outer,min);//最小值被調(diào)整到合適的位置 } } } function swap(arr,i,j){//交換位置 var temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } function show(nums){//顯示數(shù)組 for(var i=0;i<nums.length;i++){ document.write(nums[i]+' '); } document.write('<br>'); } var nums=[6,8,0,6,7,4,3,5,5,10]; show(nums);//6 8 0 6 7 4 3 5 5 10 selectSort(nums); show(nums);//0 3 4 5 5 6 6 7 9 10 </script> </body> </html>
分析可得,簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n2)。選擇排序的主要操作是進(jìn)行關(guān)鍵字之間的比較,因此改進(jìn)簡(jiǎn)單選擇排序應(yīng)該從如何減少比較出發(fā)。其實(shí)現(xiàn)實(shí)生活中就有一個(gè)很好的例子,就是比賽總的錦標(biāo)賽。8個(gè)人中選出冠軍其實(shí)不需要7+6+5=18場(chǎng)比賽,可以通過兩兩比較也就是11場(chǎng)比賽。這種方法叫做樹形選擇排序。
樹形選擇排序是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法,首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較,然后在其中n/2個(gè)較小者之間再進(jìn)行兩兩比較,直到找出最小關(guān)鍵字??梢酝ㄟ^一個(gè)完全二叉樹來表示,由于含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1,所以排序過程中每選擇一個(gè)次小關(guān)鍵字僅需要log2n次操作,所以其時(shí)間復(fù)雜度O(nlog2n),但是這種排序有一種缺點(diǎn)就是占用空間大。
所以我們需要介紹一種更加優(yōu)秀的排序,也就是堆排序。
附:堆排序算法
堆排序只需要一個(gè)記錄大小的輔助空間,每個(gè)待排序的記錄僅占用一個(gè)存儲(chǔ)空間。
堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最?。┻@一特征,使得當(dāng)前無序區(qū)中選取最大(或最?。╆P(guān)鍵字的記錄變得簡(jiǎn)單。我們以大跟堆為例子,排序的基本操作如下:
首先是建堆,建堆就是不斷調(diào)整堆的過程,從len2處開始調(diào)整,一直到第一個(gè)節(jié)點(diǎn),此處len是堆中元素的個(gè)數(shù)。建堆的過程是線性的過程,從len2到0處一直調(diào)用調(diào)整堆的過程,建堆的時(shí)間復(fù)雜度為O(n)。
接下來是調(diào)整堆,調(diào)整堆在建堆和堆排序的過程中都會(huì)用到,利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i)和right(i),選出三者最大(或最小)者,如果最大(?。┲挡皇枪?jié)點(diǎn)i而是它的一個(gè)子節(jié)點(diǎn),那么交換兩個(gè)節(jié)點(diǎn),然后繼續(xù)遞歸。
然后是堆排序:將堆的根節(jié)點(diǎn)取出,最后一個(gè)元素替換根節(jié)點(diǎn),將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程,然后再講根節(jié)點(diǎn)取出,直到所有結(jié)點(diǎn)取出。調(diào)整堆的時(shí)間復(fù)雜度為O(log2n)
所以堆排序的時(shí)間復(fù)雜度為O(nlog2n)。堆排序是就地排序,其輔助空間為O(1)。但是它不穩(wěn)定,(排序的穩(wěn)定性是指如果在排序的序列中,存在前后相同的兩個(gè)元素的話,排序前 和排序后他們的相對(duì)位置不發(fā)生變化)。
下面模擬建堆的過程:
堆排序?qū)τ谟涗洈?shù)較少的文件并不值得提倡,但是對(duì)于n較大的文件還是挺有效的。
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
- JavaScript實(shí)現(xiàn)經(jīng)典排序算法之選擇排序
- JS排序算法之冒泡排序,選擇排序與插入排序?qū)嵗治?/a>
- js交換排序 冒泡排序算法(Javascript版)
- js算法中的排序、數(shù)組去重詳細(xì)概述
- 幾種經(jīng)典排序算法的JS實(shí)現(xiàn)方法
- Javascript中的常見排序算法
- JS隨機(jī)洗牌算法之?dāng)?shù)組隨機(jī)排序
- javascript快速排序算法詳解
- Javascript排序算法之合并排序(歸并排序)的2個(gè)例子
- js的各種排序算法實(shí)現(xiàn)(總結(jié))
- JavaScript選擇排序算法原理與實(shí)現(xiàn)方法示例
相關(guān)文章
基于 Immutable.js 實(shí)現(xiàn)撤銷重做功能的實(shí)例代碼
這篇文章主要介紹了基于 Immutable.js 實(shí)現(xiàn)撤銷重做功能及一些需要注意的地方,需要的朋友可以參考下2018-03-03javascript 響應(yīng)鍵盤特定按鍵(只響應(yīng)數(shù)字鍵)
響應(yīng)鍵盤特定按鍵(只響應(yīng)數(shù)字鍵),大家可以看看思路。2009-03-03JS利用正則表達(dá)式實(shí)現(xiàn)簡(jiǎn)單的密碼強(qiáng)弱判斷實(shí)例
這篇文章主要給大家介紹了關(guān)于JS利用正則表達(dá)式實(shí)現(xiàn)簡(jiǎn)單的密碼強(qiáng)弱判斷的相關(guān)資料,實(shí)現(xiàn)后的效果非常簡(jiǎn)單,但也挺實(shí)用的,文中給出了詳細(xì)的示例代碼供大家參考學(xué)習(xí),需要的朋友們下面來一起看看吧。2017-06-06JS+CSS設(shè)置img在DIV中只顯示Img垂直居中的部分
img的寬和Div相同,但高不固定,要求只顯示Img垂直居中的部分,下面有個(gè)不錯(cuò)的示例,感興趣的朋友可以參考下2013-10-10electron-builder允許安裝時(shí)請(qǐng)求提升權(quán)限的場(chǎng)景分析
electron-builder 作為一個(gè)用于 Electron 應(yīng)用程序打包的工具,需要下載并使用 Electron 運(yùn)行時(shí)來創(chuàng)建可執(zhí)行文件,這篇文章給大家介紹electron-builder允許安裝時(shí)請(qǐng)求提升權(quán)限的相關(guān)知識(shí),感興趣的朋友跟隨小編一起看看吧2024-03-03JavaScript中重名的函數(shù)與對(duì)象示例詳析
最近同事問了一個(gè)問題,說在js中如果函數(shù)與對(duì)象重名了會(huì)怎么樣?仔細(xì)詳細(xì)這個(gè)問題值得討論一下,所以便有了這篇文章,這篇文章主要給大家介紹了關(guān)于JavaScript中重名的函數(shù)與對(duì)象的相關(guān)資料,需要的朋友可以參考借鑒,下面來一起看看吧啊。2017-09-09將html頁面保存成圖片,圖片寫入pdf的實(shí)現(xiàn)方法(推薦)
下面小編就為大家?guī)硪黄獙tml頁面保存成圖片,圖片寫入pdf的實(shí)現(xiàn)方法(推薦)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-09-09