当前位置:编程学习 > C/C++ >>

原地归并排序 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;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,