从右向左扫描，找小于tmp.key，找到这样的R[j].key

Question

6、补充BEGIN-END之间的内容，完成快速排序算法
#include <stdio.h>
typedef int KeyType;    //定义关键字类型为int
typedef char InfoType;
typedef struct
{    KeyType key;        //关键字项
    InfoType data;        //其他数据项，类型为InfoType
} RecType;                //查找元素的类型
int partition(RecType R[],int s,int t)    //一趟划分
{
    int i=s,j=t;
    RecType tmp=R[i];            //以R[i]为基准
    while (i<j)                  //从两端交替向中间扫描,直至i=j为止
    {    
/**********BEGIN**********/
/*
从右向左扫描,找小于tmp.key的R[j].key,找到这样的R[j]则赋值到R[i]处
从左向右扫描,找一个大于tmp.key的R[i]，找到这样的R[i]则赋值到R[j]处
*/

    

/**********END**********/
    R[i]=tmp;
    return i;
}
void QuickSort(RecType R[],int s,int t) //对R[s..t]的元素进行快速排序
{    int i;
    RecType tmp;
    if (s<t)                     //区间内至少存在两个元素的情况
    {    i=partition(R,s,t);
        QuickSort(R,s,i-1);        //对左区间递归排序
        QuickSort(R,i+1,t);        //对右区间递归排序
    }
}

Answer 1

int partition(RecType R[],int s,int t) //一趟划分
{
int i=s,j=t;
RecType tmp=R[i]; //以R[i]为基准
while (i<j) //从两端交替向中间扫描,直至i=j为止
{
while (i<j && R[j].key>=tmp.key) j--;
if (i<j) R[i++]=R[j]; //将比基准小的元素移到左端
while (i<j && R[i].key<=tmp.key) i++;
if (i<j) R[j--]=R[i]; //将比基准大的元素移到右端
}
R[i]=tmp; //基准元素归位
return i;
}