快速排序算法王道书上的问题

img
快速排序一定要基准左边小右边大吗,这个III是对是错?

快速排序一定要设置边界,到不是一定要左边小右边大,大家比较习惯吧。


#include <stdio.h>
#include <stdlib.h>
#define size 11
typedef char datatype;
typedef struct
{   int key;
    datatype others;
}SeqList;
 
int Partition(SeqList R[ ],int l,int h)
{   /*调用Parition(R,low,high)时对R[low..high]作划分*/
    /*并返回基准记录的位置*/
    int i,j;
    SeqList pivot;
    i=l;j=h;pivot=R[i];                      /*初始化,pivot为基准*/
    while(i<j)                               /*从区间两端交替向中间扫描,直至i=j为止*/
    { while(i<j&&R[j].key>=pivot.key)        /*pivot相当于在位置i上*/
      j--;                                   /*从右向左扫描,查找第1个关键字小于pivot.key的记录R[j]*/
    if(i<j)                                  /*表示找到的R[j]的关键字<pivot.key*/
        R[i++]=R[j];                         /*相当于交换R[i]和R[j],交换后i指针加1*/
    while(i<j&&R[i].key<=pivot.key)          /*pivot相当于在位置j上*/
        i++;                                 /*从左向右扫描,查找第1个关键字大于pivot.key的记录R[i]*/
    if(i<j)                                  /*表示找到了R[i],使R[i].key>pivot.key*/
        R[j--]=R[i];                         /*相当于交换R[i]和R[j],交换后j指针减1*/
    } /*endwhile*/
    R[i]=pivot;                              /*基准记录已被最后定位*/
    return i;
} /*partition*/
 
void QuickSort(SeqList R[ ],int low,int high)
{                                            /*对R[low.. high]快速排序*/
    int pivotpos;                            /*划分后的基准记录的位置*/
    if(low<high)                             /*仅当区间长度大于1时才须排序*/
    {   pivotpos=Partition(R,low,high);      /*对R[low..high]作划分*/
        QuickSort(R,low,pivotpos-1);         /*对左区间递归排序*/
        QuickSort(R,pivotpos+1,high);        /*对右区间递归排序*/
    }
} /*QuickSort */
 
void main()
{   SeqList R[size];
    int i;
    printf("输入数据:\n");
    for(i=1;i<size;i++)         scanf("%d",&R[i].key);
    printf("\n快速排序之前\n");
    for(i=1;i<size;i++)         printf("%d ",R[i].key);
    QuickSort(R,1,10);
    printf("\n快速排序之后\n");
    for(i=1;i<size;i++)         printf("%d ",R[i].key);
    printf("\n");
}

每经过一趟快排,轴点元素都必然就位。也就是说,一趟下来至少有1个元素在其最终位置,所以三是对的
因为最终排序是 11 18 23 68 69 73 93
经过一次后看开头和结尾有无最大或最小就可以判断了