【工具类】Arrays

【工具类】Arrays

1 . Arrays.asList

2 . Arrays.sort:

在学习 Lambda 的时候用到了 Arrays.sort,顺便看一下 sort 的实现原理:

public class Arrays_all {
	public static void main(String[] args) {
		String[] players = {"Bouboo", "Alex", "City"};
		// 比较器
		Comparator<String> comparator = new Comparator<String>() {
			@Override
			public int compare(String s1, String s2) {
				return s1.compareTo(s2);
			}
		};
		// 排序
		Arrays.sort(players, comparator);
		System.out.println(Arrays.toString(players));
		// [Alex, Bouboo, City]
	}
}
Arrays.sort (players, comparator) : comparator 是重写的,可以先不看。
先看一下Arrays.sort 做了什么处理.
public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }
因为 C 是有内容的,进入 else, 判断 LegacyMergeSort.userRequested 的值,发现在1.7 以后,不建议使用legacyMergeSort 方法了,所以在 1.6 的时候,是true,1.7 以后是false. 此时程序进入TimSort.sort(a, 0, a.length, c, null, 0, 0);
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;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi, c);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen, c);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }
TimSort的重要思想是分区与合并
分区
分区的思想是扫描一次数组,把连续正序列(如果是升序排序,那么正序列就是升序序列)(也就是后面所指的run),如果是反序列,把分区里的元素反转一下。 例如
1,2,3,6,4,5,8,6,4 划分分区结果为
[1,2,3,6],[4,5,8],[6,4]
然后反转反序列
[1,2,3,6],[4,5,8],[4,6]

合并
考虑一个极端的例子,比如分区的长度分别为 10000,10,1000,10,10,我们当然希望是先让10个10合并成20, 20和1000合并成1020如此下去, 如果从从左往右顺序合并的话,每次都用到10000这个数组和去小的数组合并,代价太大了。所以我们可以用一个策略来优化合并的顺序。

3 . Arrays.toString

contiune….

0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments