深入JDK源代码之Arrays类中的排序查找算法
最近在暑假实习，没什么任务给我做，不是我不能做，而是还没那资格，毕竟才来了一周多。闲着无事，在网上看看国内的牛公司的招聘要求，想自己能达到他们的要求，准备研究下JDK中的常用类的源代码。今天就来看看java.util.Arrays类。这个类是个数组工具类。主要提供方法sort(),fill（），binarySearch（），还有数组复制等方法。打开源文件，刚超过4千行，不过包括很多注释，那么我在这里主要讲讲这里面涉及的排序算法和查找算法。
一、binarySearch（）方法，二分法查找算法，算法思想：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。 基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
public static void sort(double[] a) { sort2(a, 0, a.length); } private static void sort2(double a[], int fromIndex, int toIndex) { //static long doubleToLongBits(double value) //根据 IEEE 754 浮点双精度格式 ("double format") 位布局，返回指定浮点值的表示形式。 final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d); /* * The sort is done in three phases to avoid the expense of using * NaN and -0.0 aware comparisons during the main sort. */ /* * Preprocessing phase: Move any NaN's to end of array, count the * number of -0.0's, and turn them into 0.0's. */ int numNegZeros = 0; int i = fromIndex, n = toIndex; while(i < n) { if (a[i] != a[i]) { //这段搞不懂，源代码怪怪的，感觉多此一举double swap = a[i]; a[i] = a[--n]; a[n] = swap; } else { if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) { a[i] = 0.0d; numNegZeros++; } i++; } } // Main sort phase: quicksort everything but the NaN's sort1(a, fromIndex, n-fromIndex); // Postprocessing phase: change 0.0's to -0.0's as required if (numNegZeros != 0) { int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero do { j--; } while (j>=0 && a[j]==0.0d); // j is now one less than the index of the FIRST zero for (int k=0; k<numNegZeros; k++) a[++j] = -0.0d; } }