这是牛客网华为java题库的一道题：HJ26 字符串排序
题中要求，对字符串中的英文字母不分大小写按照字典顺序排序，遇到相同的字母，要求保持它们的相对顺序不变，非英文字母字符保持原位置不变。例如：
输入：A Famous Saying: Much Ado About Nothing (2012/8).
输出：A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).
题解当中有这样一段代码：

List<Character> list=new ArrayList<Character>();for(Character ch:str.toCharArray()){if(isLetter(ch))list.add(ch);}//list中的元素为：[A, F, a, m, o, u, s, S, a, y, i, n, g, M, u, c, h, A, d, o, A, b, o, u, t, N, o, t, h, i, n, g]
list.sort((a,b)->Character.toLowerCase(a)-Character.toLowerCase(b));

(a,b)->Character.toLowerCase(a)-Character.toLowerCase(b)是一个拉姆达表达式，表示输入a,b两个值，返回a,b转化为小写字母的差值：Character.toLowerCase(a)-Character.toLowerCase(b)
查阅资料发现拉姆达表达式在sort方法中的应用情况是这样的：

list.sort( (a,b)->a-b) a-b>0 donothing
list.sort( (a,b)->a-b) a-b>0 donothing
list.sort( (a,b)->a-b) a-b<0 交换a和b的位置

为弄清楚该语句实际运行时a,b的值，对该程序进行debug，发现a,b的值并非我认为的a在b之前，而是b在a之前：
显然，Character.toLowerCase(a)-Character.toLowerCase(b)=‘F’-‘A’=70-65=5>0，于是A和F不交换位置。
跟踪(a,b)的变化，发现：

A, F, a, m, o, u, s, S, a, y, i, n, g, M, u, c, h, A, d, o, A, b, o, u, t, N, o, t, h, i, n, g
(F,A),(a,F),(a,A),(m,a),(m,F),(o,f),(o,m),(u,f)...(a,o),(a,F),(a,a)...

分析：
(F,A)，a-b>0，不交换
(a,F)，a-b<0，交换，F已经是是i-1序列最小值，交换之后list变为A, a, F, m, o, u, s，S,a,y,i,n,g…
(a,A)，a-b=0，不交换
(m,a)，a-b>0，不交换
(m,F)，a-b>0，不交换
(o,f)，a-b>0，不交换
(o,m)，a-b>0，不交换
(u,f)，a-b>0，不交换
…
(a,o)，a-b<0，不交换，继续找更小的值
(a,F)，a-b，不交换，继续找更小的值
(a,a)，a-b=0，不交换，继续找更大的值，发现只有F，交换a和F，list变为A, a, a, m, o, s, S，u,F,y,i,n,g…
…
看起来和二分法十分相像：
设list的索引i（i从0开始），设high=i,low=0；
比较元素i的值和元素mid=(high+low)/2（向下取整）的值
若前者小于等于后者，则令high=(high+low)/2,继续比较元素i和j的值，若前者大于后者，则令low=(high+low)/2，继续比较元素i和元素mid的值，直到在i-1序列中找到首次大于i的值mid（保证low和high差值大于1，否则结束）,交换i和mid的值。（每次将i和它左边的元素进行比较时，i左边的序列一定是不严格递增序列，每次遍历都会得到一个不严格递增序列）
查看源码，发现ArrayList的sort方法的确是用二分法实现的。

    private static <T> void binarySort(T[] a, int lo, int hi, int start,Comparator<? super T> c) {assert lo <= start && start <= hi;if (start == lo)start++;for ( ; start < hi; start++) {T pivot = a[start];// Set left (and right) to the index where a[start] (pivot) belongsint left = lo;int right = start;assert left <= right;/** Invariants:*   pivot >= all in [lo, left).*   pivot <  all in [right, start).*/while (left < right) {int mid = (left + right) >>> 1;if (c.compare(pivot, a[mid]) < 0)right = mid;elseleft = mid + 1;}assert left == right;/** The invariants still hold: pivot >= all in [lo, left) and* pivot < all in [left, start), so pivot belongs at left.  Note* that if there are elements equal to pivot, left points to the* first slot after them -- that's why this sort is stable.* Slide elements over to make room for pivot.*/int n = start - left;  // The number of elements to move// Switch is just an optimization for arraycopy in default caseswitch (n) {case 2:  a[left + 2] = a[left + 1];case 1:  a[left + 1] = a[left];break;default: System.arraycopy(a, left, a, left + 1, n);}a[left] = pivot;}}