文档章节

【java集合框架源码剖析系列】java源码剖析之java集合中的折半插入排序算法

htq
 htq
发布于 2016/07/26 09:41
字数 1668
阅读 3
收藏 0
点赞 0
评论 0

注:关于排序算法,博主写过【数据结构排序算法系列】数据结构八大排序算法,基本上把所有的排序算法都详细的讲解过,而之所以单独将java集合中的排序算法拿出来讲解,是因为在阿里巴巴内推面试的时候面试官问过我,让我说说java集合框架中用的哪种排序算法,当时回答错了,(关于面试详细过程请参看:【阿里内推一面】记我人生的处女面)面试结束后看了一下java源码,用的是折半插入排序算法,本来早就打算写此博客,但是因为准备鹅厂的在线考试,而鹅厂在我心中的地位是最高的,为了准备鹅厂的在线考试,自己基本上把所有事情都搁置起来了,把全部的精力都投入到复习中去了,所以一直没动手写。既然java的天才程序员都采用了折半插入排序,那么“此人必有过人之处”,因此得好好了解一下折半插入排序。

我们先从c语言中的折半插入排序算法看起,在此基础之上在来看java集合框架中的源码。

#include<iostream>
using namespace std;
const int len=7;

void binaryInsertSort(int * array,int len)
{
	for(int i=1;i<len;i++)//与普通的排序一样,外层for循环用来控制排序趟数
	{
		int x=array[i];
		int low=0,high=i-1;//low与high的初始化很重要,因为i从1开始,所以low=0,high=i-1,这样就能保证数组中的每一个
		//元素参与排序,教材上的low=1是错误的,因为教材上将数组中的第0位作为监视哨而未参与排序。
		while(low<=high)//寻找待插入的位置
		{
			int mid=(low+high)/2;
			if(x<array[mid])
				high=mid-1; 
			else
				low=mid+1;
		}
		for(int j=i-1;j>=low;j--)//将记录向后移动
		{
			array[j+1]=array[j];
		}
		array[low]=x;//插入记录
	}
}
int main()
{
	int a[len]={7,0,4,5,1,2,3};
	 binaryInsertSort(a,len);
	 for(int i=0;i<len;i++)
		 cout<<a[i]<<' ';
	 cout<<endl;
}
可以看到折半插入排序的思想是基于折半查找的,即对有序表进行折半查找,其性能较好,所以可将折半查找的思路运用到排序中一个数组中的元素虽然刚开始不是有序的,但是可以通过折半查找的同时构造有序表,即折半插入排序算法即是通过折半查找构造有序序列,然后在已构造的部分有序序列中运用折半查找插入元素,最终直至整个表排好序为止。

程序运行结果如下:

经过上述c语言代码的讲解,下面我们来看一下java的那些天才设计者们是如何java实现该算法的以及分析一个为何那些天才们看上的不是我们普通程序员最喜欢的快速排序而是折半插入排序。

下面是java中TimSort类中的sort源码,而java集合中的类调用的sort方法最终会调用它

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                         T[] work, int workBase, int workLen) {
        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
            binarySort(a, lo, hi, lo + initRunLen, c);
            return;
        }
可以看到在TimSort类中最终会调用binarySort方法,即折半插入排序,我们来看一下其源码:

/**
     * Sorts the specified portion of the specified array using a binary
     * insertion sort.  This is the best method for sorting small numbers
     * of elements.  It requires O(n log n) compares, but O(n^2) data
     * movement (worst case).
     *
     * If the initial part of the specified range is already sorted,
     * this method can take advantage of it: the method assumes that the
     * elements from index {@code lo}, inclusive, to {@code start},
     * exclusive are already sorted.
     *
     * @param a the array in which a range is to be sorted
     * @param lo the index of the first element in the range to be sorted
     * @param hi the index after the last element in the range to be sorted
     * @param start the index of the first element in the range that is
     *        not already known to be sorted ({@code lo <= start <= hi})
     * @param c comparator to used for the sort
     */
    @SuppressWarnings("fallthrough")
    private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                       Comparator<? super T> c) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            T pivot = a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            int left = lo;
            int right = start;
            assert left <= right;
            /*
             * Invariants:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (c.compare(pivot, a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
            int n = start - left;  // The number of elements to move
            // Switch is just an optimization for arraycopy in default case
            switch (n) {
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
    }
可以看到其实其代码一点也不复杂,与我们上面分析的c语言代码几乎完全相同,只不过它所排序的元素不再是简单的int型,比较规则也不再是简单的比较数的大小,而是通过java中的Comparator接口来规定的,可以看到注释远远多于代码量,一方面这是因为那些天才们用其高超的艺术大大的简化了代码,另一方面也是为了解释关于选择折半插入排序的原因:

/**
     * Sorts the specified portion of the specified array using a binary
     * insertion sort.  This is the best method for sorting small numbers
     * of elements.  It requires O(n log n) compares, but O(n^2) data
     * movement (worst case).



/*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
从我截取的这两段注释来看,可以知道:
1折半插入排序是最好的算法对于排序小数量的元素This is the best method for sorting small numbers of elements. 

2它只需要O(nlogn)的比较次数,但是其移动次数仍然为 O(n^2)。It requires O(n log n) compares, but O(n^2) data movement (worst case).

3它是稳定的排序算法。that's why this sort is stable.而快速排序不是稳定的排序。

分析到这我们就可以知道为何会选择折半插入排序,其中1和3是最主要的原因。




本文转载自:http://blog.csdn.net/htq__/article/details/51057207

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
sharding-jdbc源码分析—准备工作

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/7831817c1da8 接下来对sharding-jdbc源码的分析基于tag为源码,根据sharding-jdbc Features深入学习sharding-jdbc的几个主要特性...

飞哥-Javaer ⋅ 05/03 ⋅ 0

Java开发者不会这些永远都只能是三流程序员,细数一下你是不是?

源码系列 手写spring mvc框架 基于Spring JDBC手写ORM框架 实现自己的MyBatis Spring AOP实战之源码分析 Spring IOC高级特性应用分析 ORM框架底层实现原理剖析 手写Spring MVC框架实现 手把手...

美的让人心动 ⋅ 04/16 ⋅ 0

【死磕Sharding-jdbc】—–路由&执行

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/09efada2d086 继续以模块中的为基础,剖析分库分表简单查询SQL实现--,即如何执行简单的查询SQL,接下来的分析以执行SQL语句为例...

飞哥-Javaer ⋅ 05/03 ⋅ 0

【目录导航】JAVA零基础进阶之路

【JAVA零基础入门系列】(已完结)导航目录 Day1 开发环境搭建 Day2 Java集成开发环境IDEA Day3 Java基本数据类型 Day4 变量与常量 Day5 Java中的运算符 Day6 Java字符串 Day7 Java输入与输出...

MFrank ⋅ 今天 ⋅ 0

重磅!Java 性能监控调试工具 JMC 宣布开源

JRockit JVM 创始人之一、Oracle Java 产品组成员 Marcus Hirt 昨日在其博客上宣布,Java Mission Control(JMC)的源代码已正式开源。 JMC 是源自 JRockit JVM 的一套监控和管理工具,Oracl...

王练 ⋅ 05/07 ⋅ 6

【小马哥】Spring Cloud系列讲座

这里为大家推荐一个不错的Spring Cloud系列讲座,讲师介绍如下: 小马哥,阿里巴巴技术专家,从事十余年Java EE 开发,国内微服务技术讲师。目前主要负责微服务技术推广、架构设计、基础设施...

杜琪 ⋅ 03/02 ⋅ 0

Java编程基础知识点和技术点归纳

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/23 ⋅ 0

[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin ⋅ 05/25 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb ⋅ 05/08 ⋅ 0

sharding-jdbc源码解析全集

sharding-jdbc源码解析之词法解析 sharding源码解析之api分析 sharding-jdbc源码解析之spring集成 sharding-jdbc源码解析之spring集成分片构造实现 sharding-jdbc源码解析之jdbc规范重写 sh...

天河2018 ⋅ 05/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

NFS介绍 NFS服务端安装配置 NFS配置选项

NFS介绍 NFS是Network File System的缩写;这个文件系统是基于网路层面,通过网络层面实现数据同步 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netapp公司参与并主导...

lyy549745 ⋅ 33分钟前 ⋅ 0

Spring AOP 源码分析 - 筛选合适的通知器

1.简介 从本篇文章开始,我将会对 Spring AOP 部分的源码进行分析。本文是 Spring AOP 源码分析系列文章的第二篇,本文主要分析 Spring AOP 是如何为目标 bean 筛选出合适的通知器(Advisor...

java高级架构牛人 ⋅ 55分钟前 ⋅ 0

HTML-标签手册

标签 描述 <!--...--> 定义注释。 <!DOCTYPE> 定义文档类型。 <a> 定义锚。超链接 <abbr> 定义缩写。 <acronym> 定义只取首字母的缩写。 <address> 定义文档作者或拥有者的联系信息。 <apple......

ZHAO_JH ⋅ 57分钟前 ⋅ 0

SylixOS在t_main中使用硬浮点方法

问题描述 在某些使用场景中,应用程序不使用动态加载的方式执行,而是跟随BSP在 t_main 线程中启动,此时应用代码是跟随 BSP 进行编译的。由于 BSP 默认使用软浮点,所以会导致应用代码中的浮...

zhywxyy ⋅ 今天 ⋅ 0

JsBridge原理分析

看了这个Github代码 https://github.com/lzyzsd/JsBridge,想起N年前比较火的Hybrid方案,想看看现在跨平台调用实现有什么新的实现方式。代码看下来之后发现确实有点独特之处,这里先把核心的...

Kingguary ⋅ 今天 ⋅ 0

Intellij IDEA神器常用技巧五-真正常用快捷键(收藏级)

如果你觉得前面几篇博文太啰嗦,下面是博主多年使用Intellij IDEA真正常用快捷键,建议收藏!!! sout,System.out.println()快捷键 fori,for循环快捷键 psvm,main方法快捷键 Alt+Home,导...

Mkeeper ⋅ 今天 ⋅ 0

Java 静态代码分析工具简要分析与使用

本文首先介绍了静态代码分析的基本概念及主要技术,随后分别介绍了现有 4 种主流 Java 静态代码分析工具 (Checkstyle,FindBugs,PMD,Jtest),最后从功能、特性等方面对它们进行分析和比较,...

Oo若离oO ⋅ 今天 ⋅ 0

SpringBoot自动配置小记

spring-boot项目的特色就在于它的自动配置,自动配置就是开箱即用的本源。 不过支持一个子项目的自动配置,往往比较复杂,无论是sping自己的项目,还是第三方的,都是如此。刚接触会有点乱乱...

大_于 ⋅ 今天 ⋅ 0

React jsx 中写更优雅、直观的条件运算符

在这篇文字中我学到了很多知识,同时结合工作中的一些经验也在思考一些东西。比如条件运算符 Conditional Operator condition ? expr_if_true : expr_if_false 在jsx中书写条件语句我们经常都...

开源中国最帅没有之一 ⋅ 今天 ⋅ 0

vim编辑模式与命令模式

5.5 进入编辑模式 从编辑模式返回一般模式“Esc” 5.6 vim命令模式 命令 :“nohl”=no high light 无高亮,取消内容中高亮标记 "x":保存退出,和wq的区别是,当进入一个文件未进行编辑时,使...

弓正 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部