专栏首页算法之名归并排序算法 顶

归并排序算法 顶

归并排序算法的时间复杂度为O(NlogN)

合并排序算法就是把多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则称为二路合并。

/**
 * Created by Administrator on 2018-04-05.
 */
public class Merge {
    static final int SIZE = 15;
    static void mergeOne(int a[],int b[],int n,int len) {
        int i,j,k,s,e;
        s = 0;
        while (s + len < n) {
            e = s + 2 * len - 1;
            if (e >= n) {
                e = n - 1;
            }
            k = s;
            i = s;
            j = s + len;
            while (i < s + len && j <= e) {
                if (a[i] <= a[j]) {
                    b[k++] = a[i++];
                }else {
                    b[k++] = a[j++];
                }
            }
            while (i < s + len) {
                b[k++] = a[i++];
            }
            while (j <= e) {
                b[k++] = a[j++];
            }
            s = e + 1;
        }
        if (s < n) {
            for (;s < n;s++) {
                b[s] = a[s];
            }
        }
    }
    static void mergeSort(int a[],int n) {
        int h,count,len,f;
        count = 0;
        len = 1;
        f = 0;
        int[] p = new int[n];
        while (len < n) {
            if (f == 1) {
                mergeOne(p,a,n,len);
            }else {
                mergeOne(a,p,n,len);
            }
            len = len * 2;
            f = 1 - f;
            count++;
            System.out.printf("第" + count + "步排序结果:");
            for (h = 0;h < SIZE;h++) {
                System.out.printf(" " + a[h]);
            }
            System.out.printf("\n");
            if (f == 1) {
                for (h = 0;h < n;h++) {
                    a[h]  = p[h];
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] shuzu = new int[SIZE];
        int i;
        for (i = 0;i < SIZE;i++) {
            shuzu[i] = (int)(100 + Math.random() * (100 + 1));
        }
        System.out.print("排序前的数组为:\n");
        for (i = 0;i < SIZE;i++) {
            System.out.print(shuzu[i] + " ");
        }
        System.out.print("\n");
        mergeSort(shuzu,SIZE);
        System.out.print("排序后的数组为:\n");
        for (i = 0;i < SIZE;i++) {
            System.out.print(shuzu[i] + " ");
        }
        System.out.print("\n");
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 无锁CAS整理

    所有的锁都是悲观的,他们总是假设每一次的临界区操作会产生冲突,如果有多个线程同时需要访问临界区资源,就宁可牺牲性能让线程进行等待,所以说锁会阻塞线程执行.而无锁...

    算法之名
  • elasticsearch的restful API和Java API

    本人现在使用的是elasticsearch 5.2.1的,服务器IP为192.168.5.182.所以在Java API和jar包中会有所不同.

    算法之名
  • 数据结构整理 顶

    DefaultArray(data=[66,99,88], size=3 DefaultArray(data=[100,66,99,11], size=4 ...

    算法之名
  • 《数据结构》 定长顺序串常用操作代码集合

    代码来自老师上课使用的ppt或者课本 /*定长顺序串*/ #define MAXLEN 40 typedef struct { char ch[M...

    Steve Wang
  • 基础算法系列之排序算法-2.冒泡排序

    上篇文章给大家讲述了二分查找算法,现在让我们来一起学习另一个基础算法——冒泡排序算法。它是一个排序算法,可以将一个无序的序列排成有序。它将会是我们以后...

    ACM算法日常
  • 用x种方式求第n项斐波那契数,99%的人只会第一种

    斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖...

    C you again 的博客
  • 用x种方式求第n项斐波那契数,99%的人只会第一种

    大家好啊,我们又见面了。听说有人想学数据结构与算法却不知道从何下手?那你就认真看完本篇文章,或许能从中找到方法与技巧。

    C you again
  • LeetCode 200. Number of Islands(并查集)

    ShenduCC
  • Leetcode 547. Friend Circles

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • P1967 货车运输

    题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想...

    attack

扫码关注云+社区

领取腾讯云代金券