文档章节

归并排序

w
 wen123
发布于 10/21 16:00
字数 295
阅读 13
收藏 0

1.原理图

2.代码

public static void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//辅助数组
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针,k是存放指针

        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上

        //复制回原素组
        for (int i = left; i <=right; i++)
            a[i]=tmp[i];
    }

    public static void mergeSort(int [] a,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
    }

    public static void main(String[] args) {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        mergeSort(a, 0, a.length-1);
        System.out.println("排好序的数组:");
        for (int e : a)
            System.out.print(e+" ");
    }

 

© 著作权归作者所有

上一篇: 工厂方法模式
下一篇: 基数排序
w
粉丝 1
博文 34
码字总数 21185
作品 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
120
0
白话经典算法系列之五 归并排序的实现

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

长平狐
2012/12/10
63
0

没有更多内容

加载失败,请刷新页面

加载更多

前端的一些雕虫小技,从100%和滚动条说起

1、100%和滚动条 当我们在css中把html和body同时设为100%时,会出现滚动条 html, body { width: 100%; height: 100%; } 原因是html和b...

wphmoon
54分钟前
6
0
电力区块链应用案例【2019】

随着区块链技术的日益普及,出现了大量创业企业尝试使用区块链技术来解决能源与电力行业中存在的问题。在本文中,我们将介绍其中的三个能源区块链项目。 能源行业以价格不透明著称:消费者很...

汇智网教程
今天
8
0
聊聊rocketmq的adjustThreadPoolNumsThreshold

序 本文主要研究一下rocketmq的adjustThreadPoolNumsThreshold DefaultMQPushConsumer rocketmq-client-4.5.2-sources.jar!/org/apache/rocketmq/client/consumer/DefaultMQPushConsumer.ja......

go4it
今天
10
0
关于早起

早起是非常好的事情,但是像如果前一天睡得晚,或者第二天早上是非常冷的时候,那就不是很美好了。 但是本身早起是一件非常棒的事情,我记得我每次早起 如果不觉得困的话,世界是那么安静,脑...

T型人才追梦者
今天
7
0
Java输入输出

JDK中的InputStream/OutputStream构成了IO输入输出继承层次的基础。它们都是面向字节序列的,每次可以从序列中读入或者写出一个字节或者指定大小的字节数组。但是面向字节流的输入输出不便于...

ytuan996
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部