文档章节

归并排序

老汉-憨憨
 老汉-憨憨
发布于 2017/03/17 17:17
字数 221
阅读 7
收藏 0
#include <stdio.h>
#include <stdlib.h>


void printArr(int arr[], int len)
{
    int i;
    for (i = 0; i < len; i++) {
        printf("%d\t", arr[i]);
    }
    printf("\n");
}

void merge(int arr[], int l, int m, int r)
{
   int n1 = m - l + 1; 
   int n2 = r - m;
    
   int L[n1], R[n2];
   int i = 0, j = 0;

   for (i = 0; i < n1; i++) {
       L[i] = arr[l + i];
   }
    
   for (j = 0; j < n2; j++) {
       R[j] = arr[m + j + 1];
   }
   
   i = j = 0;
   int k = l;
   while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
    k++;     
   }
   
   while (i < n1)  {
        arr[k] = L[i];
        i++;
        k++; 
   }

   while (j < n2) {
       arr[k] = R[j];
       j++;
       k++;
   }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}



int main(int argc, char *argv[])
{
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int len = sizeof(arr)/sizeof(int);
    
    printf("Raw Arr[] = \t");
    printArr(arr, len);

    mergeSort(arr, 0, len - 1);

    printf("Sort Arr[] = \t");
    printArr(arr, len);
    return 0;
}

 

输出结果:

Raw Arr[] = 	38	27	43	3	9	82	10	
Sort Arr[] = 	3	9	10	27	38	43	82	

 

© 著作权归作者所有

上一篇: 堆排序
下一篇: 插入排序
老汉-憨憨
粉丝 20
博文 322
码字总数 68382
作品 0
深圳
程序员
私信 提问
排序算法之归并排序

一、分治法的思想 把复杂的问题分解,再分解,成为很小的问题,解决这些小问题之后合并,再合并。这就是分治法的思想。 通常分治法是递归的。 二、归并排序 归并排序就是利用分治法,把无序的...

Lubby
2015/10/08
102
0
java泛型中使用的排序算法——归并排序及分析

一、引言 我们知道,java中泛型排序使用归并排序或TimSort。归并排序以O(NlogN)最坏时间运行,下面我们分析归并排序过程及分析证明时间复杂度;也会简述为什么java选择归并排序作为泛型的排序...

9龙
04/29
0
0
排序算法(7) -- 归并排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87947485 一、前言 归并排序是建立...

dby_freedom
02/26
0
0
归并排序——“递归+合并”(Java版)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

十一11
2016/04/07
87
0
白话经典算法系列之五 归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

长平狐
2012/12/10
61
0

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL 11.3 locking

rudi
今天
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
11
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
4
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
9
0
队列-链式(c/c++实现)

队列是在线性表功能稍作修改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。作用就是通过伟大的程序员来实现算法解决现实生活...

白客C
今天
81
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部