C++中十种内部排序算法的比较分析

C++中十种内部排序算法的比较分析

#include<iostream>
#include<ctime>
#include<fstream>

using namespace std;
#define MAXSIZE 1000  //可排序表的最大长度
#define SORTNUM 10   //测试10中排序方法
#define max 100    //基数排序时数据的最大位数不超过百位;
typedef struct node {
  int data3;
  int next;
} node;
typedef int DataType[MAXSIZE+2];
DataType data;
DataType data2;
DataType R1;
int size;//可排序表的长度
int head;
int fr[10];
int re[10];
long compCount;//统计比较次数
long shiftCount;//统计移动次数

 void BeforeSort()//对比较次数和移动次数清零
 {
   compCount=0;
   shiftCount=0;
 }

bool Less(int i,int j)//若表中第i个元素小于第j个元素,则返回True,否则返回False
 {
   compCount++;
   return data[i]<data[j];
 }

 void Swap(int i,int j)//交换表中第i个和第j个元素
 {
   int a;
   a=data[i];
   data[i]=data[j];
   data[j]=a;
   shiftCount=shiftCount+3;
 }

 void Shift(DataType &R,DataType &R2,int i,int j)//将R2[j]赋给R[i]
 {
   R[i]=R2[j];
   shiftCount++;
 }

 void CopyData(DataType list1,DataType list2)
 {
   int i;
   for(i=1;i<=size;i++) list2[i]=list1[i];

 }

 void InverseOrder()//将可排序表置为逆序
 {
   int i,j;
   for(i=1,j=size;i<=size/2;i++,j--)
   {
     int a;
     a=data[i];
     data[i]=data[j];
     data[j]=a;
   }
   CopyData(data,data2);
 }

 void RandomizeList()//由系统随机一组数
 {
   int i;
   srand(time(0));
   for(i=1;i<=size;i++)
     data[i]=rand()%(size+1);
   CopyData(data,data2);
   ofstream out_stream;
   out_stream.open("input.txt",ios::app);
   if(out_stream.fail())
   {
     cout<<"input file opening failed.\n";
     exit(1);
   }
   for(i=1;i<=size;i++) out_stream<<data[i]<<" ";
   out_stream<<"\n";
   out_stream.close();
 }

void RecallList()//恢复最后一次用RandomizeList随机打乱的可排序表
 {
   CopyData(data2,data);
 }

 void output()//输出函数
 {
   ofstream out_stream;
   cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
   out_stream.open("output.txt",ios::app);
   if(out_stream.fail())
   {
     cout<<"Output file opening failed.\n";
     exit(1);
   }
   out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
   out_stream.close();
 }

 void BubbleSort()//冒泡排序
 {
   BeforeSort();
   int swapped,i,m;
   m=size-1;
   do{
     swapped=0;
     for(i=1;i<=m;i++)
     {
       if(Less(i+1,i))
       {
         Swap(i+1,i);
         swapped=1;
       }
     }
     m--;
   }while(swapped);
   output();
 }

 void InsertSort() //插入排序
 {
   BeforeSort();
   int i,j;
   for(i=2;i<=size;i++)
   {
     Shift(data,data,0,i);
     j=i-1;
     while(Less(0,j))
     {
       Shift(data,data,j+1,j);
       j--;
     }
     Shift(data,data,j+1,0);
   }
   output();
 }

 void SelectSort()//选择排序
 {
   BeforeSort();
   int i,j,min;
   for(i=1;i<=size-1;i++)
   {
     min=i;
     for(j=i+1;j<=size;j++)
       if(Less(j,min)) min=j;
     if(i!=min) Swap(i,min);
   }
   output();
 }

 int Partition(int low,int high)
 {
   int pivotkey;
   Shift(data,data,0,low);
   pivotkey=data[low];
   while(low<high)
   {
     compCount++;
     while(low<high&&data[high]>=pivotkey) {compCount++;--high;}
     Shift(data,data,low,high);
     compCount++;
     while(low<high&&data[low]<=pivotkey) {compCount++;++low;}
     Shift(data,data,high,low);
   }
   Shift(data,data,low,0);
   return low;

 }

 void QSort(int low,int high)//QuickSort的辅助函数
 {
   int pivotloc;
   if(low<high)
   {
     pivotloc=Partition(low,high);
     QSort(low,pivotloc-1);
     QSort(pivotloc+1,high);
   }
 }

 void QuickSort()//快速排序
 {
   BeforeSort();
   QSort(1,size);
   output();
 }

 void ShellSort()//希尔排序
 {
   BeforeSort();
   int i,j,h;
   i=4;
   h=1;
   while(i<=size)
   {
     i=i*2;
     h=2*h+1;
   }
   while (h!=0)
   {
     i=h;
     while(i<=size)
     {
       j=i-h;
       while(j>0&&Less(j+h,j))
       {
         Swap(j,j+h);
         j=j-h;
       }
       i++;
     }
     h=(h-1)/2;
   }
   output();
 }

 void Sift(int left,int right)//堆排序的调堆函数
 {
   int i,j,finished=0;
   i=left;
   j=2*i;
   Shift(data,data,0,left);
   Shift(data,data,MAXSIZE+1,left);
   while(j<=right&&!finished)
   {
     if(j<right&&Less(j,j+1)) j=j+1;
     if(!Less(0,j)) finished=1;
     else
     {
       Shift(data,data,i,j);
       i=j;
       j=2*i;
     }
   }
   Shift(data,data,i,MAXSIZE+1);
 }

 void HeapSort()//堆排序
 {
   int left,right;
   BeforeSort();
   for(left=size/2;left>=1;left--) Sift(left,size);
   for(right=size;right>=2;right--)
   {
     Swap(1,right);
     Sift(1,right-1);
   }
   output();
 }

void BInsertSort()//折半插入排序
{
  BeforeSort();
  int i,low,high,m,j;
  for(i=2;i<=size;i++)
  {
    Shift(data,data,0,i);
    low=1;
    high=i-1;
    while(low<=high)
    {
      m=(low+high)/2;
      if(Less(0,m)) high=m-1;
      else low=m+1;
    }
    for(j=i-1;j>=high+1;j--) Shift(data,data,j+1,j);
    Shift(data,data,high+1,0);
  }
  output();
}

void Binsort()//2-路插入排序
{
 BeforeSort();
 int i,k,j;
 int first,last;
 first=last=1;
 Shift(R1,data,1,1);
 for(i=2;i<=size;i++)
 {
   compCount++;
   if(data[i]>=R1[1])
   {
     compCount++;
     j=last;
     while(j>=1&&R1[j]>data[i])
     {
       Shift(R1,R1,j+1,j);
       j--;
       compCount++;
     }
     Shift(R1,data,j+1,i);
     last++;
   }
   else
   {
     first--;
     if(first==0) first=size;
     j=first+1;
     compCount++;
     while(j<=size&&R1[j]<=data[i])
     {
       Shift(R1,R1,j-1,j);
       j++;
       compCount++;
     }
     Shift(R1,data,j-1,i);
   }
 }
 k=1;
 j=first;
 while(k<=size)
 {
  Shift(data,R1,k,j);
  k++;
  j=(j+1)%(size+1);
  if(j==0) j=j+1;
 }
 output();
}

void Merge(int low,int m,int high)
{
   int i=low,j=m+1,p=1;
   while(i<=m&&j<=high)
   {
     if(Less(i,j)) Shift(R1,data,p++,i++);
     else Shift(R1,data,p++,j++);
   }
   while(i<=m)
     Shift(R1,data,p++,i++);
   while(j<=high)
     Shift(R1,data,p++,j++);
   for(p=1,i=low;i<=high;p++,i++)
     Shift(data,R1,i,p);
}

void MSort(int low, int high)
{
 int mid;
 if (low<high){
  mid=(low+high)/2;
  MSort(low, mid);
  MSort(mid+1,high);
  Merge(low, mid, high);
 }
} 

void MergeSort()//归并排序
{
  BeforeSort();
  MSort(1,size);
  output();
}

void Distribute(node *a, int w)
{
  int i;
  for (i=0; i<10; i++) fr[i] = -1;
  for (i=head; i!=-1; i=a[i].next)
  {
    int x = a[i].data3 / w % 10;
    if (fr[x] == -1)
    {
      fr[x] = re[x] = i;
      compCount++;
    }
    else
    {
      a[re[x]].next = i;
      re[x] = i;
      shiftCount++;
    }
  }
  for (i=0; i<10; i++)
  {
    if (fr[i] != -1)
    {
      a[re[i]].next = -1;
    }
  }
}

void Collect(node *a)
{
  int i, last;

  last = -1;
  for (i=0; i<10; i++)
  {
    if (fr[i] != -1)
    {
      if (last == -1)
      {
        head = fr[i];
        last = re[i];
      }
      else {
        a[last].next = fr[i];
        last = re[i];
        shiftCount++;
      }
    }
  }
  a[last].next = -1;
}

void RadixSort()//基数排序算法。
{
  BeforeSort();
  ofstream out_stream;
  node* a;
  a=new node[size];
  int i,j=1;
  for (i=0; i<size; i++) {
    a[i].data3=data[i+1];
    a[i].next = i + 1;
  }
  head = 0;
  a[size-1].next = -1;
  for (i=1; i<=max; i*=10) {
    Distribute(a, i);
    Collect(a);
  }
  cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
  while (head != -1)
  {
    data[j++]=a[head].data3;
    head = a[head].next;
  }
  CopyData(data,data2);

  cout<<"\n";
  out_stream.open("output.txt",ios::app);
  out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n\n";
  out_stream.close();
}

void Initialization()//系统初始化
{
  system("cls");//清屏
  cout<<"***************************************************************************\n"
    <<"***************** 《内部排序算法的比较》 ********************************\n"
    <<"***************************************************************************\n"
    <<"************************ *主菜单* ***************************************\n"
    <<"******* 1.由系统随机产生待排序表 ****************************************\n"
    <<"******* 2.手动输入待排序表 **********************************************\n"
    <<"******* 3.返回主菜单 ****************************************************\n"
    <<"******* 4.退出程序 ******************************************************\n"
    <<"***************************************************************************\n"
    <<"请输入要执行的步骤:";
}

 void Interpret(int cmd)//调用各个算法
 {
   int i,j,m;
   ofstream out_stream;
   out_stream.open("output.txt",ios::app);
   if(out_stream.fail())
   {
     cout<<"Output file opening failed.\n";
     exit(1);
   }
   switch(cmd)
   {
   case 1:

    out_stream<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
    out_stream<<"\tcompCount\tshiftCount\n";
    out_stream.close();
    cout<<"请输入待排序表的长度:";
    cin>>size;
    cout<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
    RandomizeList();
    for(m=0;m<3;m++)
    {
      if(m==2) InverseOrder();
      cout<<"\t";
      for(i=1;i<=size;i++) cout<<data[i]<<" ";
      cout<<"\n";
      cout<<"\tcompCount\tshiftCount\n";
      for(j=0;j<SORTNUM;j++)
      {
        RecallList();
        out_stream.open("output.txt",ios::app);
        if(j==0) {cout<<"Bubbl: ";out_stream<<"Bubbl: ";out_stream.close();BubbleSort();}
        if(j==1) {cout<<"Tnser: ";out_stream<<"Tnser: ";out_stream.close();InsertSort();}
        if(j==2) {cout<<"Selec: ";out_stream<<"Selec: ";out_stream.close();SelectSort();}
        if(j==3) {cout<<"Quick: ";out_stream<<"Quick: ";out_stream.close();QuickSort();}
        if(j==4) {cout<<"Shell: ";out_stream<<"Shell: ";out_stream.close();ShellSort();}
        if(j==5) {cout<<"Heap : ";out_stream<<"Heap : ";out_stream.close();HeapSort();}
        if(j==6) {cout<<"BInse: ";out_stream<<"BInse: ";out_stream.close();BInsertSort();}
        if(j==7) {cout<<"Merge: ";out_stream<<"Merge: ";out_stream.close();MergeSort();}
        if(j==8) {cout<<"Bin : ";out_stream<<"Bin : ";out_stream.close();Binsort();}
        if(j==9) {cout<<"Radix: ";out_stream<<"Radix: ";out_stream.close();RadixSort();}

      }}

    //}

    break;
   case 2:

     cout<<"请输入待排序表的长度:";
     cin>>size;
     cout<<"请输入"<<size<<"个数据:\n";
     for(i=1;i<=size;i++) cin>>data[i];
     CopyData(data,data2);
     out_stream<<"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
     out_stream<<"\tcompCount\tshiftCount\n";
     out_stream.close();
     cout<<"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
     cout<<"\tcompCount\tshiftCount\n";
     for(j=0;j<SORTNUM;j++)
      {
        RecallList();
        out_stream.open("output.txt",ios::app);
        if(j==0) {cout<<"Bubbl: ";out_stream<<"Bubbl: ";out_stream.close();BubbleSort();}
        if(j==1) {cout<<"Tnser: ";out_stream<<"Tnser: ";out_stream.close();InsertSort();}
        if(j==2) {cout<<"Selec: ";out_stream<<"Selec: ";out_stream.close();SelectSort();}
        if(j==3) {cout<<"Quick: ";out_stream<<"Quick: ";out_stream.close();QuickSort();}
        if(j==4) {cout<<"Shell: ";out_stream<<"Shell: ";out_stream.close();ShellSort();}
        if(j==5) {cout<<"Heap : ";out_stream<<"Heap : ";out_stream.close();HeapSort();}
        if(j==6) {cout<<"BInse: ";out_stream<<"BInse: ";out_stream.close();BInsertSort();}
        if(j==7) {cout<<"Merge: ";out_stream<<"Merge: ";out_stream.close();MergeSort();}
        if(j==8) {cout<<"Bin : ";out_stream<<"Bin : ";out_stream.close();Binsort();}
        if(j==9) {cout<<"Radix: ";out_stream<<"Radix: ";out_stream.close();RadixSort();}
       }
     break;
   case 3:
     Initialization();
     break;
   }
 }

 void main()
 {
   Initialization();
   int cmd;
   do{
     cin>>cmd;
     Interpret(cmd);
   }while(cmd!=4);
 }

以上就是本文所述的全部内容了,希望能够对大家熟悉掌握这十种排序算法有所帮助。

时间: 2015-03-28

C++堆排序算法的实现方法

本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

C++ 数据结构 堆排序的实现

堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下

C++插入排序算法实例

插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

C++归并排序算法实例

归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

C++堆排序算法实例详解

本文实例讲述了C++堆排序算法.分享给大家供大家参考,具体如下: 堆中元素的排列方式分为两种:max-heap或min-heap,前者每个节点的key都大于等于孩子节点的key,后者每个节点的key都小于等于孩子节点的key. 由于堆可以看成一个完全二叉树,可以使用连续空间的array来模拟完全二叉树,简单原始的实现如下: #include<iostream> int heapsize=0;//全局变量记录堆的大小 void heapSort(int array[],int n){ void

C++冒泡排序算法实例

冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

C++实现各种排序算法类汇总

C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

C++选择排序算法实例

选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

解读堆排序算法及用C++实现基于最大堆的堆排序示例

1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

Python实现基于二叉树存储结构的堆排序算法示例

本文实例讲述了Python实现基于二叉树存储结构的堆排序算法.分享给大家供大家参考,具体如下: 既然用Python实现了二叉树,当然要写点东西练练手. 网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解. 但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序 其中最难的问题就是交换二叉树中两个节点. 因为一个节点最多与三个节点相连,那么两个节点互换,就需要考虑到5个节点之间的关系,也需要判断是左右孩子,这将是

C语言实现基于最大堆和最小堆的堆排序算法示例

堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

Swift实现堆排序算法的代码示例

算法思想 堆排序利用了最大堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单. 1.用最大堆排序的基本思想 (1)先将初始文件R[1..n]建成一个最大堆,此堆为初始的无序区 (2)再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key (3)由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-

Python实现的堆排序算法示例

本文实例讲述了Python实现的堆排序算法.分享给大家供大家参考,具体如下: 堆排序的思想: 堆是一种数据结构,可以将堆看作一棵完全二叉树,这棵二叉树满足,任何一个非叶节点的值都不大于(或不小于)其左右孩子节点的值. 将一个无序序列调整为一个堆,就可以找出这个序列的最大值(或最小值),然后将找出的这个值交换到序列的最后一个,这样有序序列就元素就增加一个,无序序列元素就减少一个,对新的无序序列重复这样的操作,就实现了排序. 堆排序的执行过程: 1.从无序序列所确定的完全二叉树的第一个非叶子节点开始

详解堆排序算法原理及Java版的代码实现

概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

图文详解Heap Sort堆排序算法及JavaScript的代码实现

1. 不得不说说二叉树 要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree).二叉树常被用于实现二叉查找树和二叉堆. 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒.二叉树的第 i 层至多有 2i - 1 个结点:深度为 k 的二叉树至多有 2k - 1 个结点:对任何一棵二叉树 T,如果

PHP实现的堆排序算法详解

本文实例讲述了PHP实现的堆排序算法.分享给大家供大家参考,具体如下: 经验 工作了,面试我工作这家公司时被技术面打击得不行,因为自己的数据结构等基础学得实在太差,虽然原来是想做设计师的说...不过看在PHP写得还凑合的份上能来实习了,但还是决心恶补一下基础. 其实自己之前也确实感觉到了基础的重要性,一些比较深的东西都比较底层,不学好根本没法进行.像我之前用PHP做websocket,就牵扯到数据包.数据帧等概念,搞不清楚,连数据都没法处理,还得后来补.所以我准备重新学一下数据结构,算法,网络等

Java 归并排序算法、堆排序算法实例详解

基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组