11-4.c

这些是数据结构结构的经典实现算法

#include  < stdio.h>
#define n 100 //假设的文件长度,即待排序的记录数目
typedef int KeyType; //假设的关键字类型
typedef struct{ //记录类型
   	 	KeyType key; //关键字项
    	//其它数据项,类型InfoType依赖于具体应用而定义
}RecType;
typedef struct {
	RecType r[n+1];
	int length;
}SeqList;
//SeqList为顺序表类型,表中第0个单元一般用作哨兵
int  Partition(SeqList L, int low, int high)
{
	 KeyType pivotkey=L.r[low].key;                 //用子表的第一个记录作为枢轴
	 L.r[0]=L.r[low];   
     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]=L.r[0];                         //枢轴记录到位
         return low;                                 //返回枢轴记录位置
}   //完成一趟快速排序
void Qsort(SeqList  L, int low, int high)
{
     int pivotloc;  
	 if(low<high){                                            //长度大于1
          pivotloc=Partition(L,low,high);            //将L.r[low……high]一分为二
          Qsort(L,low,pivotloc-1);                     //对低子表递归排序
          Qsort(L,pivotloc+1,high);                     //对高子表递归排序
	}
}
void QuickSort(SeqList L)
{
     Qsort(L,1,L.length);
}    //对顺序表L做快速排序
void Initial(SeqList R)
{
	//初始化
}
void main()
{
	SeqList R;
	Initial(R);
	QuickSort(R);
}