下面的测试数据，我设置了数量为5.
可以修改const int N = 5;
将5变为是您想要排序的个数。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status; //用作函数值类型，表示函数结果状态
typedef int KeyType; //关键字类型为整数类型
typedef struct{
KeyType key; //关键字项
//... //其他数据项
}RecordType, RcdType; //记录类型，RcdType为RecordType的简写
//在对排序算法的讨论中，若无特别说明，均是对储存记录的顺序表排序。顺序表的0号单元闲置或用作哨兵
typedef struct{
RcdType *rcd; //存储空间基址
int length; //当前长度
int size; //存储容量
int increment; //空间不够增加空间大小
}RcdSqList; //记录的顺序表
/*初始化顺序表*/
Status InitList_Sq(RcdSqList &L, int size, int inc){
L.rcd = (RcdType *)malloc((size+1)*sizeof(RcdType)); //分配存储空间,0号单元不用，作为哨兵
if(NULL==L.rcd)
return OVERFLOW;
L.length = 1;
L.size = size + 1;
L.increment = inc;
}
/*在顺序表L表尾添加元素e*/
Status Append_Sq(RcdSqList &L, RcdType e){
//删除顺序表L的表尾元素，并用参数e返回其值
if(L.size == L.length)//顺序表已满
return ERROR;
L.rcd[L.length] = e;
++L.length; //表长加1
return OK;
}
int Partition(RcdType rcd[], int low, int high){
//对子序列rcd[low..high]进行一次划分，并返回枢轴记录应该所处的位置
//使得在枢轴之前的关键字均不大于它的关键字，枢轴之后的关键字均不小于它的关键字
rcd[0] = rcd[low]; //将枢轴移至数组的空闲分量
while(low < high){ //low和high从待排序列的两端交替地向中间移动
while(low < high && rcd[0].key <= rcd[high].key)
--high;
rcd[low] = rcd[high]; //将比枢轴关键字小的关键字移到低端
while(low < high && rcd[0].key >= rcd[low].key)
++low;
rcd[high] = rcd[low]; //将比枢轴关键字大的关键字移到高端
}
rcd[low] = rcd[0];//枢轴关键字移到正确位置
return low; //返回枢轴的位置
}
void QSort(RcdType rcd[], int s, int t){
//对记录序列rcd[s..t]进行快速排序
int pivotloc;
if(s < t){ //长度大于1
pivotloc = Partition(rcd, s, t); //对rcd[s..t]一趟快排并返回枢轴位置
QSort(rcd, s, pivotloc-1); //对低子序列递归进行排序
QSort(rcd, pivotloc+1, t); //对高子序列递归进行排序
}
}
void QuickSort(RcdSqList &L){//对记录的顺序表L进行快速排序
QSort(L.rcd, 1, L.length+1);
}
const int N = 5; //排序数字的个数
int main(){
int a[N];
int i =0;
RcdSqList L;
RcdType e;
InitList_Sq(L, N, 5);
printf("Please input data:");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
printf("Sorted:");
for(i=0;i<N;i++){
e.key = a[i];
Append_Sq(L, e);
}
QuickSort(L);
printf("Sorted:");
for(i=1;i<=N;i++){
printf("%d",L.rcd[i].key);
}
printf("\n");
return 0;
}
