旗下导航:搜·么
当前位置:网站首页 > JAVA教程 > 正文

如何利用java实现归并排序_JAVA教程,java,归并排序

作者:搜教程发布时间:2020-03-31分类:JAVA教程浏览:65评论:0


导读:java持久层面试题目(二)_JAVA教程java面试题:解释一下MyBatis中命名空间(namespace)的作用;MyBatis中的动态SQL是什么意思;JDBC编程有哪些不...

java持久层面试题目(二)_JAVA教程

java面试题:解释一下MyBatis中命名空间(namespace)的作用;MyBatis中的动态SQL是什么意思;JDBC编程有哪些不足之处,MyBatis是如何解决这些问题的。

什么是归并排序?

归并排序是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。

核心思想

将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。

java如何实现字符串压缩_JAVA教程

本文来自java快速入门栏目,文中为大家介绍了java实现字符串压缩的方法,具有一定的参考价值,希望可以帮助到大家。实现方法:1、使用双指针进行字符串压缩;2、使用HashMap进行字符串压缩。

(推荐教程:java快速入门)

实现代码:

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/1/13
 */
//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

运行结果:


相关视频教程推荐:java视频教程

以上就是如何利用java实现归并排序的详细内容,更多请关注ki4网其它相关文章!

java生成随机数的三种方法_JAVA教程

java生成随机数的三种方法如下:1、通过Math.random()方法实现;2、通过System.currentTimeMillis()方法获取毫秒数实现;3、通过Random类实现。

标签:java归并排序


欢迎 发表评论: