合并排序非递归实现总结

水深无声 2022-03-02 13:43 166阅读 0赞

合并排序在众多排序算法中算是比较稳定的排序算法，时间复杂度为nlogn，采取分治的思想，可以说是比较高效的的排序算法。  
开始将长度为len的数组分为长度为1的len个子序列，开始作如下按照从小到大顺序合并：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]  
直到合并成一个长度和正数组长度相等的子序列即可。

--------------------

下面是代码的非递归实现实现：

#include <iostream>
    #include<vector>
    using namespace std ;
    
    
    void merge(vector<int>&ls, vector<int>&tmp, int l, int m, int r) {
        
        int left = l ;
        int k = l ;
        int mid = m+1 ;
        //将当前段的元素转移到ｔｍｐ数组中相应位置
        while(left<=m&&mid<=r) {
        
            
            if(ls[left] > ls[mid]) {
        
                tmp[k++] = ls[mid++];
            }
            else {
        
                tmp[k++] = ls[left++] ;
            }   
        }
    
        if(left <= m) {
        
            while(left <= m) {
        
                tmp[k++] = ls[left++] ;
            }
        }
        else {
        
            while(mid<=r) {
        
                tmp[k++] = ls[mid++] ;
            }
        }       
    }
    
    void mergePass(vector<int>&ls, vector<int>&tmp, int s, int n) {
        
        int i= 0;   
    
        while(i<=n-2*s) {
        
            //将前一组长度为s个元素合并
            merge(ls, tmp, i, i+s-1, i+2*s-1) ;
            i = i+2*s ;
        }
        //剩余的元素少于3s的话
        if(i+s<n) {
        
            merge(ls, tmp, i, i+s-1, n-1) ;
        }
    
        else {
        
            for(int k=i; k<=n-1; k++) {
        
                tmp[k] = ls[k] ;
            }
        }
    }
    
    //合并排序非递归
    void mergeSort(vector<int>&ls) {
           
        vector<int>tmp =ls ;
        int s= 1 ;
        int len = ls.size();
        while(s<len) {
        
            mergePass(ls, tmp, s, len) ;
            s+=s ;
            mergePass(tmp, ls, s, len) ;
            s+=s ;
        }
    }
    
    int main()
    {
        
        vector<int>ls ;
        while(1) {
        
            int n ;
            cin >> n ;
            if(n == -1) {
        
                break ;
            }
            ls.push_back(n) ;
        }
    
        mergeSort(ls) ;
        for(int i=0; i<(int)ls.size(); i++) {
        
            cout << ls[i] <<"  "  ;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]: /images/20220302/19d6e69f09b64d35a58c6716ab0efaf0.png