排序算法一览（下）：归并类、分布类和混合类排序

public class Sort {
  public static > void mergeSort( T[] arr ) {
    T[] tmpArr = (T[]) new Comparable[arr.length];
    mergeSort(arr, tmpArr, 0, arr.length - 1);
  }
 
  private static >
  void mergeSort( T[] arr, T[] tmpArr,
      int left, int right ) {
    //recursive way
    if ( left < right ) {
      int center = ( left + right ) / 2;
      mergeSort(arr, tmpArr, left, center);
      mergeSort(arr, tmpArr, center + 1, right);
      merge(arr, tmpArr, left, center + 1, right);
    }
   }
 
  private static > void merge( T[] arr, T[] tmpArr,
      int lPos, int rPos, int rEnd ) {
    int lEnd = rPos - 1;
    int tPos = lPos;
    int leftTmp = lPos;
 
    while ( lPos <= lEnd && rPos <= rEnd  ) {
      if ( arr[lPos].compareTo( arr[rPos] ) <= 0 )
        tmpArr[ tPos++ ] = arr[ lPos++ ];
      else
        tmpArr[ tPos++ ] = arr[ rPos++ ];
    }
 
    //copy the rest element of the left half subarray.
    while ( lPos <= lEnd )
      tmpArr[ tPos++ ] = arr[ lPos++ ];
    //copy the rest elements of the right half subarray. (only one loop will be execute)
    while ( rPos <= rEnd )
      tmpArr[ tPos++ ] = arr[ rPos++ ];
 
    //copy the tmpArr back cause we need to change the arr array items.
    for ( ; rEnd >= leftTmp; rEnd-- )
      arr[rEnd] = tmpArr[rEnd];
  }
}

procedure strandSort( A : list of sortable items ) defined as:
  while length( A ) > 0
    clear sublist
    sublist[ 0 ] := A[ 0 ]
    remove A[ 0 ]
    for each i in 0 to length( A ) - 1 do:
      if A[ i ] > sublist[ last ] then
        append A[ i ] to sublist
        remove A[ i ]
      end if
    end for
    merge sublist into results
  end while
  return results
end procedure

const int base=10;
wx *headn,*curn,*box[base],*curbox[base];
 
void basesort(int t)
{
  int i,k=1,r,bn;
  for(i=1;i<=t;i++)
  {
    k*=base;
  }
  r=k*base;
  for(i=0;inext;curn!=NULL;curn=curn->next)
  {
    bn=(curn->num%r)/k;
    curbox[bn]->next=curn;
    curbox[bn]=curbox[bn]->next;
  }
  curn=headn;
  for(i=0;inext=box[i]->next;
      curn=curbox[i];
    }
  }
  curn->next=NULL;
}
 
int main()
{
  int i,n,z=0,maxn=0;
  curn=headn=new wx;
  cin>>n;
  for(i=0;inext=new wx;
    cin>>curn->num;
    maxn=max(maxn,curn->num);
  }
  while(maxn/base>0)
  {
    maxn/=base;
    z++;
  }
  for(i=0;i<=z;i++)
  {
    basesort(i);
  }
  printwx();
  return 0;
}

american_flag_sort(Array, Radix)
  for each digit D:
    # first pass: compute counts
    Counts <- zeros(Radix)
    for object X in Array:
      Counts[digit D of object X in base Radix] += 1
    # compute bucket offsets
    Offsets <- [ sum(Counts[0..i]) for i in 1..Radix]
    # swap objects into place
    for object X in Array:
      swap X to the bucket starting at Offsets[digit D of X in base Radix]
    for each Bucket:
      american_flag_sort(Bucket, Radix)

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

for i in [0...length(a)-1]
  b[a[i]] := b[a[i]]+1

j := 0
for i in [0...length(b)-1]
  repeat b[i] times
    a[j] := i
    j := j+1

private static void countingSort(int[] A, int[] B, int k) {
    int[] C = new int[k];
    // 计数
    for (int j = 0; j < A.length; j++) {
        int a = A[j];
        C[a] += 1;
    }
    // 求计数和
    for (int i = 1; i < k; i++) {
        C[i] = C[i] + C[i - 1];
    }
    // 整理
    for (int j = A.length - 1; j >= 0; j--) {
        int a = A[j];
        B[C[a] - 1] = a;
        C[a] -= 1;
    }
}