文档章节

归并排序

兔之
 兔之
发布于 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

© 著作权归作者所有

共有 人打赏支持
兔之
粉丝 66
博文 247
码字总数 95896
作品 7
深圳
程序员

暂无文章

Maven 项目中依赖的搜索顺序

ettings_mirror 的优先级高于 central settings_profile_repo 优先级高于 settings_mirror settings_profile_repo 优先级高于 pom_repositories settings_profile_repo 优先级高于 pom_prof......

xingyu4j
30分钟前
2
0
改变maven项目的名称

pom.xml <groupId>com.soft.xxx</groupId><artifactId>xxx</artifactId><packaging>war</packaging><version>0.0.1-SNAPSHOT</version><name>xxx Maven Webapp</name><build>......

1713716445
32分钟前
2
0
windows下按照RabbitMQ

rabbitMQ是一个在AMQP协议标准基础上完整的,可服用的企业消息系统。它遵循Mozilla Public License开源协议,采用 Erlang 实现的工业级的消息队列(MQ)服务器,Rabbit MQ 是建立在Erlang OTP平...

zhaochaochao
32分钟前
2
0
10个PHP比特币开源项目

如果你是一个Phper,如果你希望学习区块链,那么本文列出的10个开源的Php比特币项目,将有助于你了解在自己的应用中如何加入对比特币的支持。 如果你希望快速掌握使用Php对接比特币钱包的方法...

笔阁
39分钟前
23
0
MyBatis级联探讨

数据模型 <?xml version="1.0" encoding="UTF-8" ?><!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd"><mapper name......

职业搬砖20年
43分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部