`
jiangshuiy
  • 浏览: 340060 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

java类库中Arrays的排序算法探析(Object与泛型类型)

 
阅读更多

     在Arrays中关于基本类型如int,long,float等都在java类库中Arrays的排序算法探析(基础类型)做了一定分析,本篇主要关于Object类型的sort,以及之后的泛型sort。

 

直接查看源码中的方法定义及实现:

 

    public static void sort(Object[] a) {
        Object[] aux = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }


    public static void sort(Object[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);//验证参数是否合法
	Object[] aux = copyOfRange(a, fromIndex, toIndex);//创建待排序数组临时存储区
        mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
    }

 

由上可见,两个重载方法的具体实现指向了同一个具体实现,应该是个私有方法:

 

/**
     * Src is the source array that starts at index 0
     * Dest is the (possibly larger) array destination with a possible offset
     * low is the index in dest to start sorting
     * high is the end index in dest to end sorting
     * off is the offset to generate corresponding low, high in src
     */
    private static void mergeSort(Object[] src,
				  Object[] dest,
				  int low,
				  int high,
				  int off) {
	int length = high - low;

	// Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
			 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }
 

        当然,如果能直接看代码一眼就完全明白的话,那到此就可以为止了。

先理一下流程:

1 如果待排序的数组大小小于设置的插入排序阈值,则直接采用插入排序解决;

2 如果不满足1,则将其一分为二,递归处理;这样经过多次递归,其实最终还是分段采用插入排序将其拆分为了N个有序的段;

3 到了这里,前面是多个分别有序的段,这里需要将其逐一连接起来,使其更大长度上有序,这一部分展示的就是:如果前一段的最后一个值(也就是前一段的最大值)小于紧挨着的后一个段的第一个值(也就是这一段的最小值),则这两段总体是有序的;

4 如果没有3那种理想状态,则需要我们来处理,这里处理的思想就是:前后两段逐一开始比较,小的先放,依次放第二小的,直到两段都为空;

5 3或4逐级返回,最终构成一个整体的有序数组。

 

再说泛型的排序:

 

 public static <T> void sort(T[] a, Comparator<? super T> c) {
	T[] aux = (T[])a.clone();
        if (c==null)
            mergeSort(aux, a, 0, a.length, 0);
        else
            mergeSort(aux, a, 0, a.length, 0, c);
    }

public static <T> void sort(T[] a, int fromIndex, int toIndex,
				Comparator<? super T> c) {
        rangeCheck(a.length, fromIndex, toIndex);
	T[] aux = (T[])copyOfRange(a, fromIndex, toIndex);
        if (c==null)
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
        else
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
    }

 可以看出来,泛型排序的处理过程几乎和对象数组的一模一样,值得注意的是,如果Comparator为null,则使用默认的Comparable接口的自然序。下面看具体调用的实现方法:

 

private static void mergeSort(Object[] src,
				  Object[] dest,
				  int low, int high, int off,
				  Comparator c) {
	int length = high - low;

	// Insertion sort on smallest arrays
	if (length < INSERTIONSORT_THRESHOLD) {
	    for (int i=low; i<high; i++)
		for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
		    swap(dest, j, j-1);
	    return;
	}

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid-1], src[mid]) <= 0) {
           System.arraycopy(src, low, dest, destLow, length);
           return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

 仔细看来,无Comparator的实现和对象数组的事项没有任何差别,具有Comparator的也仅仅在比较使采取的是compare方法来决定数组顺序。

 

这个实现值得学习的有几点:

1 小规模的比较采取的是插入排序,这就避免了递归到一个数组只有一个元素那种情况,在小规模情况下,插入排序实现简单,效率也还可以(类库中设置的是7);

2 在相邻两段的连接时,如果发现两个段的连接处构成正确顺序,则直接返回,减少了需要逐个比较元素重新插入一遍带来的性能影响;

3 无符号位运算取中间值,代替/;

4 对外接口与对内实现的独立,对外可能有多个接口,但内部实现其实是一样的,这样非常方便于后续调整和性能优化;

总体感觉就是这些方法的实现极大的优化了性能,并且给后续调整留下了空间,便于维护。

 

唯一感到有点不足的就是:

就是临时变量实在是有点多,刚开始难以理解~

 

 

分享到:
评论

相关推荐

    java编写的插入排序算法

    ### Java编写的插入排序算法 #### 一、插入排序算法基本思想 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在...

    最快的排序算法 java最快的排序-在Java中对列表进行排序的最快方法,排序算法数据结构

    在 Java 中,还有其他的排序算法,如 Arrays.sort() 方法,该方法使用的排序算法是快速排序,它具有高效的性能,但不稳定排序算法。 在实际应用中,选择合适的排序算法取决于具体的应用场景。例如,在有大量元素...

    Java直接插入排序算法源码

    总的来说,Java中的直接插入排序算法是一个直观易懂的排序方法,虽然在效率上不敌更高级的排序算法,但它在理解和实现上相对简单,对于初学者来说是很好的学习材料。通过阅读和实践这个源代码,你可以深入理解排序...

    java 8种排序算法

    在编程领域,排序算法是数据结构与算法学习中的重要组成部分,尤其在Java中,掌握各种排序算法对于优化程序性能至关重要。下面将详细讲解标题中提到的八种排序算法及其原理和实现。 1. **直接插入排序(直接选择...

    ECharts - Java类库.zip

    在这个压缩包中,包含的 "ECharts-master" 文件可能是一个仓库,包含了 Java 版本的 ECharts 实现或者是一个用于与 ECharts 交互的 Java 工具包。 1. **ECharts 概述** ECharts 是百度公司开发的一个数据可视化库...

    Java排序算法 Java排序算法.rar

    在编程领域,排序算法是计算机科学中的核心...在Java中,可以使用内置的`Arrays.sort()`或`Collections.sort()`方法,它们底层实现了高效的排序算法,如TimSort,一种混合排序算法,具有稳定性且在实际应用中表现出色。

    Java各种排序算法代码

    在编程领域,排序算法是计算机科学中的核心概念,尤其是在Java这样的高级编程语言中。Java提供了丰富的内置库函数,如Arrays.sort(),可以方便地对数组进行排序。然而,理解并掌握各种排序算法对于优化程序性能、...

    8中排序算法(java实现)

    以下是关于标题"8种排序算法(Java实现)"及其描述中提到的排序算法的详细讲解: 1. **插入排序**: - **直接插入排序**:基本思想是从第二个元素开始,逐个与前面已排序的元素比较,找到合适的位置插入,保持已...

    Java排序算法包 支持自定义比较条件

    - 在Java中,`java.util.Arrays`类提供了内置的排序方法,如`Arrays.sort()`,可以对基本类型数组和对象数组进行排序。 2. **自定义比较器(Comparator)**: - 当内置的排序规则不能满足需求时,可以使用`...

    java四大排序算法总结.zip

    同时,现代Java库(如`Arrays.sort()`方法)通常使用更高级的排序算法,如TimSort,它结合了稳定的排序和插入排序的特性,能在大多数情况下提供良好的性能。 总的来说,理解和掌握这些基础排序算法是每个Java程序员...

    Java 排序算法大结合

    在Java编程语言中,排序算法是数据结构与算法领域中的重要组成部分。这些算法用于将一组数值按照特定顺序(通常是升序或降序)排列。在提供的文件中,我们可以看到几个经典的排序算法的Java实现,包括插入排序...

    基于JAVA语言的常见排序算法分析与比较.zip

    在计算机科学领域,排序算法是数据结构和算法分析的重要组成部分,...在"基于JAVA语言的常见排序算法分析与比较.pdf"文件中,你将找到更详细的算法实现、性能测试和可视化示例,这将对学习和掌握Java排序算法大有裨益。

    java实现常见的集中排序算法

    在Java中,我们可以使用ArrayUtils、Collections等工具类进行排序,例如`Arrays.sort()`和`Collections.sort()`,它们内部使用了高效的排序算法,如TimSort,是混合排序算法,结合了插入排序和归并排序的优点,对小...

    Java排序算法,常用算法集代码

    在编程领域,排序算法是计算机科学的基础之一,尤其在Java编程中,理解并掌握各种排序算法至关重要。这个压缩包文件提供了Java实现的常见排序算法,对于初学者和有经验的开发者来说,都是一个宝贵的资源。 首先,让...

    常见的八大排序算法及其JAVA实现

    在编程领域,排序算法是数据结构与算法学习中的基础部分,它对于理解计算机如何处理数据至关重要。本篇文章将深入探讨八大常见的排序算法,并提供它们在Java语言中的具体实现。这八大排序算法包括冒泡排序、选择排序...

    Java2 类库详解

    1. **核心类库**:这是Java2类库的基础,包括了Object、String、Arrays等基础类,以及Math、System、Thread等核心功能类。这些类提供了基本的数据类型操作、异常处理、线程管理等功能。 2. **集合框架**:Java2类库...

    java sort排序算法实例完整代码

    这个算法在Java中主要体现在`java.util.Arrays`和`java.util.Collections`两个类中,提供了对数组和集合的排序功能。下面我们将深入探讨`sort`排序算法的工作原理、性能分析以及实际应用示例。 ### 1. `Arrays.sort...

    031112_【第11章:Java常用类库】_Arrays笔记

    031112_【第11章:Java常用类库】_Arrays笔记

    常用排序算法分析与实现(Java版)

    ### 常用排序算法分析与实现(Java版) #### 插入排序 **1. 直接插入排序** 直接插入排序是一种简单的排序方法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并...

Global site tag (gtag.js) - Google Analytics