常用排序算法-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),但几乎不用它作为内存排序算法。问题在于归并两个有序数组需要额外内存，另外还有复制临时数组拷回原数组的额外操作。