快速排序的短发.doc

编程工具：C-Free 5.0
【实验二】：快速排序
（一）快速排序.cpp
#include<stdio.h>
#include<stdlib.h>
#define SIZE 100
void quick_sort(int data[],int x,int y);
int pation(int data[],int x,int y);
int main()
{
int i,n,data[SIZE];
printf("请输入要排列的数目（<=100）：");
scanf("%d",&n);
printf("请输入要排列的数列：\n");
for(i=0;i<n;++i)
scanf("%d",&data[i]);
quick_sort(data,0,n-1);
printf("排列后的数列为：\n");
for(i=0;i<n;++i)
printf( "%d ",data[i]);
printf("\n");
return 0;
}
void quick_sort(int data[],int x,int y)
{
if(x>=y) return;
int q=pation(data,x,y);
quick_sort(data,x,q-1);
quick_sort(data,q+1,y);
}
int pation(int data[],int x,int y)
{
int n=data[x],i=x+1,j=y,temp;
while(1)
{
while(data[i]<n) ++i;
while(data[j]>n) --j;
if(i>=j) break;
temp=data[i]; data[i]=data[j]; data[j]=temp;
}
data[x]=data[j];
data[j]=n;
return j;
}

（二）插入排序.cpp
#include<stdio.h>
#include<conio.h>
#define X 100
#define Y 100
int main()
{
int a[X],r[Y];
int *p;
int i,j,n;
printf("请输入要排列的数目（<=100）：");
scanf("%d",&n);
printf("请输入要排列的数列：\n");
for(i=0;i<n;i++)
{
p=&a[i];
scanf("%d",p);
r[i+1]=a[i];
}
r[0]=1;
for(i=2;i<=n;i++)
{
r[0]=r[i];
j=i-1;
while(r[j]>r[0])
{
r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
printf("排列后的顺序是：\n");
for(i=1;i<=n;i++)
{
p=&r[i];
printf("%d ",*p);
}
printf("\n");
return 0;
}