对序列(503，87，512，61，908，170，897，275，653，426)使用快速排序（以第1个记录为枢轴）算法进行排序，补充函数，输出最后的排序结果。函数为：// 快速排序 #include "stdio.h" #define MAXSIZE 20 //顺序表的最大长度 typedef struct { int key; char otherinfo; }ElemType; //顺序表的存储结构 typedef struct { ElemType r[20]; //存储空间的基地址 int length; //顺序表长度 }SqList; //顺序表类型 void show(SqList L) { int i; for(i=1;i<=L.length;i++) printf("%4d",L.r[i].key); printf("\n"); } int Partition(SqList &L,int low,int high) { //对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置 //*************************************** //**************************************** }//Partition void QSort(SqList &L,int low,int high) { //调用前置初值：low=1; high=L.length; //对顺序表L中的子序列L.r[low..high]做快速排序 int pivotloc; if(low<high) { //长度大于1 pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二，pivotloc是枢轴位置 QSort(L,low,pivotloc-1); //对左子表递归排序 QSort(L,pivotloc+1,high);//对右子表递归排序 } }//QSort void QuickSort(SqList &L) { //对顺序表L做快速排序 QSort(L,1,L.length); } //QuickSort void main() { SqList L; L.r[1].key=503; L.r[2].key=87; L.r[3].key=512; L.r[4].key=61; L.r[5].key=908; L.r[6].key=170; L.r[7].key=897; L.r[8].key=275; L.r[9].key=653; L.r[10].key=426; L.length=10; QuickSort(L); printf("快速排序后的结果为："); show(L); }

下面是代码实现：

#include "stdio.h"
#define MAXSIZE 20 //顺序表的最大长度

typedef struct {
    int key;
    char otherinfo;
}ElemType; //顺序表的存储结构

typedef struct {
    ElemType r[MAXSIZE]; //存储空间的基地址
    int length; //顺序表长度
}SqList; //顺序表类型

void show(SqList L) {
    int i;
    for(i=1;i<=L.length;i++)
        printf("%4d",L.r[i].key);
    printf("\n");
}

int Partition(SqList &L,int low,int high) {
    //对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置
    int pivotkey=L.r[low].key; //将子表的第一个记录作为枢轴记录
    while(low<high) { //从表的两端交替地向中间扫描
        while(low<high&&L.r[high].key>=pivotkey) high--;
        L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端
        while(low<high&&L.r[low].key<=pivotkey) low++;
        L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端
    }
    L.r[low].key=pivotkey; //枢轴记录到位
    return low; //返回枢轴位置
}

void QSort(SqList &L,int low,int high) {
    //调用前置初值：low=1; high=L.length;
    //对顺序表L中的子序列L.r[low..high]做快速排序
    int pivotloc;
    if(low<high) { //长度大于1
        pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二，pivotloc是枢轴位置
        QSort(L,low,pivotloc-1); //对左子表递归排序
        QSort(L,pivotloc+1,high);//对右子表递归排序
    }
}

void QuickSort(SqList &L) {
    //对顺序表L做快速排序
    QSort(L,1,L.length);
}

void main() {
    SqList L;
    L.r[1].key=503;
    L.r[2].key=87;
    L.r[3].key=512;
    L.r[4].key=61;
    L.r[5].key=908;
    L.r[6].key=170;
    L.r[7].key=897;
    L.r[8].key=275;
    L.r[9].key=653;
    L.r[10].key=426;
    L.length=10;
    QuickSort(L);
    printf("快速排序后的结果为：");
    show(L);
}

输出结果为：

快速排序后的结果为：  61  87 170 275 426 503 653 897 908 512