iT邦幫忙

4

用Javascript征服演算法 (3-select sort & 實作)

進入Sort囉~~~開心
用Javascript征服演算法 (3-select sort & 實作)

轉眼間就來到鐵人賽第五天了!! 排列組合的問題也該告一段落

接下來開始介紹演算法(or資結)中蠻常見的Sort的問題,但在介紹之前,我想先對幾個簡單的Sort作為進入點

大致上在解Sort problem當中,最基本的就是Select Sort、Insert Sort 跟 Bubble Sort

今天就先來介紹簡單的Select Sort,以及他的javascript實作(相對前幾天來說更為簡單)

Select Sort

Select Sort的做法呢,首先他會將需要排序的目標,分成兩堆,一堆為已排序,另外一堆為未排序

分完兩堆後,會將未排序中最大or最小值(看是要由小排到大,還是由大排到小)加入已排序的資料的最後面

以上就是Select Sort的運作方式(什麼結束了? 當然~因為它是簡單排序法阿XD)

接下來就是Javascript的實作囉

一樣,先來分析我們需要哪幾個步驟來完成程式

  1. 一個定義好的list
  2. 搜尋所有陣列
  3. 搜尋未排序陣列
  4. 找出最大or最小值,加到已排序資料
  5. 當在比較過程,搜尋到最大or最小值時,可能需要作swap來將此值移到已排序的資料中

ps. 在實作時,會直接將已排序的資料設定在最左側

OK 以上四步驟後,就可以開始寫Code了

首先是 1. 一個定義好的list

var list = [10, 9, 1, 2, 5, 3, 8, 7];

再來是 2. 搜尋陣列

 for(var i = 0; i < list.length; i++) {
	}
  1. 搜尋未排序陣列

    for(var i = from + 1; i < to; i++) {

    }
    
  2. 找出最大or最小值,加到已排序資料

    function ascending(a, b) {return a - b;}

5.當在比較過程,搜尋到最大or最小值時,可能需要作swap來將此值移到已排序的資料中

function swap(list, i, j) {
    var tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
	}

以上程式碼完整呈現如下

function swap(list, i, j) {
	    var tmp = list[i];
	    list[i] = list[j];
	    list[j] = tmp;
	}
	
	function ascending(a, b) {return a - b;}
	
	function selectedIdx(list, from, to, compare) {
	    var selected = from;
	    for(var i = from + 1; i &lt; to; i++) {
	        if(compare(list[i], list[selected]) &lt; 0) { 
	            selected = i; 
	        }
	    }
	    return selected;
	}
	    
	function selectionSort(list, compare) {
	    for(var i = 0; i &lt; list.length; i++) {
	        var selected = selectedIdx(list, i, list.length, compare);
	        if(selected !== i) { swap(list, i, selected); }
	    }
	}
	
	var list = [10, 9, 1, 2, 5, 3, 8, 7];
	
	selectionSort(list, ascending);
	console.log(list);

今天的Select Sort探討就到這邊,明天會介紹Inselect Sort囉!!!

想直接運行程式可以到以下連結當中

[
http://jsfiddle.net/stanney/TrW6P/](<br />
http://jsfiddle.net/stanney/TrW6P/)


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
pajace2001
iT邦研究生 1 級 ‧ 2013-09-28 22:03:00

沙發
「拍手」

我要留言

立即登入留言