欢迎来到Doc100.Net免费学习资源知识分享平台!
您的位置:首页 > 程序异常 >

原处归并排序 merge sort in place

更新时间: 2014-05-14 08:20:17 责任编辑: Author_N2

 

原地归并排序 Merge Sort in place

师姐给身边的某小朋友 出了道题:O(1)空间复杂度实现归并排序

在草纸上笔画了一下,20分钟编码调试

思路是:merge的时候,merge(arr,  l,  m, n)在 l m+1处放 i j指标,

循环i直到m    若arr[j]>arr[i]  则右移 i-m的元素 j++  m++ 

简单修改 使用模板 就可以扩展到多种arr类型,以下简单以数组为例




#include <iostream>
using namespace std;

void merge(int* arr, int l, int m, int n){
    int i=l, j=m+1;
    while(i<=m && j<=n){
        if(arr[i]>arr[j]){//向右平移左半部分
            int tmp = arr[j];
            for(int t=j; t>i; t--) 
               arr[t]=arr[t-1];
            arr[i] = tmp;
            ++m;
            ++j;
        }
        ++i;
    }
}

void mergeSort(int* arr, int l, int n){
    if(l<n){
        int m = (l+n)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, n);
        merge(arr, l, m, n);
    }
}

int main(){
    int a[9] = {2, 3, 9, 3, 1, 4, 6, 8, 10};
    mergeSort(a,0,8);
    for (int i=0; i<=8; ++i)
         cout<<a[i]<<" ";
    cout<<endl;
}






上一篇:上一篇
下一篇:下一篇

 

随机推荐程序问答结果

 

 

如对文章有任何疑问请提交到问题反馈,或者您对内容不满意,请您反馈给我们DOC100.NET论坛发贴求解。
DOC100.NET资源网,机器学习分类整理更新日期::2014-05-14 08:20:17
如需转载,请注明文章出处和来源网址:http://www.doc100.net/bugs/t/220796/
本文WWW.DOC100.NET DOC100.NET版权所有。