(递归版)合并排序

递归版的合并排序,时间复杂度为O(nlogn),空间复杂度为O(n+logn);

算法思想:

利用分而自治的思想,把排序分成两块,每块内部排序,再进行一次遍历排序即可,递归调用此过程即可。

主要代码:

void MergeSort(int *arr,int length){
    Msort(arr,arr,0,length-1); 
}
void Msort(int *arr1,int *arr2,int begin,int end){
    int arr3[10];
    int m;
    if(begin == end)
        arr2[begin] = arr1[end];
    else{
        m = (end + begin)/2;
        Msort(arr1,arr3,begin,m);
        Msort(arr1,arr3,m+1,end);
        sort(arr3,arr2,begin,m,end);
    }
}
void sort(int *arr3,int *arr1,int begin,int m,int end){
    int i=begin,j=m+1,k,h;
    for(k=i; i<=m && j<=end;k++){
        if(arr3[i] < arr3[j])
            arr1[k] = arr3[i++];
        else
            arr1[k] = arr3[j++];
    }
    if(i <= m){
        for(h=0; h<=m-i;h++)
            arr1[k+h] = arr3[i+h];
    }else{
        for(h=0; h<=end-j;h++)
            arr1[k+h] = arr3[j+h];
    }
}

全部代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5};
int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9};
int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0};
void copy(int *from,int *arr,int length);
void print(int *arr,int length);
void MergeSort(int *arr,int length);
void Msort(int *arr1,int *arr2,int begin,int end);
void sort(int *arr3,int *arr1,int begin,int m,int end);
int main(){
    clock_t start,end;
    int Arr[10];
    int i;
    copy(arrtest1,Arr,10);
    print(Arr,10);
    MergeSort(Arr,10);
    print(Arr,10);
    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest1,Arr,10);
        //print(Arr,10);
        MergeSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest2,Arr,10);
        //print(Arr,10);
        MergeSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest3,Arr,10);
        //print(Arr,10);
        MergeSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);
    
    getchar();
    return 0;
}
void MergeSort(int *arr,int length){
    Msort(arr,arr,0,length-1); 
}
void Msort(int *arr1,int *arr2,int begin,int end){
    int arr3[10];
    int m;
    if(begin == end)
        arr2[begin] = arr1[end];
    else{
        m = (end + begin)/2;
        Msort(arr1,arr3,begin,m);
        Msort(arr1,arr3,m+1,end);
        sort(arr3,arr2,begin,m,end);
    }
}
void sort(int *arr3,int *arr1,int begin,int m,int end){
    int i=begin,j=m+1,k,h;
    for(k=i; i<=m && j<=end;k++){
        if(arr3[i] < arr3[j])
            arr1[k] = arr3[i++];
        else
            arr1[k] = arr3[j++];
    }
    if(i <= m){
        for(h=0; h<=m-i;h++)
            arr1[k+h] = arr3[i+h];
    }else{
        for(h=0; h<=end-j;h++)
            arr1[k+h] = arr3[j+h];
    }
}
void copy(int *from,int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        arr[i] = from[i];
    }
}

void print(int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

运行示例:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏天天

DOM

1323
来自专栏编程思想之路

Android6.0源码分析之View(二)--measure Android6.0源码分析之View(一)

接着上一篇 Android6.0源码分析之View(一) 紧接着来学习view的measure,(注,开始写博客之后,很明显我的学习效率高多了,研究了俩星期硬是...

2689
来自专栏九彩拼盘的叨叨叨

使用 CSS 伪元素需要注意的

若不设置,则伪元素不会显示。如果不想设置 content 的内容,可以将内容设置为空。如:

692
来自专栏河湾欢儿的专栏

event事件对象

event: 事件对象,当一个事件发生的时候,和当前这个对象发生的这个事件有关的一些详细信息都会被临时保存到一个指定的地方-event对象,供我们在需要的时候调...

902
来自专栏james大数据架构

Jquery基本用法总结

选择器 $("#mydiv") 通过ID $("p#myp") 选择id=myp 的所有p元素(组合型) $(".mydiv") 通过 class="mydi...

1969
来自专栏flutter开发者

自定义View案例【LabelView】

在前面的几篇文章中我们介绍了Flutter中自定义view的用法,学习了canvas中常用的绘制方法,在这篇及以后的几篇文章中我会给大家写几个自定义View的例...

2122
来自专栏ytkah

css继承样式怎么控制?用选择器

  css样式继承性是指下级的样式属性会继承上级的属性,通俗点讲是儿子来继承父亲的属性,比如li会继承ul的属性。css继承原理是我们设置上级(父级)的CSS样...

4165
来自专栏姬小光

小鸡君の前端小姜汤【第014期】- 内联样式

在第003期我们讲过一点所谓样式,当时举的栗子是行内样式,只能写在元素的标签上,作为 style 属性的值存在的。这一期我们学习内联样式,或叫嵌入样式。

833
来自专栏HTML5学堂

详析设置样式的方法

上一期文章当中,小编与大家详细的总结了获取标签的方法,能够便于大家灵活的去获取网页中的标签。如果想具体了解详析获取标签,可以回复“获取标签”到“HTML5学堂”...

3227
来自专栏进击的君君的前端之路

CSS选择器知识点整理

1835

扫码关注云+社区

领取腾讯云代金券