vlambda博客
学习文章列表

 def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f)

 def on[U](f: U => T): Ordering[U] = new Ordering[U] { def compare(x: U, y: U) = outer.compare(f(x), f(y))   }

  def compare(x:U, y:U) = Ordering[T].compare(f(x), f(y))

 def sorted[B >: A](implicit ord: Ordering[B]): Repr = { val len = this.length //可变集合构建（从这可以看到Scala常规操作就是在函数式结构内部封装可变结构，而不对用户暴露可变性） val b = newBuilder //单个元素不用排序，直接返回当前集合 if (len == 1) b ++= this else if (len > 1) { //标记需要添加多少个元素 //当调用“result”返回集合结果时。一些生成器（builder）将根据此值优化它们的表示。如Set对个数为0~4的集合会进行优化处理 b.sizeHint(len) val arr = new Array[AnyRef](len) //以前使用的ArraySeq用于更紧凑但速度较慢的代码 var i = 0 for (x <- this) { //此处进行类型转换为了调用Java方法 arr(i) = x.asInstanceOf[AnyRef] i += 1 } //使用Java的Arrays.sort进行排序 java.util.Arrays.sort(arr, ord.asInstanceOf[Ordering[Object]]) i = 0 while (i < arr.length) { //重新转换为原类型 b += arr(i).asInstanceOf[A] i += 1 } } //返回排序结果 b.result()  }

 public static <T> void sort(T[] a, Comparator<? super T> c) { if (c == null) { //没有比较器，调用sort，并判断是否选择旧的归并排序（归并） sort(a); } else { //有比较器，仍然需要判断是否用户选择了旧的归并排序 if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else //调用新的TimSort排序 TimSort.sort(a, 0, a.length, c, null, 0, 0); }    }

 public static void sort(Object[] a) { //可以使用系统属性java.util.Arrays.useLegacyMergeSort来选择旧的归并排序实现 if (LegacyMergeSort.userRequested) legacyMergeSort(a); else //ComparableTimSort实际是TimSort的一个近似副本实现，用于实现Comparable的对象数组，而不是使用显式比较器。很显然，这就是一个没有比较器的TimSort，不对其进行讨论。 ComparableTimSort.sort(a, 0, a.length, 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; //大小为0和1的数组始终是排序的
 //如果数组很小，则使用不需要归并的“mini-TimSort”，这个值为32，小于32将不会使用归并，而使用binarySort（二分排序， 它需要O(nlogn)次比较，但是最坏的情况需要O(n^2)次数据移动） //MIN_MERGE常数应为2的幂。Tim Peter的C实现中为64，但是凭经验确定32在此实现中能更好地工作。万一您将此常量设置为一个不是2的幂的数字，则需要更改minRunLength计算  //对于binarySort，如果指定范围的初始部分已经排序，则此方法可以利用它：此方法假定索引lo（包含）到start（不包含）中的元素已经排序。 //1.从数组开始处找到一组连接升序或严格降序（找到后翻转）的数 //2.使用二分查找的方法将后续的数插入之前的已排序数组，binarySort对数组a[lo:hi]进行排序，并且a[lo:start]是已经排好序的。 //算法的思路是对a[start:hi]中的元素，每次使用binarySearch为它在a[lo:start]中找到相应位置，并插入。
 if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi, c); //使用二分排序，计算出从哪开始二分排序并利用已有序的元素（截止到initRunLen，数组一定是升序的） binarySort(a, lo, hi, lo + initRunLen, c); return; }
 TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); //从剩下需要排序的元素个数中，选取minRun大小，之后待排序数组将被分成以minRun大小为区块的一块块子数组 int minRun = minRunLength(nRemaining); do { //找到初始的一组升序数列，countRunAndMakeAscending会找到一个run //这个run必须是已经排序的，并且该函数会保证它为升序，也就是说，如果找到的是一个降序的，会对其进行翻转 int runLen = countRunAndMakeAscending(a, lo, hi, c);
 //若这组区块大小小于minRun，则将后续的数补足，利用binarySort对run进行扩展，并且扩展后，run仍然是有序的 if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen, c); runLen = force; }
 //当前的run位于a[lo:runLen]，将其入栈ts.pushRun(lo, runLen); //为后续merge各区块作准备：记录当前已排序的各区块的大小（pushRun记录run中元素索引和元素个数） ts.pushRun(lo, runLen); //对当前的各区块进行merge ts.mergeCollapse();
 //寻找下一个run，lo之前是已经排序的 lo += runLen; nRemaining -= runLen; //计算剩下未排序的元素 } while (nRemaining != 0); //直到将待排序数组排序完退出循环
 //归并所有剩余run以完成排序 assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1;}

 private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, Comparator<? super T> c) { assert lo < hi; int runHi = lo + 1; if (runHi == hi) return 1;
 if (c.compare(a[runHi++], a[lo]) < 0) { //降序的需要反转一下 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { //升序 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++; } //返回已经升序的元素个数 return runHi - lo;}

 private static int minRunLength(int n) { assert n >= 0; int r = 0;  while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r;  }

 private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { if (runLen[n - 1] < runLen[n + 1]) n--; mergeAt(n); } else if (runLen[n] <= runLen[n + 1]) { mergeAt(n); } else { break; // Invariant is established } }  }