Java集合框架之算法

Java集合框架中，还有两个工具类值得关注：Collections和Arrays。对于一个集合或数组，有很多必要的操作，比如查找、排序、反转、随机打乱、求最大值最小值等等。其中查找、排序都要用到合适的算法，以便快速完成这些操作。

1. 查找

Collections和Arrays中的查找都是二分查找法。二分查找法基于一个按升序排列的元素列表，分为三部分：中值前列表、中值、中值后列表。如果是中值，直接返回，如果元素比中值大，就把“中值后列表”变成新列表，反之，把“中值前列表”变成新列表。然后对新列表继续上述操作。一直循环下去，找到为止。在最坏的情况下，需要查找log2n次，所以二分查找法的时间复杂度是O(logn)。

因为二分查找法是基于一个按升序排列的元素列表，所以Collections中的二分查找法只针对List。List的实现又分为是不是RandomAccess。RandomAccess是一个标记接口，ArrayList有实现这个标记，而LinkedList没有实现这个标记。这两者的二分查找实现有细微的区别，如果是RandomAccess，就会基于数组下标进行二分查找，如果不是，就要依赖外部迭代器进行二分查找，显然通过数组下标查找效率会更高。

2. 排序

Collections的排序方法都是调用Arrays的排序方法。对于Arrays中的排序方法，分为两类，一类是基本数据类型，一类是对象类型。对于基本数据类型采用的是双轴快速排序（Dual-Pivot QuickSort），是一种改进的快速排序算法，早期版本是相对传统的快速排序。对于对象类型则是使用TimSort，思想上也是一种归并和二分插入排序（binarySort）结合的优化排序算法。TimSort 并不是 Java 的独创，简单说它的思路是查找数据集中已经排好序的分区（这里叫 run），然后合并这些分区来达到排序的目的。

TimSort的大致逻辑是，如果元素个数在32个以内，就用二分插入排序；如果多于32个元素，就采取结合二分插入排序和归并排序的办法。这就综合了两种排序算法在不同场景下的优势。两种算法有何不同，在本文第三节就讲到。

另外，Java 8 引入了并行排序算法（直接使用 parallelSort 方法），这是为了充分利用现代多核处理器的计算能力，底层实现基于 fork-join 框架，当处理的数据集比较小的时候，差距不明显，甚至还表现差一点；但是，当数据集增长到数万或百万以上时，提高就非常大了，具体还是取决于处理器和系统环境。

排序算法仍然在不断改进，最近双轴快速排序实现的作者提交了一个更进一步的改进，历时多年的研究，目前正在审核和验证阶段。根据作者的性能测试对比，相比于基于归并排序的实现，新改进可以提高随机数据排序速度提高 10%～20%，甚至在其他特征的数据集上也有几倍的提高。

3. 常见的排序算法

排序分内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。通常我们指的排序是内部排序。内部排序有很多，从大的层面可以分为两类：一类是比较排序（冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序……），一类是非比较排序（计数排序，基数排序，桶排序……）。

各类排序算法的性能对比：

输入图片说明

从上表可以看出，排序算法还有一个稳定性的概念：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。需要注意的是，排序算法是否为稳定的最终是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。冒泡排序就可以实现为稳定的，也可以实现为不稳定的，上表的稳定性与否只是个参考。稳定性有什么意义呢？举个例子，班级学生按姓名自然排序，如果姓名相同，按年龄排序。那么就可以先按年龄排序，再按姓名排序。这样相同姓名的同学之间的顺序就可以遵循年龄顺序了。

时间复杂度也只是一个参考，并不是说稳定性一样，效率就是一样的。时间复杂度的数学定义是："存在有正常数C、n0，使得当n≧n0时都有0≦T(n)≦C*f(n)，则T(n)=O(f(n))。" 其中，f(n)代表当执行规模为n时，使用该算法执行的次数。时间复杂度相同，只是执行次数的数量级相同。数量级虽然相同，但是具体数量可能相差很大（比如log2N和log10N数量级相同，但是随着N越来越大，差距也会越来越大。）。不仅如此，就算执行数量相等，每次执行的时间也会有所不同。同一个算法，在不同规模情况下，每次执行的时间也会有所不同。所以，才有在不同场合选择不同算法的必要性，才会有那么多算法并存于世。

本文只详细介绍四种在Java集合框架中用到了的排序，在Java中的实现都有优化，优化的细节太多不做详解。本文试图从基本的原理出发帮助大家理解Java集合框架中的复杂算法：

3.1 快速排序

在元素列表中选一个基准元素，比这个基准元素小的放在左边，比这个基准元素大的放在右边；在两边元素列表再各选一个基准元素，再按前面的方法各操作一次；以此类推……最终，就能完全排序。

/** * 快速排序 */public void fastSort() {		int[] arr = {55,3,66,37,90,24,98,38,63,23,72,66,26,49};		this.print(arr);		int i = 0;	int j = arr.length-1;	int hole = 0;	int x = arr[0];		fastSorting(arr,i,j,hole,x);		this.print(arr);	}/** *  * @param arr 数组 * @param i 排序起始index * @param j 排序结束index * @param hole 初始空洞index * @param x 基准值，必须为初始空洞index的值 * ①先从右至左，找到比基准值小的值，然后把当前值填充空洞，当前位置成为新的空洞，j的值减1； * ②再从左至右，找到比基准值大的值，然后把当前值填充空洞，当前位置成为新的空洞，i的值减1； * ③反复执行，直到i大于j；至此完成了第一个目标，让所有比基准值小的值排到左边，比基准值大的值排到右边 * ④如果基准值左边的元素个数大于1，或基准值右边的元素个数大于1，就递归执行前三步骤；执行完成后，就完成了第二个目标，即完成了整个排序 */private void fastSorting(int[] arr,int i,int j,int hole,int x) {		//记录初始index和结束index，因为i和j会变化	int init = i;	int end = j;	boolean flag = true;		while(i<=j) {				if(flag) {						//从右至左，找到比基准值小的值，然后把当前值填充空洞，当前位置成为新的空洞			if(arr[j] < x) {				arr[hole] = arr[j];				hole = j;				flag = false;			}			j--;		} else {						//从左至右，找到比基准值大的值，然后把当前值填充空洞，当前位置成为新的空洞			i++;			if(arr[i] > x) {				arr[hole] = arr[i];				hole = i;				flag = true;			}		}			}		//最后把基准值填入最后的空洞	arr[i] = x;		//如果基准值左边的元素个数大于1，就递归执行本方法逻辑	if(init

看完这个实现，你会发现每次操作的执行时间差不多，也是就是说，实际操作时间应该是时间复杂度的常数倍。是一种很理想的排序算法。在不要求稳定性的情况下，是一种很好的选择。所以在Java Arrays中，对基本数据类型进行排序（只有一种属性，就是它本身的值，所以不需要稳定性），选择的就是快速排序。

3.2 二分插入排序

插入排序就像抓牌，小牌放在左边，大牌放在右边，拿到一张新牌，就从右到左逐个比较，遇到小于等于新牌的位置，就在后面插入这张新牌。插入排序的时间复杂度是O(n2)。

二分插入排序可以参考前文提到的二分查找法，利用的是以前的牌都排好了序。拿到一张新牌以后，不是从右到左逐个比较，而是从中间位置开始，如果中间那张牌比新牌小，就找右边那手牌的中间位置，以此类推……因为二分查找的时间复杂度是O(logn)，要查找n次，所以二分插入排序的时间复杂度是O(nlongn)。

/** * 二分插入排序 */public void binarySort() {		int[] arr = {55,3,66,37,90,24,98,38,63,23,72,66,26,49};		this.print(arr);		for(int i=1;i
    
      insertValue) {			//当中值大于插入值，减小ep，并相应调整mid			ep = mid;			mid = sp/2 + ep/2;		}else {			//当中值小于等于插入值，增大sp,并相应调整mid			sp = mid+1;			mid = sp/2 + ep/2;		}	}		//此时，sp=ep，sp的值就是要插入的位置，先将sp右边的元素右移1个位置	for(int j=i;j>sp;j--) {		arr[j] = arr[j-1];	}		//再将插入值插入sp位置	arr[sp] = insertValue;	}

看完这个实现，你会发现二分插入排序的最大的开销在于找到插入位置后，后面的元素通通都要右移一个位置。虽然它的时间复杂度是O(nlogn)，看起来跟其他排序算法差不多，但是n的那部分（n次插入操作），开销特别大，而且规模n越大，每次操作的开销越大。而logn的那部分（查找插入位置），开销几乎可以忽略不计。

所以，n比较小的时候，二分插入排序的性能特别好，因为查找插入位置开销很小。当n比较大的时候，性能就会下滑的越来越快。加上二分插入排序是稳定的，所以Java的TimeSort选择在数据量小（n<=32）的情况下用二分插入排序。

3.3 归并排序

假设元素列表长度为n，拆成n个元素列表，每个列表1个元素，再两两合并，合并完了顺便排个序；然后再对两个已经排好序的长度为2的列表进行合并排序；以此类推……递归地对两个有序列表合并排序，叫做归并排序。

两个有序列表的合并排序细节是怎么样呢？这个非常简单，只要从比较二个列表的第一个元素，谁小就先取谁，放到一个新列表，取了后就在对应列表中删除这个数。然后再进行比较，如果有列表为空，那直接将另一个列表的数据依次取出即可。

/** * 归并排序 */public void mergeSort() {		int[] arr = {55,3,66,37,90,24,98,38,63,23,72,66,26,49};		this.print(arr);		mergeSorting(arr);		this.print(arr);	}/** * 归并排序 先拆分成两个子数组，再递归直到每个数组只剩下一个元素为止，然后合并两个已经排好序的两个子数组 * @param arr 数组 */private void mergeSorting(int[] arr) {		//拆分成两个子数组	int[] arrLeft = Arrays.copyOfRange(arr, 0, arr.length/2);	int[] arrRight = Arrays.copyOfRange(arr, arr.length/2, arr.length);		//递归直到每个数组只剩下一个元素为止	if(arrLeft.length>1) {		mergeSorting(arrLeft);	}	if(arrRight.length>1) {		mergeSorting(arrRight);	}		//合并两个已经排好序的两个子数组。代码执行到了这里，arrLeft和arrRight已经排好序了。		//左边子数组的指针	int lp = 0;	//右边子数组的指针	int rp = 0;	for(int i=0;i

归并排序性能上非常稳定，实际操作时间应该是时间复杂度的常数倍。但是要占用比较大的内存空间。它是一种稳定的排序算法，所以适合对复杂对象的排序。所以当数据量大于32，Java的TimeSort就会切换为归并排序。

另外，归并排序符合fork-join模型，完全可以改进为和fork-join框架结合的算法，用多线程进行排序。在数据量大的时候，优势非常明显。

3.4 堆排序

在优先队列中，就利用了堆排序来实现。要理解堆排序，首先要理解它的数据结构。这里简要用文字描述一下它的原理，如果想理解的更清楚，请自行学习，很多资料有图片辅助理解。

支持堆排序的物理结构是一个数组，逻辑结构是一个二叉堆，二叉堆是一棵完全二叉树或近似完全二叉树，假设子节点在数组中的index是s，那么父节点的index就一定是(s-1)/2。如果父节点的index是p，那么它的两个子节点的index分别是2p+1和2p+2。

二叉堆又分为最小堆和最大堆，最小堆的父节点的值一定小于等于子节点的值，最大堆刚好相反，父节点的值一定大于等于子节点的值。

当一个普通的数组进行最小堆化以后，它的根节点，即数组的第一个元素，一定是整个数组中最小的元素。然后把第一个元素去掉，替换成最后一个元素（最大的元素），再进行第二次最小堆化，就会得到第二小的元素……以此类推，最终就能完全排序。

/*** 堆排序 */public void heapSort() {		int[] arr = {55,3,66,37,90,24,98,38,63,23,72,66,26,49};	int[] resultArr = new int[arr.length];		this.print(arr);			//堆化-去掉最小值补上最大值-堆化-去掉最小值补上最大值……循环到最后，最终完全排序	for(int j=0;j
    
     arr[i]) {		int temp = arr[i];		arr[i] = arr[parent];		arr[parent] = temp;				if(parent>0) {			i = parent;			heapSorting(arr,i);		}	}}

看完这个实现，你就会明白为什么优先队列会选择堆排序。事实上，堆排序的性能在众多排序算法里面并不算拔尖，甚至有点落后（这也是Java默认的排序算法不选择它的原因）。但是它特别适合优先队列的业务场景：首先，优先队列并不需要完全排序，只要把优先级最高的数据放到一个特定的位置（通常数组的第一个位置）就行。数组只要进行一次堆化，就可以实现这个目标，时间复杂度就是O(logn)。每次添加一个元素，进行一次堆化，删除一个元素，也进行一次堆化，每次操作的时间复杂度都只是O(logn)。

所以，优先队列这种场景并不需要一次性完全排序，用堆排序特别合适。

Java集合框架不仅封装了数据结构，实现了常用的数据容器，还封装了一些算法，让开发者直接使用。所以，很多Java开发者感觉不到数据结构和算法的重要性，因为都被封装起来了，很容易不知不觉地用了。但是，了解里面的原理，可以做到最佳实践。这也是本文的目的。

理解本文的扩展知识：

完全二叉树和近似完全二叉树是什么？

fork-join框架的原理是什么？

外部排序是什么？

转载于:https://my.oschina.net/leaforbook/blog/1821943

你可能感兴趣的文章