内蒙古大学《算法与数据结构》课件第7章排序

第7章排序7.1内部排序方式7.2插入排序7.3选择排序7.4交换排序

7.5归并排序7.6基数排序7.7各种内部排序算法的比较7.1内部排序方式排序：将一组数据按照排序码从小到大(或从大到小)的顺序进行排列。数据表（datalist）：是待排序数据元素的有限集合，有时称为待排序表。排序码(key):

通常数据元素有多个属性域,其中有一个属性域可用来区分数据,作为排序依据，该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。排序的确切定义：

设含有n个数据元素的序列为{R[0],R[1],……R[n-1]}，称为待排序表，其相应的排序码序列为{K[0],K[1],……K[n-1]}。需确定0，1，……，n-1的一种排列p[0],p[1],……p[n-1]，使各排序码满足下列的非递减（或非递增）关系：排序算法的稳定性:

如果在数据表中有两个数据R[i]和R[j],它们的排序码k[i]

==k[j]

,且在排序之前,数据R[i]排在R[j]前面。如果在排序之后,数据R[i]仍在数据R[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:

内排序是指在待排序数据全部放在内存中的排序；外排序是指由于待排序数据太多，无法同时把待排序数据存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:

排序的时间开销是衡量排序算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价一般都按平均情况进行衡量，对于那些受数据排序码序列初始排列及数据个数影响较大的，需要按最好情况和最坏情况进行估算。排序算法执行时所需的附加空间:

评价算法好坏的另一标准。待排序数据表的类定义：classElement{

KeyTypekey;//排序码fieldotherdata;//其它数据成员public:

KeyTypeKey(){returnkey;} //提取排序码voidsetKey(KeyTypex){key=x;}//修改}；//Elementclassdatalist

{//数据表ElementR[]; //存储向量

int

MaxSize,CurrentSize;//最大元素个数与当前元素个数public:

datalist(int

MaxSz=100){//构造函数

MaxSize=Maxsz;

CurrentSize=0;R=newElement[MaxSz];

}；//datalistvoidswap(Element&x,Element&y){//交换元素

Elementtemp=x;x=y;y=temp;}

voidInsertionSort();voidBinaryInsertSort();voidSelectSort();voidBubbleSort();voidShellsort();voidQuickSort(intleft,intright);voidMaxHeap_HeapSort();}//datalist7.2插入排序(InsertSorting)1、直接插入排序（基于顺序查找）2、折半插入排序（基于折半查找）3、希尔排序（基于逐趟缩小增量）7.2.1直接插入排序基本思想是：当插入第i(i2)

个数据时，前面的处理R[1],…,R[i-1]已经排好序。这时用R[i]的排序码与R[i-1],R[i-2],…的排序码顺序进行比较，直到R[j].key<=R[i].key(0j<i)将R[j+1],…,R[i-1]向后顺移,将R[i]插入到j+1位置处。

初始[50]2245800845*62i=2[2250]45800845*62i=3[224550]800845*62i=4[22455080]0845*62i=5[0822455080]45*62i=6[08224545*5080]62i=7[08224545*508062]01234567例如：给出初始排序码序列502245800845*62

的直接插入排序示意图。

图7.1直接插入排序示例直接插入排序的算法如下：voidInsertionSort(){

//按排序码Key非递减顺序对数据表进行直接插入排序

for(i=2;i<=CurrentSize;i++){if(R[i].Key<R[i-1].Key){R[0]=R[i];for(j=i-1;R[0].Key<R[j].Key;j--)R[j+1]=R[j];R[j+1]=R[0];}}}//InsertionSort最好的情况（排序码有序）：“比较”的次数：最坏的情况（排序码逆序）：“比较”的次数：“移动”的次数：“移动”的次数：直接插入排序算法分析：0平均的情况：若待排序数据序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的排序码比较次数和数据移动次数约为因此，直接插入排序的时间复杂度为O(n2)。空间效率：O(1)——因为仅占用1个缓冲单元R[0]直接插入排序是一种稳定的排序方法。直接插入排序算法分析：7.2.2折半插入排序(BinaryInsertsort)基本思想是:设在数据表中有一个数据序列R[1],R[2],…,R[n]。其中,R[1],R[2],…,R[i-1]是已经排好序的数据。在插入R[i]时,利用折半查找法寻找R[i]的插入位置。14364952805861239775ileftrightmmleftleftmrightileftrightmrightmrightmleft例如:插入位置插入位置R再如:14364952586180

239775R折半插入排序示例折半插入排序的算法如下：voidBinaryInsertSort(){for(i=2;i<=CurrentSize;i++){left=1,right=i-1;R[0]=R[i];flag=1;

while(left<=right)&&flag{middle=(left+right)/2; if(R[0].Key<R[middle].Key)right=middle-1;elseif(R[0].Key>R[middle].Key)left=middle+1;elseflag=0;//遇到有相同排序码的元素时，停止寻找

}if(!flag)//当flag＝0时，说明序列中存在有相同排序码的元素

left=middle;//此时元素需从R[middle]到R[i-1]向后顺移元素

for(k=i-1;k>=left;k--)//元素后移R[k+1]=R[k];

R[left]=R[0];}//for}//BinaryInsertSort3515455025102030折半插入排序的算法分析:折半插入的比较次数或者是查找成功时进行或者是不成功进行的。查找成功指针停留在判定树中某个结点上。查找不成功时查找指针停留在某个外结点（失败结点）.时间效率：比较次数:

在插入第i个数据时,最多需要经过log2(i+1)次排序码比较，才能确定它应插入的位置。因此，将n个数据用折半插入排序所进行的排序码比较次数为：O(n*log2n)折半插入排序的算法分析:空间效率：

O(1)(R[0])但是移动次数并未减少，所以折半插入排序效率仍为O(n2)

折半查找排序是不稳定的排序

7.1.3希尔排序(ShellSort)希尔排序又称为缩小增量排序。

基本思想:

首先取一个整数d<n

作为间隔,将全部数据分为d个子序列,所有距离为d的数据放在同一个子序列中,

在每一个子序列中分别施行直接插入排序。然后缩小间隔d,

例如取d=d/2，重复上述的子序列划分和排序。直到最后取d=1,

将所有数据放在同一个序列中排序为止。其中，d

称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}7.1.3希尔排序(ShellSort)例：排序码序列T=(49，38，65，97,76,13,27,49*,55,04）请写出希尔排序的具体实现过程。结论：开始时d

的值较大，子序列中的数据较少，排序速度较快；随着排序进展，d

值逐渐变小，子序列中数据个数逐渐变多，由于前面工作的基础，大多数数据已基本有序，所以排序速度仍然很快。380123456789104938659776132749*5504初态：第1趟(d=5)第2趟(d=3)第3趟(d=1)4913134938276549*975576042738

6549*9755135576045513270427044949*4949*763876

65

659797551327044949*3876

659713

270449*

76

97R[i]希尔排序的算法voidShellsort(){d=CurrentSize/2;//d是子序列间隔

while(d>=1){//当间隔d为零时，结束排序

ShellInsert(d);//调用一趟直接插入排序

d=d/2;//缩小增量d

}}//ShellsortvoidshellInsert(intd){

//一趟希尔排序，按间隔d划分子序列

for(inti=d+1;i<=CurrentSize;i++){R[0]=R[i]; for(j=i-d;j>0&&R[0].Key<R[j].Key;j-=d)R[j-d]=R[j];R[j+d]=R[j];}}//shellInsert算法分析：d的取法有多种。最初shell提出取d=n/2，d=d/2，直到d=1。knuth

提出取d=d/3+1。还有人提出都取奇数为好，也有人提出各d互质为好。对特定的待排序数据序列，可以准确地估算排序码的比较次数和数据移动次数。Knuth利用大量实验统计资料得出:

当n很大时，排序码平均比较次数和数据平均移动次数大约在n1.25到1.6n1.25的范围内。Shell排序是不稳定的排序。7.3选择排序基本思想:

每一趟(例如第i趟,i=1,…,n-1)与后面n-i个待排序数据中选出的排序码最小的数据交换.选择排序有多种具体实现算法：1)

直接选择排序

2)树形选择排序(锦标赛排序)

3)

堆排序直接选择排序是一种简单的排序方法,它的基本步骤是：在一组数据R[i](i=1,…,n-1)～R[n]中选择具有最小排序码的数据；

若它不是这组数据中的第一个数据,则将它与这组数据中的第一个数据对调;7.3.1直接选择排序

(SelectSort)例如：初始排序码序列：[504580620845*22]i=108[4580625045*22]i=20822[80625045*45]i=3082245*[62508045]i=4082245*45[508062]i=5082245*4550[8062]i=6082245*455062[80]

图7.2直接选择排序示例直接选择排序的算法如下：voidSelectSort(){

for(i=1;i<CurrentSize;i++){ k=i; for(j=i+1;j<=CurrentSize;j++){if(R[j].Key<R[k].Key)k=j;//k记当前具有最小排序码的元素下标

}forif(k!=i)swap（R[i]，R[k]）; }for}//SelectSort直接选择排序算法分析：直接选择排序的排序码比较次数与数据的初始排列无关。设整个待排序数据序列有n个数据,则第i趟(i=1,…,n-1)选择具有最小排序码数据所需的比较次数是n-i次。总的排序码比较次数为：数据的移动次数与数据序列的初始排列有关。当这组数据的初始序列有序时,数据的移动次数0，达到最少。最坏情况是每一趟都要进行交换，总的数据移动次数为

3(n-1)。直接选择排序算法的时间效率为：O(n2)直接选择排序算法的空间效率为：O(1)直接选择排序是一种不稳定的排序方法。

7.3.2树形选择排序基本思想：与体育比赛时的锦标赛类似。首先取

n个数据的排序码,

进行两两比较,得到

n/2

个优胜者(排序码小者),作为第一步比较的结果保留下来。然后对这

n/2

个数据再进行排序码的两两比较,…,如此重复,直到选出一个排序码最小的数据为止。∞如果n不是2的k次幂，则让叶结点数补足到满足2k-1<n≤2k的2k个。叶结点上面一层的非叶结点是叶结点排序码两两比较的结果。最顶层是树的根。08Winner

2108086325*2121254925*160863tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]胜者树胜者树的概念每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。胜者树最顶层是树的根，表示最后选择出来的具有最小排序码的数据。∞08Winner

2108086325*2121254925*160863tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]tree[14]R[0]胜者树

形成初始胜者树（最小排序码上升到根）∞16Winner

(胜者)2116166325*2121254925*16∞63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]R[1]输出冠军并调整胜者树后树的状态∞21Winner

(胜者)2163∞6325*2121254925*∞∞63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]输出亚军并调整胜者树后树的状态R[2]∞25Winner

(胜者)2563∞6325*25∞254925*∞∞63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]输出第三名并调整胜者树后树的状态R[3]∞25*Winner(胜者)25*63∞6325*∞∞∞4925*∞∞63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]输出第四名并调整胜者树后树的状态R[4]∞49Winner(胜者)4963∞6349∞∞∞49∞∞∞63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]输出第五名并调整胜者树后树的状态R[5]∞63Winner

(胜者)∞63∞63∞∞∞∞∞∞∞∞63tree[7]tree[8]tree[9]tree[10]tree[11]tree[12]tree[13]

tree[14]全部比赛结果输出时树的状态R[6]若n=2k,锦标赛排序构成的胜者树是一个满二叉树,其深度为k。除第一趟选择具有最小排序码的数据需要进行

n-1

次排序码比较外,重建胜者树选择具有次小、再次小排序码数据所需的排序码比较次数均为k次。总排序码比较次数为O(nk)=O(nlog2n)。数据的移动次数不超过排序码的比较次数，所以锦标赛排序总时间复杂度为O(nlog2n)。树形选择排序算法分析:若n2k,则补充叶结点数，使之成为一个满二叉树，除第一趟选择具有最小排序码的数据最多需要进行

n-1

次排序码比较外,其它重建胜者树选择具有次小、再次小排序码数据所需的排序码比较次数最多为log2n次。总排序码比较次数为O(nlog2n)。这种排序方法虽然减少了许多排序时间,但是使用了较多的附加存储(n-1个存储单元)。锦标赛排序是一个稳定的排序方法。树形选择排序算法分析:7.3.3堆排序堆排序是对树形选择排序的改进，它的时间复杂度同树形选择排序，O(nlog2n)。但只需一个元素的附加空间，从第四章可知，完全二叉树可以用一个数组表示，在这种表示法中，容易确定一个结点的双亲结点和左右子女的下标。堆的定义：n个元素的排序码序列{k1,k2,…,kn}，当且仅当满足如下关系时：

(i=1，2，…，n/2)则称之为堆。例如:初始排序码序列

3852456438*18下标

123456不是堆例：序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,55,67）判断它们是否“堆”？918566765855234561677最大堆082546495867234561最小堆堆排序的算法思想：首先建立最大堆。将heap[1]与heap[n]交换，把剩余的元素heap[1],…heap[n-1]再整理成堆，新堆的根heap[1]是集合中具有第二大排序码的元素，将heap[1]再与heap[n-1]交换,再把剩余的元素heap[1]，…，heap[n-2]整理成堆，如此重复，直到全部元素有序。实现堆排序需要解决两个问题：(1)如何将一个无序序列建成一个最大堆，即建堆；(2)如何在输出堆顶元素之后，把剩余元素调整成为一个新的堆，即堆调整。（1）如何建堆步骤：从最后一个分支结点开始往前逐步向前调整，让每个双亲小于或等于(大于或等于)它的左右子女，直到根结点为止。注：叶结点没有子女，无需单独调整。自下向上逐步调整为最小堆例:将一组序列53,17,78,09,45,65,87,23建立最小堆。=4=3例:将一组序列53,17,78,09,45,65,87,23建立最小堆。=2=211例:将一组序列53,17,78,09,45,65,87,23建立最小堆。11例:将一组序列53,17,78,09,45,65,87,23建立最小堆。例:将一组序列38,52,45,64,38*,18建立最大堆。（2）调整堆在堆排序过程中，主要的工作是调整堆。假设heap[1],…heap[n]是初始最大堆，heap[1]是排序码最大数据元素。将heap[1]与heap[n]的元素进行交换，再对heap[1],…,heap[n-1]进行调整，使之成为最大堆，依此重复n-1次。最大堆的向下调整算法如下：voidMaxHeap_HeapAdjust(inti,int

EndOfHeap){//i为调整堆的开始位置，EndOfHeap为调整堆的结束位置

current=i;child=2*i;heap[0]=heap[i];//heap[0]用作临时存储单元

while(child<=EndOfHeap){

if(child<EndOfHeap&&heap[child].Key<heap[child+1].Key)child=child+1;if(heap[0].Key>=heap[child].Key)break; else{

heap[current]=heap[child];current=child;child=2*child;}}

heap[current]=heap[0];}//MaxHeap_HeapAdjust

堆排序的算法：voidMaxHeap_HeapSort(){

//对表heap[1]到heap[n]进行排序,使得表中各个元素按其排序码非递减有序。

for(i=n/2；i>0；i--)

MaxHeap_HeapAdjust(i,n);//建立最大堆

for(i=n；i>1；i--){swap(heap[1]，heap[i]);//交换

MaxHeap_HeapAdjust(1，i-1);//重建大顶堆

}}//MaxHeap_HeapSort堆排序算法分析：

堆排序的时间复杂度为O(nlog2n)。该算法的附加存储是用heap[0]作为临时存储单元，所以空间复杂度为O(1)。堆排序也是一个不稳定的排序方法。7.4交换排序7.4.1冒泡排序(BubbleSort)基本思想：相邻元素的排序码进行比较，若位置不合适（下标小的排序码比下标大的排序码大），则交换它们，直到在某一趟时，没有元素交换或做n-1趟，例如：序号排序码第一遍第二遍第三遍第四遍第五遍13615

15151515

2223622222222

3652236272727

4996527363636

5159965454545

665279965656572765459965658454565659999

图7.7冒泡排序示例图冒泡排序的算法:voidBubbleSort(){exchange=1;for(i=1;i<CurrentSize&&exchange;++i){exchange=0; //交换标志置为0，假定未交换

for(j=CurrentSize;j>=i;j--){if(R[j-1].Key>R[j].Key){ //逆序Swap(R[j-1],R[j]);//交换exchange=1;//交换标志置为1,有交换}//if}//for

}//for}//BubbleSort算法分析：最好情况：当待排序列已经有序时，此算法只执行一趟冒泡，做n-1次比较，不移动元素，这是最好的情形。最坏情况：算法执行n-1趟冒泡，第i趟做n-i次比较，执行n-i次元素交换。这样在最坏情形下总的比较次数KCN和元素移动次数EMN为：冒泡排序需要一个附加单元以实现元素的对换。冒泡排序的时间复杂度为O(n2)，它也是一个稳定的排序方法。7.4.2快速排序(QuickSort)基本思想：

取待排序数据序列中的某个数据(例如取第一个数据)作为基准点,按照该数据的排序码大小,将整个数据序列划分为左右两个子序列：左侧子序列中所有数据的排序码都小于或等于基准点数据的排序码。右侧子序列中所有数据的排序码都大于基准点数据的排序码。对左右两个子序列分别进行快速排序。例如：基准位置pivot.Key=38

初始排序码3845526038*186430

ij进行1次交换之后3045526038*1864ij进行2次交换之后30526038*186445

ij进行3次交换之后3018526038*6445ij进行4次交换之后30186038*526445ij进行5次交换之后301838*60526445

ij进行6次交换之后301838*60526445

ij一趟快速排序示例快速排序的算法思想为：voidQuickSort(){if(List的长度大于1){

将序列List划分为两个子序列LeftList

和RightList;

QuickSort(LeftList);

QuickSort(RightList);

将两个子序列LeftList

和RightList合并为一个序列List;}}//QuickSort

快速排序的递归算法：voidQuickSort(intleft,intright){ //在待排序区间left~right中递归地进行快速排序

if(left<right){

int

pivotpos=Partition(left,right);//划分

QuickSort(R,left,pivotpos-1);

//在左子区间递归进行快速排序

QuickSort(R,pivotpos+1,right);

//在右子区间递归进行快速排序}}//QuickSort对一个序列进行划分的算法：intPartition(intlow,inthigh){Elementpivot=R[low]; i=low;j=high;while(i<j){//从表的两端交替地向中间扫描while(i<j&&R[j].Key>pivot.Key)--j;if(i<j)R[i]=R[j];

//将比基准元素排序码小的元素移到左侧

while(i<j&&R[i].Key<=pivot.Key)++i;if(i<j)R[j]=R[i];//大于基准元素的交换到区右侧去

}R[i]=pivot;returni;}//Partition快速排序算法分析：设每个子表的基准点都在中间（比较均衡），则：第1趟比较，可以确定1个元素的位置；第2趟比较（2个子表），可以再确定2个元素的位置；第3趟比较（4个子表），可以再确定4个元素的位置；第4趟比较（8个子表），可以再确定8个元素的位置；

……第k趟比较（2k-1个子表），可以再确定2k-1个元素的位置；1、时间复杂度(最好与平均情况)每一趟最多比较n-1次，最多移动n+1次。共可确定20＋21＋…＋2k-1=2k个元素的位置。当2k≥n时，排序结束。则只需k=log2n

趟便可排好序。O(nlog2n)时间复杂度为：快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的深度一致，理想情况为log2n

。因此，要求空间开销为O(log2n)，最坏情况下附加存储空间(即栈)将达到O(n)快速排序是一种不稳定的排序方法。对于n较大的平均情况而言，快速排序是“快速”的，但是当n很小时，这种排序方法往往比简单排序方法还要慢。用第一个数据作为基准数据

快速排序退化的例子

08

16212525*4908012345pivot初始

16212525*49

0816

212525*4921

081625

2525*49

081621

25*4925*

0816212549

0816212525*i=1i=2i=3i=4i=5最坏情况:O(n2)

改进办法:

取每个待排序数据序列的第一个数据、最后一个数据和位置接近正中的3个数据的平均值，取其排序码居中者作为基准点数据。快速排序是对冒泡排序的改进序号排序码第一趟第二趟第三趟第四趟第五趟13615

15151515

2223622222222

3652236272727

4996527363636

5159965454545

665279965656572765459965658454565659999

图7.7冒泡排序示例图思考题:(1)对n=7给出一个最好情况下的初始排列。(2)n=7时在最好情况下需进行多少次比较?快速排序思考题：(1)41326577.5归并排序归并是将两个或两个以上的有序表合并成一个新的有序表。08212525*496272931637540816212525*374954627293数组R1中两个有序表R1[l..m]和R1[m+1..n]。把它们归并成一个有序表,存于另一个数组R2[l..n]

中。这种归并方法称为2路归并例如：初始排序码[52][33][65][80][73][23][29]第一趟归并[3352][6580][2373][29]第二趟归并[33526580][232973]第三趟归并[23293352657380]08212525*49627293163754lmm+1pR1ij0816212525*374954627293lpkR2设变量i

和j分别是表R1[l]…R1[m]

和R1[m+1]…R1[n]的当前检测指针。变量k是存放指针。2路归并排序算法如下：

voidMerge(ElementR1[],ElementR2[],intl,int

m,intp){

/*R1[l..m]与R1[m+1...p]是两个有序表，将这两个有序表归并成一个有序表R2[l..p]*/i=l;j=m+1;k=l;

while(i<=m&&j<=p){//两两比较if(R1[i].Key<=R1[j].Key){R2[k]=R1[i];i++;k++;}else{R2[k]=R1[j];j++;k++;}}//whileif(i<=m)for(;i<=m;i++,k++)R2[k]=R1[i];elsefor(;j<=p;j++,k++)R2[k]=R1[j];}最多比较次数是两个子序列的长度和减1:m-l+1+p-(m+1)+1-1=p-l若两个子序列的长度为len,则为最多比较次数是2*len-1一趟归并排序的思想：设数组R1[0..n-1]中的n个元素已经分为一些长度为len的归并项，将这些归并项两两归并，归并成一些长度为2*len的归并项，结果放到R2中。如果n不是2*len的整数倍，则一趟归并到最后，可能遇到两种情形：（1）剩下一个长度为len的归并项和另一个长度不足len的归并项，可调用一次Merge算法，将它们归并成一个长度小于2*len的归并项。（2）只剩下一个归并项，其长度小于或等于len，可将它直接复制到数组R2中。一趟归并排序算法如下：voidMergePass(ElementR1[],ElementR2[],int

len){

i=0;while(i+2*len<=n){//i+2*len-1<=n-1

Merge(R1,R2,i,i+len-1,i+2*len-1);i+=2*len;}

if(i+len<=n-1)

Merge(R1,R2,i,i+len-1,n-1);elsefor(intj=i;j<=n-1;j++)R2[j]=R1[j];}//MergePassMergePass做一趟2路归并排序，比较次数不超过元素个数n（2路）归并排序的主算法为:voidMergeSort(){//按元素排序码非递减的顺序对表R中元素排序

ElementtempList[MaxSize];

len=1;

while(len<n){

MergePass(R,tempList,len);len*=2;

MergePass(tempList,R,len);len*=2;}}//MergeSortMergeSort调用MergePass正好log2n

次非递归的归并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16算法分析:在归并排序算法中，算法总的时间复杂度为O(nlog2n)。归并排序占用附加存储空间较多，需要另外一个与原待排序元素数组同样大小的辅助数组，这是此算法的缺点。归并排序是一个稳定的排序方法。7.6基数排序基数排序是一种特殊的排序方法，它不经过排序码大小的比较，而是根据每个排序码分量的值来排列元素的顺序。基数排序采用“分配”与“收集”的办法，用对多排序码进行排序的思想实现对单排序码进行排序的方法。7.6.1多排序码排序以扑克牌排序为例，每张扑克牌有两个“排序码”：花色和牌点。其顺序关系为：花色：

♠

牌点：2<3<4<5<6<7<8<9<10<J<Q<K<A，花色是高位，牌点是低位，所有扑克牌的不减序列为：

2<3<…,<A<2<…<A<2<…<A<2<…<A对于上例两排序码的排序，可以先按花色排序，然后再按牌点排;也可以先按牌点排序，再按花色排序，这就是多排序码排序.实现多排序码排序有两种常用的方法：最高位优先MSD（MostSignificantDigitfirst）最低位优先LSD（LeastSignificantDigitfirst）一般情况下，假定有一个n个元素的序列{R[0],R[1],…,R[n-1]},且每个元素的排序码含有d个分量，如果对于序列中任意两个元素