文档章节

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

htq
 htq
发布于 2016/07/26 09:41
字数 1668
阅读 4
收藏 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
武汉
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

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

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

美的让人心动
04/16
0
0
sharding-jdbc源码分析—准备工作

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

飞哥-Javaer
05/03
0
0
【死磕Sharding-jdbc】—–路由&执行

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

飞哥-Javaer
05/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
2
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
7
3
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
4
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
2
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部