AUSTOj10 - 暮无雪代码博客

#include <stdio.h>

#define MAXSIZE 20 //记录最大个数
typedef struct{
int data[MAXSIZE+1]; //data[0]可闲置或作监视哨
int length; //顺序表长度
}SqList;

//创建顺序表
void CreateSqList(SqList &L, int n){
int i;
L.length = n;
for(i=1; i<=L.length; i++){
scanf("%d",&L.data[i]);
getchar();
}
}

//输出顺序表
void PrintSqList(SqList &L){
int i;
for(i=1; i<=L.length; i++)
printf("%d\n",L.data[i]);
}

//直接插入排序,Acc=1表示升序,Acc=-1表示降序
void InsertSort(SqList &L,int Acc){

int i,j;
if(Acc==1){
for(i=2;i<=L.length ;i++){
L.data [0]=L.data [i];
for(j=i-1;L.data [j]>L.data [0];j--){
L.data [j+1]=L.data [j];
}
L.data [j+1]=L.data [0];
}
}
else{
for(i=2;i<=L.length ;i++){
L.data [0]=L.data [i];
for(j=i-1;L.data [j]<L.data [0];j--){
L.data [j+1]=L.data [j];
}
L.data [j+1]=L.data [0];
}
}

//--------补充代码--Start------

//--------补充代码--End------
}

//折半插入排序
void BInsertSort(SqList &L){
int mid;
for(int i=2;i<=L.length ;i++){
L.data [0]=L.data [i];
int low=1,high=i-1;
while(low<=high){
mid=(low+high)/2;
if(L.data [0]<L.data [mid]) high=mid-1;
else low=mid+1;
}
for(int j=i-1;j>=high+1;j--) L.data [j+1]=L.data [j];
L.data [high+1]=L.data [0];
}
//--------补充代码--Start------

//--------补充代码--End------
}

//主函数
int main(){
int n,Acc;
SqList List,TempList;
int select;

while(scanf("%d",&select)!=EOF){
getchar();
if(select==0)
return 0;
else if(select==1){
scanf("%d",&n);
CreateSqList(List, n);
}
if(select==2){
TempList=List;
scanf("%d",&Acc);
getchar();
InsertSort(TempList,Acc);
PrintSqList(TempList);
}
else if(select==3){
TempList=List;
BInsertSort(TempList);
PrintSqList(TempList);
}
}
return 0;
}

#include <stdio.h>

#define MAXSIZE 20 //记录最大个数

//学生结构体
typedef struct{
char name[10];
int age;
int no;
}Student;
typedef struct{
Student data[MAXSIZE+1];//data[0]可闲置或作监视哨
int length; //顺序表长度
}SqList;

//创建顺序表
void CreateSqList(SqList &L, int n){
L.length = n;
for(int i=1; i<=L.length; i++){
scanf("%d %d %s",&L.data[i].no,&L.data[i].age,L.data[i].name);
getchar();
}
}

//输出顺序表
void PrintSqList(SqList &L){
for(int i=1; i<=L.length; i++)
printf("%d %d %s\n",L.data[i].no,L.data[i].age,L.data[i].name);
}

//按照学号起泡排序，Acc=1表示升序,Acc=-1表示降序
void BubbleSort(SqList &L, int Acc){
int i,j;
Student t;
if(Acc==1){
for(i=1;i<L.length ;i++){
for(j=1;j<=L.length -i;j++){
if(L.data [j].no>L.data [j+1].no){
t=L.data [j];
L.data [j]=L.data [j+1];
L.data [j+1]=t;
}
}
}
}
else{
for(i=1;i<=L.length ;i++){
for(j=1;j<=L.length -i;j++){
if(L.data [j].no<L.data [j+1].no){
t=L.data [j];
L.data [j]=L.data [j+1];
L.data [j+1]=t;
}
}
}
}

//--------补充代码--Start------

//--------补充代码--End------
}

//=============按照学号快速排序start=============
//一趟快速排序过程,Acc=1表示升序,Acc=-1表示降序
int Partition(SqList &L, int low, int high, int Acc){
Student t;
if(Acc==1){
t=L.data [low];
while(low<high){
while(L.data [high].no>=t.no&&low<high) high--;
L.data [low]=L.data [high];
while(L.data [low].no<t.no&&low<high) low++;
L.data [high]=L.data [low];
}
L.data [low]=t;
return low;
}
else{
t=L.data [low];
while(low<high){
while(L.data [high].no<=t.no &&low<high) high--;
L.data [low]=L.data [high];
while(L.data [low].no>t.no&&low<high) low++;
L.data [high]=L.data [low];
}
L.data [low]=t;
return low;
}
//--------补充代码--Start------

//--------补充代码--End------
}
void QSort(SqList &L, int low, int high, int Acc) {
int pivotloc;
if(low<high){ //当L.data[low..high]为空或只有一个记录时无需排序
pivotloc=Partition(L, low, high, Acc); //对 L.data[low..high]] 进行一次划分,并返回枢轴位置
QSort(L, low, pivotloc-1, Acc); //递归处理左区间
QSort(L, pivotloc+1, high, Acc); //递归处理右区间
}
}
void QuickSort(SqList &L,int Acc){
QSort(L, 1, L.length, Acc);
}
//=============按照学号快速排序end=============

//主函数
int main(){
int n,Acc,SortType;
SqList List,TempList;
int select;

while(scanf("%d",&select)!=EOF){
if(select==0)
return 0;
else if(select==1){
scanf("%d",&n);
CreateSqList(List, n);
}
if(select==4){
TempList=List;
scanf("%d",&Acc);
BubbleSort(TempList,Acc);
PrintSqList(TempList);
}
if(select==5){
TempList=List;
scanf("%d",&Acc);
QuickSort(TempList,Acc);
PrintSqList(TempList);
}
}
return 0;
}