iT邦幫忙

DAY 11
3

用Javascript征服演算法系列 第 8

用Javascript征服演算法 (6-Quick Sort-實作)

有pseudo code 實作超快ㄉ而
快要沒時間了><

有了pseudo code後,超快就把程式寫出來了

加上昨天那篇的說明,很快就理解為何這樣寫就能完成,十分順利><

在此先附上code!!!

在貼一下神般pseudo code,就是參考此code寫出js版本

QUICKSORT(A, p, r) 
   if p < r 
     then q <- PARTITION(A, p, r) 
               QUICKSORT(A, p, q-1) 
               QUICKSORT(A, q+1, r) 
end QUICKSORT 

PARTITION(A, p, r) 
    x <- A[r] 
    i <- p-1 
    for j <- p to r-1 
        do if A[j] <= x 
                 then  i <- i+1 
                         exchange A[i]<->A[j] 
    exchange A[i+1]<->A[r] 
    return i+1 
end PARTITION 

JS code如下~

function swap(A,i,j){
   var ele = A[i];
   A[i] = A[j];
   A[j] = ele;
    
}
        
 function quick_sort(A,p,r){
     
     if(p < r)
     {
        var q = partition(A,p,r);
         
         quick_sort(A, p, q-1);
         quick_sort(A, q+1, r);
         
     }
     
 }

function partition(A,p,r){
     
     var x = A[r];
     var i = p - 1;
    
    for(var j = p; j <= r-1; j++)
    {
        if(A[j] <= x)
        {
            i = i+1;
            swap(A,i,j);
        }
    }
    
    swap(A,i+1,r);
    return i+1;
      
}
var list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];
quick_sort(list,0,list.length -1);

console.log(list)

以上是今天內容分享,明天在寫多一點QQQQ


上一篇
用Javascript征服演算法 (6-Quick Sort)
下一篇
用Javascript征服演算法 (7-Merge Sort)
系列文
用Javascript征服演算法10

1 則留言

0
fillano
iT邦超人 1 級 ‧ 2013-10-04 06:42:11

讚喜歡 .... 23:50 XD ...好險

我要留言

立即登入留言