常用排序算法-java实现（希尔，归并）
3、希尔排序

/** Shellsort, using a sequence suggested by Gonnet.* @param a an array of Comparable items.*/public static void shellsort( Comparable [] a ){   for( int gap = a.length / 2; gap > 0; gap = gap==2?1:(int) (gap/2.2))        for( int i = gap; i< a.length; i++){            Comparable tmp = a[i];            int j = i;            for( ; j > gap && tmp.compareTo( a[j-gap]) < 0; j -= gap)                a[j] = a[j-gap];            a[j] = tmp;        }}

思想是：首先，比较相隔最远的元素；然后比较距离次远的元素，依次类推，逐渐向基本的插入排序靠拢。
实际中，甚至在N为上万的情况下，希尔排序的性能也是相当好的。代码的简单性使它成为排序中等规模输入的良好算法。
平均运行时间降到O(N5/4)

4、归并排序

/**  Mergesort algorithm.*  @param a an array of Comparable items.*/public static void mergeSort( Comparable [] a){      Comparable [] tmpArray = new Comparable[a.length];      mergeSort( a, tmpArray, 0 , a.length-1 );}/** Internal method that makes recursive calls.* @param a an array of Comparable items.* @param tmpArray an array to place the merged result.* @param left the left-most index of the subarray.* @param right the right-most index of the subarray.*/private static void mergeSort( Comparable [] a, Comparable[] tmpArray, int left, int right){   if( left < right ){      int center = (left + right) / 2;      mergeSort(a, tmpArray, left, center);      mergeSort(a, tmpArray, center + 1, right);      merge(a, tmpArray, left, center+1, right);   }}/** Internal method that merges two sorted halves of a subarray.* @param a an array of Comparable items.* @param tmpArray an array to place the merged result.* @param leftPos the left-most index of the subarray.* @param rightPos the index of the start of the second half.* @param rightEnd the right-most index of the subarray.*/private static void merge(Comparable [] a, Comparable [] tmpArray,                         int leftPos, int rightPos, int rightEnd){    int leftEnd = rightPos - 1;    int tmpPos = leftPos;    int numElements = rightEnd - leftPos + 1;    while( leftPos <= leftEnd && rightPos <= rightEnd)          if (a[leftPos].compareTo( a[rightPos] ) < 0 )              tmpArray[tmpPos++] = a[leftPos++];          else              tmpArray[tmpPos++] = a[rightPos++];    while ( leftPos <= leftEnd )           tmpArray[tmpPos++] = a[leftPos++];    while ( rightPos <= rightEnd )           tmpArray[tmpPos++] = a[rightPos++];    for( int i=0; i< numElements; i++, rightEnd --)          a[rightEnd] = tmpArray[rightEnd];}

运行时间是O(NlogN),但几乎不用它作为内存排序算法。问题在于归并两个有序数组需要额外内存，另外还有复制临时数组拷回原数组的额外操作。