D

此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项A、B、C都是相邻元素比较，是稳定的。所以选D。

C

此题考查的知识点是各类排序算法的思想。
   冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D错。
   直接插入排序思想是假设待排序的记录存放在数组R[n+1]中，排序过程中的某一时刻，R被分成两个子区间[R[1]，R[i-1]]和[R[i]，R[n]]，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第i个记录R[i]插入到有序区中的适当位置，使得R[1]到R[i]变为新的有序区。首先比较R[i]和R[i-1]，如果R[i-1]≤R[i]，则R[1..i]已排好序，第i遍处理就结束了；否则交换R[i]与R[i-1]的位置，继续比较R[i-1]和R[i-2]，直到找到某一个位置j(1≤j≤i-1)使得R[j]≤R[j+1]时为止。与序列初态有关，B错。
   快速排序是通过基准元素v把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于v：右边的各记录的关键字都大于等于v；重复该过程直到排好序。与序列初态有关，A错。
   二路归并是首先把每个记录看成是一个有序序列，共n个，将它们两两合并成[n/2]个分类序列，每个序列长度为2(当n为奇数时，最后一个序列长度为1)；对[n/2]个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为n的分类序列为止。与序列初态无关，所以选C。

C。此题考查的知识点是各类排序算法的效率。起泡排序比较n(n-1)/2次，没有交换次数i堆排序一次比较log₂n次，共需要n轮；直接插入排序比较n-1次，没有交换；二路归并排序一次比较log₂n次，共需要n轮。综上，应选C。

C。本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。

排序方法	平均时间性能	最好时间性能	最坏时间性能	辅助存储空间	稳定性
直接插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
简单选择排序	O(n2)	O(n)	O(n2)	O(1)	不稳定
快速排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(log2n)	不稳定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
基数排序	O(d(n+radix))	O(d(n+radix))	O(d(n+radix))	O(radix)	稳定

A

由这些排序方法的特点可知本题答案为A。    

C

此题考查的知识点是各类排序算法的思想。应选C。

A

此题考查的知识点是各类排序算法的思想。应选A。

D

此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较n-i次，快速排序结束后才能得到结果，堆排序可以在选择5次后得到结果，每次比较元素次数为log₂n。所以应选D。

A

只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆顶元素总是当前剩下元素的最大或最小的，本题答案为A。

B

本题根据简单选择排序法的算法思想可得答案B。

A

此题考查的知识点是各类排序算法的思想。应选A。

C

此题考查的知识点是冒泡算法的思想及过程。第一趟比较5次，第2趟比较4次，第3趟比较3次，第4趟比较2次，第5趟比较1次，结束。共15次，应选C。

D

完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：
   
   得出答案为D。

C

对于(46，79，56，38，40，84)，取出46，对(79，56，38，40，84)进行划分，先将79与40交换，得到(40，56，38，79，84)，再将56与38交换，得到(40，38，56，79，84)，将46插入得到(40，38，46，56，79，84)，本题答案为C。

C

简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i趟选择具有最小关键字对象所需的比较次数总是n-i-1次(此处假定整个待排序对象序列有n个对象)。因此，总的关键字比较次数为：
   
   最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n-1)。

A

此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1)，快速排序为O(log₂n)，归并排序为O(n)。应选A。

A

对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为A。

B

冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。

A

可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。

C

第6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入60，要与95、70和50进行比较，共比较3次，本题答案为C。

A

此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为N。

B

此题考查的知识点是分块排序的思想。因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog₂k)。可以用二叉树分治形式描述，最好的情况是树的高度为log₂k。全部时间下界为O(nlog₂k)。应选B。

A

根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：
   
   可以得出调整后的小根堆为3，5，12，8，28，20，15，22，19。

B

此题考查的知识点是归并排序。第l遍归并的子序列长度为2⁰，第2遍为2¹，…，第i遍为2^i-1，所以由2^i-1≥n知，对n个记录的数据集合，总共需要归并log₂n次。应选B。

C

此题考查的知识点是堆排序。应选C。

A

此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log₂(n!)次比较。
   由Stirling公式可知，log₂(n!)≈nlog₂n-1.44n+O(log₂n)。所以基于关键字比较的分类时间的下界是O(nlog₂n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

A

下表为各种排序方法的性能比较。由表可知，本题答案为A。

C

t=3，d₀=9，d₁=4，d₂=2，d₃=1，第1趟(d¹=4)后的结果为(15，40，60，20，50，70，95，45，80)，第2趟(d₂=2)后的结果为(15，20，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。

A

n=20，共需进行[log₂n]=5趟归并，第l趟归并后成为10个有序表，第2趟归并后成为5个有序表(每个长度为4)，第3趟归并将长度为4个的有序表归并为长度为8的有序表，本题答案为：5，4，8。

这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。

可以做到。取a与b进行比较，c与d进行比较。设a＞b，c＞d(a＜b和c＜d情况类似)，此时需2次比较，取b和d比较，若b＞d，则有序a＞b＞d：若b＜d时则有序c＞d＞b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。

将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较……比较中的小者放前半部，大者放后半部，用了n/2次比较。再在前后两部分中分别简单选择最小和最大元素，各用(n/2)-1次比较。总共用了(3n/2)-2次比较。显然，当n≥3时，(2n-3)＞(3n/2)-2。
   用分治法求解再给出另一参考答案。
   对于两个数x和y，经一次比较可得到最大值和最小值；对于三个数x，y，z，最多经3次比较可得最大值和最小值；对于n个数(n＞3)，将分成长为，n-2和2的前后两部分A和B，分别找出最大者和最小者：Max A，Min A，Max B，Min B，最后Max={Max A，Max B}和Min={Min A，Min B}。对A使用同样的方法求出最大值和最小值，直到元素个数不超过3。
   设C(n)是所需的最多比较次数，根据上述原则，当n＞3时有如下关系式：
   
   通过逐步递推，可以得到：C(n)=(3n/2)-2。显然，当n＞3时，2n-3＞(3n/2)-2。事实上(3n/2)-2是解决这一问题的比较次数的下限。

假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2^h-1；反之，若有u个叶子结点，则二叉树的高度至少为(log₂u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log₂(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log₂(n!)。根据斯特林公式，有log₂(n!)=O(nlog₂n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为

此题考查的知识点是基于比较的排序算法效率。

本题主要考查直接插入法的算法思想及性能分析。
   根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。
   (1)在关键字自小到大有序的情况下，插入第i个(2≤i≤n)元素的比较次数为1，因此，总的比较次数为1+1+1+…+1=n-1。
   (2)在关键字自大到小有序的情况下，插入第i个(2≤i≤n)元素的比较次数为i，因此，总的比较次数为2+3+4+…+n=[n(n+1)/2]-1=(n-1)(n+2)/2。
   (3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为n-1。
   (4)在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字时比较次数最少，此时前半部分的比较次数为m-1，后半部分的比较次数为(n-m-1)(n-m+2)/2，因此，总的比较次数为m-1+(n-m-1)(n-m+2)/2=(n-2)(n+8)/8(假设n为偶数，m=n/2)。

(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k-1，那么第一遍划分得到两个长度均为的子文件，第二遍划分得到4个长度均为的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，各需2次，共10次即可。
   (2)在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。
   (3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n²)。所以当n=7时，最坏情况下的比较次数为21次。
   (4)在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。

此题考查的知识点是快速排序的思想。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

(1)堆的存储是顺序的。
   (2)最大值元素一定是叶子结点，在最下两层上。
   (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：
   由于第i层上的结点数至多是2^i-1，以它为根的二叉树的深度为h-i+1，则调用次筛选算法时总共进行的关键字比较次数不超过下式之值：
   

此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K₁，K₂，…，K_n，当且仅当该序列满足如下性质(简称为堆性质)：
   (1)k_i≤K_2i且k_i≤K_2i+1或
   (2)k_i≥K_2i且k_i≥K_2i+1(1≤i≤n)。k_i相当于二叉树的非叶结点，K_2i则是左孩子，k_2i+1是右孩子。

K₁～K_n是堆，在K_n+1加入后，将K₁..K_n+1调成堆。设c=n+l，f=，若K_f≤K_c，则调整完成。否则K_f与K_c交换之后，c=f,f=，继续比较，直到K_f≤K_c，或f=0，即为根结点，调整结束。

void BubbleSort2 (int a[], int n){    //相邻两趟向相反方向起泡的冒泡排序算法
   int change=1; low=0; high=n-1;    //冒泡的上下界
   while(low＜high && change){
   change=0;    //交换标志
   for(i=low; i＜high; i++)    //从上向下起泡
   if(a[i]＞a[i+1]){ a[i]a[i+1]; change=1; }   //有交换，修改标志change
   high--;    //修改上界
   for(i=high; i＞low; i-- )    //从下向上起泡
   if(a[i]＜a[i+1]{a[i] a[i-1]; change=1;}
   low++;    //修改下界
   }
   }

此题考查的知识点是双向冒泡算法。题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。

typedef struct{
   int key;
   datatype info
   }RecType;
   void CountSort(RecType a[], b[], int n){    //计数排序算法，将a中记录排序放入b中
   int i,j,cnt;
   for(i=0; i＜n; i++){    //对每一个元素
   for(j=0, cnt=0; j    if(a[j].key＜a[i].key) cnt++;    //统计关键字比它小的元素个数
   B[cnt]=a[i];
   }
   }
   对于有n个记录的表，关键字比较n²次。
   简单选择排序算法比本算法好。简单选择排序的比较次数是n(n-1)/2，且只用一个交换记录的空间；而这种方法的比较次数是n²，且需要另一数组空间。

此题考查的知识点是计数排序思想。因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n²次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为：
   for(i=0; i＜n; i++) a[i].count=0;    //各元素再增加一个计数域，初始化为0
   for(i=0; i＜n; i++)
   for(j=i+1; j＜n; j++)
   if(a[i].key＜a[j].key) a[j].count++;
   else a[i].count++;

int Partition(RecType R[], int n, int h){
   //一趟快速排序算法，枢轴记录到位，并返回其所在位置
   int i=n, j=h, R[0]=R[i], x=R[i].key;
   while(i＜j){
   while(i＜j && R[j].key＞=x)j--;
   if(i＜j)R[i]=R[j];
   while(i＜j && R[i].key＜=x)i++;
   if(i＜j)R[j]=R[i];
   }//while
   R[i]=R[0];
   return i;
   }

此题考查的知识点是快速排序的思想。

int Partition(RecType K[], int m, int n){
   //交换记录子序列K[1..n]中的记录，使枢轴记录到位，并返回其所在位置
   //此时，在它之前(后)的记录均不大(小)于它
   int i m, j=n, K[0]=K[j], x=K[j].key;
   while(i＜j){
   while(i＜j && K[i].key＜=x) i++;
   if(i＜j) K[j]=K[i];
   while(i＜j && K[j].key＞=x) j--;
   if(i＜j) K[i]=K[j];
   }//while
   K[i]=K[0];
   return i;
   }

此题考查的知识点是快速排序的思想。以K_n为枢轴的一趟快速排序。以最后一个关键字为枢轴先从前向后再从后向前快速排序。

void sift(RecType R[], int n){    //把R[n]调成大堆
   int j=n; R[0]=R[j];
   for(i=n/2; i＞=1; i=i/2)
   if(R[0].key＞R[i].key){ R[j]=R[i]; j=i;}
   else break;
   R[j]=R[0];
   Void HeapBuilder(RecType R[], int n){
   for(i=2; i＜=n; i++) sift(R,i):
   }

此题考查的知识点是堆的插入算法。从第n个记录开始依次与其双亲(n/2)比较，若大于双亲则交换，继而与其双亲的双亲比较，以此类推直到根为止。

此题考查的知识点是堆的算法。将插入的元素放到最后，然后调整。
   (1)加入关键字值为5的结点后，最小最大堆如下图。
   
   (2)加入关键字值为80的结点后，最小最大堆如下图。
   
   (3)从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点；若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。
   void MinMaxHeaplns(RecType R[], int n){
   //假设R[1..n-1]是最小最大堆，插入第n个元素，把R[1..n]调成最小最大堆
   j=n; R[0]=R[j];
   h=log₂n+1;    //求高度
   if(h%2==0){    //插入元素在偶数层，是最大层
   1=n/2;
   if(R[0].key＜R[i].key){    //插入元素小于双亲，先与双亲交换，然后调小堆
   R[j]=R[i];
   j=i/4;
   while(j＞0 && R[j]＞R[i]){  R[i]=R[j]; i=j; j=i/4; }//调小堆
   R[i]=R[0];
   }
   else{    //插入元素大于双亲，调大堆
   i=n; j=i/4;
   while(j＞0 && R[j]＜R[i]){ R[i]=R[1]; i=j; j=i/4; }
   R[i]=R[0];
   }
   }
   else{    //插入元素在奇数层，是最小层
   i=n/2;
   if(R[0].key＞R[i].key){    //插入元素大于双亲，先与双亲交换，然后调大堆
   R[j]=R[i];
   j=i/4;
   while(j＞0 && R[j]＜R[i]){ R[i]=R[j]; i=j; j=i/4; }//调大堆
   R[i]=R[0];
   }
   else{    //插入元素小于双亲，调小堆
   i=n; j=i/4;
   while(j＞0 && R[j]＞R[i]){ R[i]=R[j]; i=j; j=i/4; }
   R[i]=R[0];
   }
   }

typedef struct{
   int key;
   int next;
   }SLRecType;
   SLRecType R[N+1];
   typedef struct{
   intf,e;
   }SLQueue;
   SLQueue B[10];
   int Radixsort(SLRecType R[], int n){    //设备关键字已输入到R数组中
   for(i=1;i＜n;i++) R[i].next=i+1;
   R[n].next=-1; p:1;    //-1表示静态链表结束
   for(i=0;i＜=9;i++){    //设置队头队尾指针初值
   B[i].f=-1; B[i].e=-1;
   }
   while(p!=-1){    //一趟分配
   k=R[p].key;    //取关键字
   if(B[k].f==-1) B[k].f=p;    //修改队头指针
   else R[B[k].e].next=p;
   B[k].e=p;
   p=R[p].next;    //下一记录
   }
   i=0;    //一趟收集
   while(B[i].f==-1) i++;
   t=B[i].e; p=B[i]f;
   while(i＜9){
   i++;
   if(B[i].f!=-1){ R[t].next=B[i].f; t=B[i].e;}
   }
   R[t].next=-1;
   return p;//返回第一个记录指针
   }

此题考查的知识点是基数排序。基数排序法又称“桶子法”(Bucket Sort)，它是透过键值的部分信息，将要排序的元素分配至某些“桶”中，达到排序的目的。基数排序法是属于稳定性的排序，其时间复杂度为O(dn)，其中d为所采取的基数，而n为关键字数。本题是基数排序的特殊情况，关键字只含一位数字的整数。若关键字含d位，则要进行d趟分配和d趟收集。关键字最好放入字符数组，以便取关键字的某位。

可以做到。取a与b进行比较，c与d进行比较。设a＞b，c＞d(a＜b和c＜d情况类似)，此时需2次比较，取b和d比较，若b＞d，则有序a＞b＞d：若b＜d时则有序c＞d＞b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。

上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，如果在一个大量数据的文件中，如含有15000个元素的记录文件中选取前10个最大的元素，宜采用堆排序。

(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2h-1，显然，第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各文件的长度均为1，此时排序结束。由于n=7，k=3，在最好情况下，第一遍经过6次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为3)进行排序，各需要2次，这样就可将整个文件排序完毕，从而知n=7的最好情况下需进行10次比较。例如：4，7，5，6，3，1，2。
   (2)在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小)，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为O(n²)，反而不快了。对于n=7的记录文件，显然最坏情况下的比较次数为21。例如：7，6，5，4，3，2，1。

依据堆定义可知：序列(1)、(2)、(4)是堆，(3)不是堆，从而可对其调整使之成为大根堆(100，95，65，85，80，60，40，75，82，10，20)。

因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为r，显然，十进制数基数为10，二进制数的基数为2。要建立r个空队列所需时间为O(r)；把n个记录分放到各个队列中，重新收集起来需要的时间为O(n)，因此一趟排序所需的时间复杂度为O(n+r)；若每个关键字有d位，则总共要进行d遍排序，所以基数排序的时间复杂度为O(d(n+r))。由于关键字的位数d与基数r和最大关键字取值有关。因此不同的r和关键字将需要不同的时间。所以，本题中总的时间复杂度为O(d(n+2))，d为关键字最大值对应的二进制数位数，即将十进制的关键字用二进制数表示时，复杂度增大了。另外只需要设置两个指针队列，即将十进制的关键字用二进制数表示时，空间复杂性减少了。

设对记录R[1..n]进行快速排序，要求用非递归算法。利用一个包含有low和high两个整数成员的记录数组stack[]作为栈，low和high成员分别指示某个子文件的首、尾记录的下标号。算法如下：
   void quicksort(SeqList R, int n){ //设待排序记录放在R[1..n]中，下标从1开始
   inti,j,low,high,top=0;
   struct{
   int low,high;
   }stack[Max];    //Max为一个大于n的常量
   RecType temp;
   top=1; stack[top].low=1; stack[top].high=n;   //入栈
   while(top＞0){    //栈非空，则取出一个子文件进行划分
   low=stack[top].low; high=stack[top].high; top--;  //出栈
   i=low; j=high; temp=R[i];
   do{
   while(i＜j && R[i].key＞temp.key)j--;
   if(i＜j){
   R[i]=R[j]; i++;
   while(i＜j && R[i].key＜temp.key) i++;
   if(i＜j){ R[j]=R[i]; j--;}
   }
   }while(i==j);    //划分结束
   R[i]=temp;    //基元元素插入
   if(i+1＜high){    //右子文件有两个以上记录，则首、尾位置入栈
   top++; stack[top].low=i+1; stack[top].high=high;
   }
   if(low＜i-1){    //左子文件有两个以上记录，则首、尾位置入栈
   top++; staCk[top].low=low; staCk[top].high=i-1;
   }
   }
   }

采用类似于快速排序中的划分思想。算法如下：
   void part(KeyType A[], int n){
   int i-1; j=n;
   KeyType temp;
   while(i＜j){
   while(i＜j && A[j]＞=0) j--;    //从右向左找负数
   while(i＜j && A[i]＜0) i++;    //从左向右找非负数
   if(i＜j){    //交换元素A[i]和A[j]
   temp=A[i]; A[i]=A[j]; A[j]=temp;
   i++; j--;
   }
   }
   }
   该算法的时间复杂度为O(n)。

建立堆的算法如下：
   void BuildHeap(SeqList R,KeyType A[n]){    //类型定义
   int i;
   R.len=0;    //初始化
   for(i=0; i＜n; i++) HeapInsert(R, A[i]);
   }