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

正文

请到「今天看啥」查看全文

重复步骤直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

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 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 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 //copy the rest elements of the right half subarray. (only one loop will be execute)   
    while ( rPos //copy the tmpArr back cause we need to change the arr array items.   
    for ( ; rEnd >= leftTmp; rEnd-- )   
      arr[rEnd] = tmpArr[rEnd];   
  }   
}

归并排序有许多变种，比如梯级归并排序（Cascade Merge Sort）、振荡归并排序（Oscillating Merge Sort）和多相归并排序（Polyphase Merge Sort）。以多相归并排序为例，它经常用在外排序中，可以减少原始归并排序每次循环需要遍历的元素个数，因为原始的归并排序每次都做二路归并，在文件数量多的时候效率低下。

Strand排序（Strand Sort）

Strand排序不断地从待排序的序列中拉出排好序的子列表，并归并成一个最终的结果。该算法的平均和最坏时间复杂度都达到了O(n2)，最好时间复杂度为O(n)。Strand排序高效的条件要求：

• 以链表（linked list）方式存放的数据排序起来最为有效，因为它需要反复添加和移除元素，而链表添加移除元素的代价很小；

• 原始数据中已经很大程度上有序了，这样每次可以尽量多地拉出一个有序子列表数据。

举例来说，现在有原始列表（4，5，2，3，1）：

• 遍历元素，第一个元素4，拉出包含4的最长递增子序列：（4，5），原列表变成了（2，3，1）；

• 继续拉出最长递增子序列（2，3），和前面拉出的序列归并得到（2，3，4，5），原列表变成了 （1）；

• 拉出（1），归并得到（1，2，3，4，5）。

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

分布类排序

基数排序（Radix Sort）

相较于前面严格的比较排序，基数排序更多地利用了待排序元素本身的特性。待排序元素需要是整型，基数排序时将整数按照位数切分成不同的数字，然后按每个位数分别比较；但是推广一下，整数也可以表达字符串，和符合特定格式的浮点数，所以基数排序堆元素的要求进一步降低。具体实现步骤：

待比较元素统一成相同格式（例如短数前面补零），然后从最低位开始，依次进行一次排序，接着是次低位……直到最高位也完成排序。

例如有元素（432，546，723）：

• 第一遍按照个位数排序，变成（432，723，546）；

• 接着按照十位数排序：（723，432，546）；

请到「今天看啥」查看全文