频道栏目
首页 > 程序开发 > web前端 > JavaScript > 正文
[排序算法]合并排序[JS实现]
2012-12-17 10:56:54           
收藏   我要投稿
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));

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:js调用php和php调用js的方法
下一篇:js 走马灯
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站