8.5 数据结构——归并排序和基数排序

8.5.1 归并排序

基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列，在内部排序中，通常采用2-路归并排序，即将两个位置相邻的有序子序列R[1~m]和R[m+1~n]归并为一个有序序列R[1~n]。

例：{48，，34，60，75，12，26，48'}

整个归并排序需要趟。

8.5.2 基数排序 

基本思想：分配+收集

也叫桶排序或箱排序，设置若干个箱子，将关键字为k的记录放入低k个箱子，然后按序号将非空的连接。

基数排序：数字是有范围的，均由0~9这十个数字组成，则只需设置十个箱子，相继按个、十、百……进行排序。

例：{614，738，921，485，637，101，215，790，306}

第一趟分配（按个位）：

第一趟收集：{530，790，921，101，614，485，215，306，637，738}

第二趟分配（按百位）：

第二趟收集：{101，306，614，215，921，530，637，738，485，790}

第三趟分配（按千位）：

第三趟收集：{101，215，306，485，530，614，637，738，790，921}