Java 容器 & 泛型：四、Colletions.sort 和 Arrays.sort 的算法

一、Colletions和Arrays

Collentions 此类完全是服务容器的”包装器“。提供了一些操作或者返回容器的静态方法。而Arrays是用来操作数组的各种方法。其中它们的联系在于其中的Sort方法，也就是这次博客的主题。

 

二、插入，快速、归并基本算法

① 插入排序

{a1}，{a2，a3，a4，…，an}}

{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}

…

{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

原理及记忆方法：每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。这通俗的是找座位思想。Java版实现如下


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

import java.util.Arrays;

 

public class InsertionSort

{

    public static void main(String[] args)

    {

        int[] intA = new int[]{2,1,3,4,6,7,5};

        System.out.println(Arrays.toString(intA));

        insertionSort(intA);

        System.out.println(Arrays.toString(intA));

    }

     

    public static void insertionSort(int[] a)

    {

        int p,right;

        int temp;

        for (p = 0; p < a.length; p++)

        {

            temp = a[p];

            /**

             * 将a[p]值往左侧有序列比较，插入。

             */

            for (right = p; right > 0 && a[right-1] > temp ; right--)

                a[right] = a[right-1];// 置换

            a[right] = temp;

        }

    }

}

右键，run一下可以看到控制台结果：


1

2

[2, 1, 3, 4, 6, 7, 5]

[1, 2, 3, 4, 5, 6, 7]

 

② 快速排序

快排是基于分治策略的算法，不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 Java版实现如下：


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

package javaBasic.algorithm;

 

import java.util.Arrays;

 

public class QuickSort

{

    public static void main(String[] args)

    {

        int[] intA = new int[]{2,1,3,4,6,7,5};

        System.out.println(Arrays.toString(intA));

        //middleSort(intA, 0, intA.length - 1);

        //System.out.println(Arrays.toString(intA));

        sort(intA, 0, intA.length - 1);

        System.out.println(Arrays.toString(intA));

    }

     

    // 快速排序中的一个划分过程

    public static int  middleSort(int a[] , int left , int right)

    {

        int temp = a[left]; // 作为中间轴数

        while( left  < right)

        {

            /**

             * 从右到左，找到第一个比中间轴数小的，移到左端

             */

            while( left < right && a[right] > temp )

                right--;

            a[left] = a[right];

             

            /**

             * 从左到右，找到第一个比中间轴数大的，移到右端

             */

            while( left < right && a[left] < temp)

                left++;

            a[right] = a[left];

        }

         

        /**

         * 将中间轴数赋值

         */

        a[left] = temp;

        return left;

    }

     

    // 快速排序

    public static void sort(int[] a , int left, int right)

    {

        if (left < right)

        {

            /**

             * 根据左右索引相同才停止。

             * 不同的话，按着分治思想。

             * 找到中间轴数，一分为二，以此类推。

             */

            int middle = middleSort(a, left, right);

            sort(a, left, middle - 1);

            sort(a, middle + 1, right);

        }

    }

     

}

记忆方法：分治，就是分工。这里演示的是对分。大量经验数据表面，采用两个枢轴来划分成3份的算法更高效，这就是DualPivotQuicksort。这样也是我们后面讲的JDK源码。右键，run一下可以看到控制台和插入排序一样的结果。

③ 归并排序

如图，来自百度百科。归并排序也是一种分治思想的算法，之不用快速是对分。归并是一种分解到合并的算法。如下实现方式：


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

package javaBasic.algorithm;

 

import java.util.Arrays;

 

public class MergeSort

{

    public static void main(String[] args)

    {

        int[] intA = new int[]{10,4,6,3,8,2,5,7};

        System.out.println(Arrays.toString(intA));

        mergeSort(intA,0,intA.length-1);

        System.out.println(Arrays.toString(intA));

    }

     

    public static void mergeSort(int[] a, int left ,int right)

    {

        if (left < right)

        {

            int middle = (left + right) / 2; // 中间索引

             

            mergeSort(a, left, middle); // 对左侧数组递归

            mergeSort(a, middle+1, right); // 对右侧数组递归

             

            merge(a,left,middle,right); // 归并算法

        }

    }

 

    private static void merge(int[] a, int left, int middle, int right)

    {

        int [] tmpArr = new int[a.length];

         

        int mid = middle+1;

        int tmpArrLeft = left;// 记录左侧数组的索引

        int tmpLeft = left;

         

        /**

         * 从两个数组中取出小的一部分复制

         */

        while (left <= middle && mid <= right)

        {

            if (a[left] <= a[mid])

                tmpArr[tmpArrLeft++] = a[left++];

            else

                tmpArr[tmpArrLeft++] = a[mid++];

        }

         

        /**

         * 剩余部分右侧复制

         */

        while (mid <= right)

        {

            tmpArr[tmpArrLeft++] = a[mid++];

        }

         

        /**

         * 剩余部分左侧复制

         */

        while (left <= middle)

        {

            tmpArr[tmpArrLeft++] = a[left++];

        }

         

        /**

         * 分了再合

         */

        while(tmpLeft <= right)

        {

            a[tmpLeft] = tmpArr[tmpLeft++];

        }

    }

     

}

结果和上图一样：


1

2

[10, 4, 6, 3, 8, 2, 5, 7]

[2, 3, 4, 5, 6, 7, 8, 10]

 

三、JDK数则

在此谢谢@江南白衣大哥的文章，对我帮助很大。以下引用的：


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

5. JDK7/8中排序算法的改进

面试季的同学背一脑袋的插入、归并、冒泡、快排，那，JDK到底看上了哪家的排序算法？

 

Colletions.sort(list) 与 Arrays.sort(T[])

Colletions.sort()实际会将list转为数组，然后调用Arrays.sort()，排完了再转回List。

而Arrays.sort()，对原始类型(int[],double[],char[],byte[])，JDK6里用的是快速排序，对于对象类型(Object[])，JDK6则使用归并排序。为什么要用不同的算法呢？

 

JDK7的进步

到了JDK7，快速排序升级为双基准快排(双基准快排 vs 三路快排)；归并排序升级为归并排序的改进版TimSort，一个JDK的自我进化。

 

JDK8的进步

再到了JDK8， 对大集合增加了Arrays.parallelSort()函数，使用fork-Join框架，充分利用多核，对大的集合进行切分然后再归并排序，而在小的连续片段里，依然使用TimSort与DualPivotQuickSort。

 

结论

JDK团队的努力，从一些简单的New Features / Change List 根本看不到，所以没事升级一下JDK还是好的

 

我也查看了关于算法追踪到DualPivotQuicksort类，但是这类却不在JDK API。（抛出个问题：为什么这个类不出现在API里面？）哈哈，一看作者是Java之父参与写的，瞬间有研究的激情。根据白衣大哥说的，快速排序由双基准排序到三路快速排序。这也是在大量经验数据表面，采用两个枢轴来划分成3份的算法更高效。算法的思想也是分治思想。

下面又看到了一段发人自省的注释：


1

2

3

4

5

6

7

8

9

10

11

12

13

/**

    * If the length of an array to be sorted is less than this

    * constant, Quicksort is used in preference to merge sort.

    *  当数组长度小于286，为什么快速排序比归并排序好？

    */

   private static final int QUICKSORT_THRESHOLD = 286;

 

   /**

    * If the length of an array to be sorted is less than this

    * constant, insertion sort is used in preference to Quicksort.

    * 当数组长度小于47，为什么插入排序比快速排序好？

    */

   private static final int INSERTION_SORT_THRESHOLD = 47;

 

为什么？第二个问题，欢迎大神解答。

我的理解：第一，建立在大量经验数据结果。第二，根据算法时间复杂度和空间复杂度。至于深入了解需要大神解答。

JDK排序顺序图如下：

时间： 2024-10-30 23:42:50

Java 容器 & 泛型：四、Colletions.sort 和 Arrays.sort 的算法的相关文章

Java 容器 &amp; 泛型：五、HashMap 和 TreeMap的自白

一.Map回顾     Map,又称映射表,是将键映射到值的对象.有四种实现Map接口并且经常使用的Map集合为:HashMap,TreeMap,Hashtable 和 LinkedHashMap. 泥瓦匠记忆宫殿:     1.一个映射不包含重复的键.     2.每个键最多只能映射到一个值. 二.HashMap     HashMap是基于哈希表的Map接口的实现.其对键进行散列,散列函数只能作用于键.下面模拟下,公司员工和找员工的例子: ? 1 2 3 4 5 6 7 8 9 10 11

Java 容器 &amp; 泛型：一、认识容器

容器是Java语言学习中重要的一部分.泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就"顺理成章"地知道了.Java的容器类主要由两个接口派生而出:Collection和Map.   一.Collection vs Collections 首先,Collection 和 Collections 是两个不同的概念.之所以放在一起,是为了更好的比较.Collection是容器层次结构中根接口.而Collections是一个提供一些处理容器类静态方法的类. JDK不提供Colle

Java 容器 &amp; 泛型：二、ArrayList 、LinkedList和Vector比较

一.List回顾 序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表.确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2,并且如果列表本身允许 null 元素的话,通常它们允许多个 null 元素.实现List的有:ArrayList.LinkedList.Vector.Stack等.值得一提的是,Vector在JDK1.1的时候就有了,而List在JDK1.2的时候出现,待会我们会聊到ArrayList和Vector的区别.  

Java 容器 &amp; 泛型：六、容器讲到为什么要使用泛型

ArrayList是集合类中无处不在的,泛型也是,泛型对集合类尤其有用.但是为啥要使用泛型?理解好了这个问题可以帮助理解相关的更多知识点.下面泥瓦匠以最简单的例子来验证这个问题. 一.泛型 泛型的目的是为了可以让更多不同类型的对象重用.没错,这样理解就太low.真正目的是为了在编译时找到bug,而不是在运行时.(编译时,指的是源代码翻译成机器识别的代码的时候.运行时,是指代码在机器中运行的时候.)泛型只存在编译时,理解这个可以帮助你更好的理解泛型. 这样,在编译时会比在运行时更容易地找到bug和

Java 容器 &amp; 泛型：三、HashSet，TreeSet 和 LinkedHashSet比较

上一篇总结了下ArrayList .LinkedList和Vector比较,今天泥瓦匠总结下Hash .LinkedList和Vector比较.其实大家都是Collection,只不过有点各自特性.那就是数据结构的不同表现.   一.Set回顾 一个不包括重复元素(包括可变对象)的Collection,是一种无序的集合.Set不包含满 a.equals(b) 的元素对a和b,并且最多有一个null. 泥瓦匠的记忆宫殿: 1.不允许包含相同元素 2.判断对象是否相同,根据equals方法   二.

java.util.Arrays.sort两种方式的排序（及文件读写练习）

import java.io.*; import java.util.*; public class SortTest{    public static void main(String args[]) throws IOException, ClassNotFoundException {        FileReader InWord = new FileReader(new File("words.txt"));        BufferedReader in = new

关于Java Arrays.sort()的问题

问题描述 我写了一个关于Arrays.sort()的例子 .int[] arrayT = {2,1,121,123};for(int i : arrayT){ Arrays.sort(arrayT);System.out.println(i);}输出结果是:2 2 121 123为什么不是我想像的1,2,121,123呢? 而且还出现了在数组中没有出现的元素?? 问题补充:freish 写道 解决方案 因为你的Arrays.sort(arrayT);在for里面,第一次for的i取得是未排序数组

java容器 collection-JAVA中什么是容器？什么是集合？求大神指导

问题描述 JAVA中什么是容器?什么是集合?求大神指导 容器是什么?跟接口是什么关系?集合又是什么?求大神帮忙?????? 解决方案 Java集合容器主要有以下几类: 1,内置容器:数组 2,list容器:Vetor,Stack,ArrayList,LinkedList, CopyOnWriteArrayList(1.5),AttributeList(1.5),RoleList(1.5),RoleUnresolvedList(1.5), ConcurrentLinkedQueue(1.5),Ar

Java容器——未获支持的操作

    先看一个例子: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import