[排序算法]合並排序[JS實現]

1.首先需要引入合並兩個已排序的表的算法 假設有一個數組A[1…m],p,q,r為它的三個索引,並有1⇐p⇐q<r⇐m。兩子數組A[p…q],A[q+1…r]各按升序排列,我們需要重新安排A中的元素的位置,使得子數組A[p…r]也按升序排列。這就是合並A[p…q]和A[q+1…r]的過程。合並算法是如下工作,使用兩個指針s和t,初始化時分別指向A[p]和A[q+1],再用空數組B[p…r]做暫存器。每一次比較元素A[s]和A[t],將小的元素添加到B,若相同則把A[s]添加進去。然後更新指針,若A[s]⇐A[t],則s++;反之則t++,當條件s=q+1或t=r+1成立時結束。在第一種情況下將數組A[t…r]中剩餘的元素添加到B,而另一種情況則將數組A[s…q]中剩餘的元素添加到B。最後把數組B[p…r]復制加A[p…r]。如下給出偽代碼:

 

/**********************************************************************************

算法:merge

輸入:數組A[1…m],p,q,r為它的三個索引,並有1<=p<=q<r<=m。兩子數組A[p…q],A[q+1…r]各按升序排列

輸出:合並兩個子數組A[p…q],A[q+1…r]的新數組A[1…m]

***********************************************************************************/

 

s = p; t = q + 1; k = p;

while(s <= q && t <= r) {

    if(A[s] <= A[t]) {

        B[k] = A[s];

        s++;

    } else {

        B[k] = A[t];

        t++;

    }

    k++;

}

if(s === q + 1) {

    B[k…r] = A[t…r];

} else {

    B[k…r] = A[s…q];

}

A[p…r] = B[p…r];

2.合並排序

 

/**********************************************************************************

算法:mergesort

輸入:A[1…n]

輸出:按非降序排列的數組A[1…n]

    mergesort(A, 1, n);

***********************************************************************************/

過程 mergesort(A, low, high)

    if(low < high) {

        mid = parseInt((low + high) / 2);

        mergesort(A, low, mid);

        mergesort(A, mid + 1, high);

        merge(A, low, mid, high);

    }

按上述合並排序的偽代碼給出合並排序的 JS實現版本:

 

function merge(arr, p, q, r) {

    var crr = [];

    var a = p, b = q + 1, k = p;

    while(a <= q && b <= r) {

        if(arr[a] <= arr[b]) {

            crr.push(arr[a]);

            a ++; 

        } else {

            crr.push(arr[b]);

            b ++; 

        }   

        k ++; 

    }   

 

    if(a === q + 1) {

        while(b <= r) {

            crr.push(arr[b]);

            b ++; 

        }   

    } else {

        while(a <= q) {

            crr.push(arr[a]);

            a ++; 

        }   

    }

 

    var i = 0, cl = crr.length;

    while(i < cl) {

        arr[p++] = crr[i++];

    }

 

    return arr;   

}

 

function mergesort(arr, low, high) {

    if(low === high) {

        return arr;

    } else if(high – low === 1) {

        if(arr[low] > arr[high]) {

            var temp = arr[low];

            arr[low] = arr[high];

            arr[high] = temp;

        }

 

        return arr;

    } else {

        var mid = parseInt((low+high)/2);

        arr = mergesort(arr, low, mid);

        arr = mergesort(arr, mid+1, high);

        return merge(arr, low, mid, high);

    }

}

 

// 示例

var test = [88, 32, 22, 32, 87, 88];

console.log(mergesort(test, 0, test.length – 1));

發佈留言