Java中的Arrays.sort 分析及其非递归实现——Bash
上篇文章我们讨论了快速排序算法，它与归并算法同属分治算法的一种。
两者在实现上很相似，都使用了分治递归的策略来实现。
?
相信大家对快排和归并排序都不陌生，不过我们平常接触到的一般是这两种算法的递归实现方式。
以Java为例，其Arrays类中的sort在排序Object的时候用的就是归并排序。
不过其在实现上做了优化,在子问题足够小时（每个递归子序列长度不大于7）通过插入排序完成这个子序列的排序。
?
概括而言，Java中的Arrays.sort在排序Object对象的数组时用的是归并排序+插入排序的方式，即对插入排序结果的归并。
?
Java中的实现如下：
?
private static final int INSERTIONSORT_THRESHOLD = 7; /** * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset to generate corresponding low, high in src */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) {int length = high - low;// Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } }?
上述方式通过函数递归调用实现，本文接下来要讨论的是该方案的非递归实现，实现语言是Bash。
与上篇文章中使用的方法类似，通过栈的数据结构特点，模拟函数的递归调用。
?
由于快排的递归操作不需要对子问题进行合并，因此只需要将问题按照一定策略分解，并将子问题解决。
而归并排序则需要将子问题的结果做进一步的处理，因此，在栈空间的使用上，不仅需要跟踪递归调用的栈，还需要记录子问题计算结果的栈，用来对子问题结果做递归合并处理。
?
这种方式有点像通过逆波兰式计算表达式结果的思路，具体代码如下：
?
#!/bin/bashdeclare -a inputArray=(1 3 2 4 5 9 8 7 0);##init for large number testfor i in `seq 1000`do inputArray[$i]=$RANDOM;doneinputLength=${#inputArray[@]};lastIndex=$((inputLength-1));## trace Stack for recursive callsdeclare -a traceStackStart;declare -a traceStackEnd;traceStackDeep=0;##stack for the already sorted sub Array to mergedeclare -a mergeStackStart;declare -a mergeStackEnd;mergeStackDeep=0;## begin recursive call...traceStackStart[0]=0;traceStackEnd[0]=$lastIndex;traceStackDeep=1;## recursive call until traceStack emptywhile [ $traceStackDeep -ne 0 ]do #pop stack traceStackDeep=$((traceStackDeep-1)); low=${traceStackStart[$traceStackDeep]}; hig=${traceStackEnd[$traceStackDeep]}; if [ "$low" = "+" ]; then mergeStackDeep=$((mergeStackDeep-1)); l1=${mergeStackStart[$mergeStackDeep]}; h1=${mergeStackEnd[$mergeStackDeep]}; mergeStackDeep=$((mergeStackDeep-1)); l2=${mergeStackStart[$mergeStackDeep]}; h2=${mergeStackEnd[$mergeStackDeep]}; ## merge sorted subArray here i=0; j=0; desLow=0; declare -a tmp=(0); for((i=l1,j=l2;i<=h1 && j<=h2;desLow++)) do if [ ${inputArray[$i]} -le ${inputArray[$j]} ]; then tmp[$desLow]=${inputArray[$i]}; i=$((i+1)); else tmp[$desLow]=${inputArray[$j]}; j=$((j+1)); fi done if [ $i -gt $h1 ]; then for((;j<=h2;j++,desLow++)) do tmp[$desLow]=${inputArray[$j]}; done else for((;i<=h1;i++,desLow++)) do tmp[$desLow]=${inputArray[$i]}; done fi for((tmpI=0,i=l1;i<=h2;i++,tmpI++)) do inputArray[$i]=${tmp[$tmpI]}; done ## push the merge sort result to the mergeStack mergeStackStart[$mergeStackDeep]=$l1; mergeStackEnd[$mergeStackDeep]=$h2; mergeStackDeep=$((mergeStackDeep+1)); elif [ $low -lt $hig ]; then l=$low; h=$hig; space=$((h-l)); if [ $space -le 7 ]; then #insertion sort here for((i=l+1;i<=h;i++)) do for((j=i;j>l;j--)) do if [ ${inputArray[$j-1]} -gt ${inputArray[$j]} ]; then tmp=${inputArray[$j-1]}; inputArray[$j-1]=${inputArray[$j]}; inputArray[$j]=$tmp; fi done done mergeStackStart[$mergeStackDeep]=$l; mergeStackEnd[$mergeStackDeep]=$h; mergeStackDeep=$((mergeStackDeep+1)); else m=$((l+(h-l)/2)); n=$((m+1)); traceStackStart[$traceStackDeep]="+"; traceStackEnd[$traceStackDeep]="+"; traceStackDeep=$((traceStackDeep+1)); traceStackStart[$traceStackDeep]=$l; traceStackEnd[$traceStackDeep]=$m; traceStackDeep=$((traceStackDeep+1)); traceStackStart[$traceStackDeep]=$n; traceStackEnd[$traceStackDeep]=$h; traceStackDeep=$((traceStackDeep+1)); fi fidoneecho ${inputArray[*]};??
?
?
?