算法积累<2>归并排序非递归的实现

比眉伴天荒 2022-08-21 04:47 166阅读 0赞

递归算法虽然很方便但是相应的时间复杂度会提高  
所以在此贴上非递归的详细代码

/*
    * @Author: Katherine-qj
    * @Date:   2016-03-15 20:54:29
    * @Last Modified by:   Katherine-qj
    * @Last Modified time: 2016-03-15 21:30:05
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void Merge(int x[],int low,int mid, int high){
        int i = low, j = mid+1;//i指向第一个有序区的起始位置  j指向第二个有序区的起始位置
        int k = 0;//暂时存储的起始下标
        int *temp = (int*)malloc(sizeof(int)*5);
        while(i<=mid&&j<=high) {
       //判断两个有序部分是否比较到最后
            if(x[i]<=x[j])  //比较两个有序区的元素并放入临时数组中
                temp[k++]=x[i++];
            else
                temp[k++]=x[j++];
    
        }
        while(i<=mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
            temp[k++]=x[i++];
        while(j<=high)//同上
            temp[k++]=x[j++];
        for(i=low,k=0;i<=high;i++,k++)//将排好序的存回arr中low到high这区间
            x[i]=temp[k];
    
      free(temp);
    }
    
     void MassgerSort(int x[],int n){
        int low,mid,high;//low 起始位置 mid 第一有序`区结束位置 ，high 第二有序区结束位置
        int size=1;//每次合并的步数
        while(size<=n-1){
       //考虑到了奇数
             low=0;//第一有序区的第一元素
             while(low+size<=n-1){
       //
                mid=low+size-1;  //确定第一个有序区的结束位置
                high=mid+size;   //确定第二个有序区的结束位置
                if(high>n-1)//第二个序列个数不足步数
                    high=n-1; //就让结束位置在数组长度减一 也就是奇数最后会单独空出来
                Merge(x,low,mid,high);//调用归并子函数
                low=high+1;//下一次归并时第一个有序位置的结束位置
             }
             size*=2;//范围扩大一倍
        }
    }
    
    int main() {
        int x[] = {-1,0,4,3,9};
        MassgerSort(x,5);
        for(int i = 0;i<5;i++)
        {
            printf("%d  ",x[i]);
        }
    
        getchar();
        return 0;
    }