文档章节

归并排序

兔之
 兔之
发布于 2016/04/12 11:33
字数 184
阅读 23
收藏 3

归并排序是比较简单的分治算法。

a 是待排序数组,aux 是辅助数组。

public class MergeSort
{
    private static void merge(int[] a, int[] aux, int low, int mid, int high) 
    {
        for(int index = low; index <= high; index++)
            aux[index] = a[index];

        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++)
        {
            if (i > mid)              a[k] = aux[j++];
            else if (j > high)        a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else                      a[k] = aux[i++];
        }
    }

    private static void sort(int[] a, int[] aux, int low, int high)
    {
        if (high <= low) return;
        int mid = low + (high - low) / 2;
        sort(a, aux, low, mid);
        sort(a, aux, mid + 1, high);
        merge(a, aux, low, mid, high);
    }

    public static void main(String[] argv)
    {
        int[] array = {3, 8, 1, 5, 2, 10, 5 ,5, 6, 1};
        int[] aux;
        aux = new int[10];
        sort(array, aux, 0, 9);

        for(int i: array)
            System.out.println(i);
    }
}

参考

https://class.coursera.org/algs4partI-010/lecture/30

© 著作权归作者所有

共有 人打赏支持
上一篇: 另一种快速排序
下一篇: Shell 排序
兔之
粉丝 67
博文 247
码字总数 95896
作品 7
深圳
程序员
私信 提问

暂无文章

排序--二分插入排序

二分插入排序是对直接插入排序的一个优化,在排序--直接插入排序中已经分析过直接插入排序的最坏时间复杂度是平方级别的,二分插入排序则是通过二分查找对寻找插入位置进行了优化,在找到插入...

FAT_mt
9分钟前
0
0
Quora点赞过万!麻省理工5.0GPA十条学习技巧

美国版知乎Quora上有个问题是:顶尖学生如何学习。排名第一的答案已经赢得13.5K次点赞,我们翻译出来分享给大家。 MIT normally does not rank its students. So if you hear that someone g...

乔老哥
22分钟前
0
0
IOC的学习(1)

1.IOC理论概要 java中,一个对象A怎么才能调用对象B? 当一个对象的构建,需要多个其他对象时,对象和对象有复杂的构建关系。spring帮助我们维系对象的依赖关系,降低系统的实现成本,前提是...

杨健-YJ
34分钟前
5
0
Spring 的 getBean 方法源码解析

文本将从以下几个方面介绍 相关文章 FactoryBean 接口 BeanFactory 接口 BeanFactory 接口 和 FactoryBean 接口的区别 getBean 方法的源码解析 Spring 循环依赖的解决方式 相关文章 Spring 中...

TSMYK
37分钟前
3
0
PTA-基础编程题目集-7-14 求整数段和

给定两个整数A和B,输出从A到B的所有整数以及这些数的和。 输入格式: 输入在一行中给出2个整数A和B,其中−100≤A≤B≤100,其间以空格分隔。 输出格式: 首先顺序输出从A到B的所有整数,每...

niithub
44分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部