首页 > 编程语言 > 详细

归并排序

时间:2018-10-23 23:58:10      阅读:221      评论:0      收藏:0      [点我收藏+]

采用分而治之的方法。

 

 

 

#include <iostream>

using namespace std;
void dqMerge(int a[],int temp[],int low,int mid,int high);
             
void dqSort(int a[],int temp[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        dqSort(a,temp,low,mid); //对左部分进行归并排序
        dqSort(a,temp,mid+1,high); //对右部分进行归并排序
        dqMerge(a,temp,low,mid,high);
    }

}

void dqMerge(int a[],int temp[],int low,int mid,int high){
    int i=low; //左序列指针
    int j=mid+1; //右序列指针
    int t=0;
    while(i<=mid && j<=high){
        if(a[i]<a[j]){
            temp[t++]=a[i];
            i++;
        }else{
            temp[t++]=a[j];
            j++;
        }
    }
    for(;i<=mid;){
        temp[t++]=a[i++];
    }
    for(;j<=high;){
        temp[t++]=a[j++];
    }
    //将temp中的元素拷贝到原来数组中
    t=0;
    while(low<=high){
        a[low++]=temp[t++];
    }
}

int main() { 
    //归并排序    分而治之
    int a[]={8,71,1,33,24,61,94,22,5};
    int temp[9];
    dqSort(a,temp,0,8);
    for(int i=0;i<9;i++){
        cout<<temp[i]<<endl;
    }
    return 0;
}

结果:

1
5
8
22
24
33
61
71
94

 

归并排序

原文:https://www.cnblogs.com/logo-88/p/9840367.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!