#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define LIST_INIT_SIZE 20
#define OVERFLOW -2
int bj1,yd1,n;
clock_t start_t,end_t;
/****************************************定义结构体***********************************/
typedef struct
{
int *elem;
int length;
int listsize;
}SqList;
/***************************************定义初始化函数*********************************/
void Initiate(SqList &L)
{
//构造一个空的线性表。
L.elem=(int * ) malloc(LIST_INIT_SIZE * sizeof(int));
if(!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize=LIST_INIT_SIZE;
// return OK;
}//InitLi
/***************************************定义复制函数************************************/
void copy(SqList &P,SqList &Q,int n)
{
P.length=n;
Q.length=n;
for(int i=1;i<=n;i++)
{
Q.elem[i]=P.elem[i];
}
}
/*****************定义随机生成一个长度为n的数组的函数********************/
void addlist(SqList &L,int n)
{
for(int i=1;i<n+1;i++)
{
L.elem[i]=rand();
}
L.length=n;
}
/*************************1选择排序*****************************/
void SelectSort(SqList &L)//选择
{
start_t=clock();
int i,j,k,bj=0,yd=0;
for(i=1;i<L.length;i++)
{
k=i;
for(j=i+1;j<=L.length;j++)
{
bj++;
if(L.elem[j]<L.elem[k])k=j;
}
if(i!=k)
{
L.elem[0]=L.elem[i];
L.elem[i]=L.elem[k];
L.elem[k]=L.elem[0];
yd+=3;
}
}
end_t=clock();
printf("比较次数为 %d\n移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
/***********************2起泡排序****************************/
void qipao(SqList &L)//起泡
{
start_t=clock();
int i=1,j,bj=0,yd=0;
while(i<L.length)
{
for(j=1;j<L.length;j++)
{
bj++;
if(L.elem[j]>L.elem[j+1])
{
L.elem[0]=L.elem[j];
L.elem[j]=L.elem[j+1];
L.elem[j+1]=L.elem[0];
yd+=3;
}
}
i++;
}
end_t=clock();
printf("比较次数为 %d\n移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
/**********************3直接插入排序****************************/
void InsertSort(SqList &L)//直接插入
{
start_t=clock();
int i,j,yd=0,bj=0;
for(i=2;i<=L.length;i++)
{
if(L.elem[i]<L.elem[i-1])
{
L.elem[0]=L.elem[i];
yd++;
j=i-1;
bj++;
while(L.elem[0]<L.elem[j])
{
L.elem[j+1]=L.elem[j];
j--;
yd++;
bj++;
}
L.elem[j+1]=L.elem[0];
yd++;
}
}
end_t=clock();
printf("比较次数为 %d\n移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
/***************************4希尔******************************/
void shell(int *a,int n)
{
int yd=0,bj=0;
start_t=clock();
int i,j,k,x;
k=n/2; /*间距值*/
while(k>=1) {
for(i=k;i<n;i++) {
x=a[i];
yd+=1;
j=i-k;
while(j>=0&&x<a[j]) {
bj++;
a[j+k]=a[j];
yd+=1;
j-=k;
}
a[j+k]=x;
yd+=1;
}
k/=2; /*缩小间距值*/
}
end_t=clock();
printf("比较次数为 %d\n移动次数为 %d\n",bj,yd);
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
/********************************快速排序和归并排序应用到的两个函数*************************/
void BeforeSort()
{
yd1=0,bj1=0;
}
void display(int m,int n)
{
printf("比较次数为 %d\n移动次数为 %d\n",m,n);
}
/*********************5快速排序算法************************/
int Partition(SqList &L,int low,int high)//快速排序
{
int pivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low];
while (low<high)
{
yd1++;
while(low<high&&L.elem[high]>=pivotkey)
--high;
L.elem[low]=L.elem[high];
bj1++;
yd1++;
while (low<high&&L.elem[low]<=pivotkey)
++low;
L.elem[high]=L.elem[low];
bj1++;
yd1++;
}
L.elem[low]=L.elem[0];
yd1++;
return low;
}
/***********************快速排序的递归过程***********************/
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
start_t=clock();
BeforeSort();
QSort(L,1,L.length);
display(yd1,bj1);
end_t=clock();
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
/************************6归并排序********************************/
//将两个有序的序列sr[left, mid], sr[mid+1, right]排好序复制到di中去
void Merge(int *sr, int *di, int left, int mid, int right)
{
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right)
{bj1++;
if (sr[i] < sr[j])
{
di[k++] = sr[i++];
yd1++;
}
else
{di[k++] = sr[j++];
yd1++;}
}
if (i > mid)
while (j <= right)
{
bj1++;
di[k++] = sr[j++];
yd1++;
}
else if (j > right)
while (i <= mid)
{
bj1++;
di[k++] = sr[i++];
yd1++;
}
}
//合并大小为s的相邻数组（数组的总长为s)
void MergePass(int *sr, int *di, int s, int n)
{
int i = 0;
while (i <= n - 2 * s)
{
Merge(sr, di, i, i+s-1, i+2*s-1);
i += 2*s;
}
//剩下的元素个数大于s小于2*s时，对这段用Merge
//剩下的元素个数小于s时，直接从sr复制到di中去
if (i + s < n)
Merge(sr, di, i, i+s-1, n - 1);
else
for (int j = i; j <= n-1; ++j)
{ di[j] = sr[j];
yd1++;}
}
void MergeSort(int *a, int n)
{
start_t=clock();
BeforeSort();
int *b = (int*)malloc((n) * sizeof(int));
int s = 1;
while (s < n)
{
MergePass(a, b, s, n);
s += s;
MergePass(b, a, s, n);
s += s;
}
free(b);
display(yd1,bj1);
end_t=clock();
printf("排序用时为 %f\n",float(end_t-start_t)/CLK_TCK);
}
void show(SqList &L)
{
for(int i=1;i<=L.length;i++)
{
printf("%d ",L.elem[i]);
}
printf("\n");
}
void show1(SqList &L)
{
for(int i=0;i<L.length;i++)
{
printf("%d ",L.elem[i]);
}
printf("\n");
}
void main()
{
int flag=1;
int t,m;
printf("请输入你所选择的方式：0为随机生成，1为人工输入:");
scanf("%d",&t);
SqList L;
SqList L1;
SqList L2;
SqList L3;
SqList L4;
SqList L7;
SqList L5;
SqList L6;
Initiate(L);
Initiate(L1);
Initiate(L2);
Initiate(L3);
Initiate(L4);
Initiate(L7);
Initiate(L5);
Initiate(L6);
if(t==0)
{
printf("请输入你要输入的个数:");
scanf("%d",&n);
addlist(L,n);
show(L);
}
if(t==1)
{
printf("\n输入表长:");
scanf("%d",&n);
L.length=n;
printf("\n输入元素:");
for(int i=1;i<n+1;i++)
{
scanf("%d",&L.elem[i]);
}
}
copy(L,L1,n);
copy(L,L2,n);
copy(L,L3,n);
copy(L,L4,n);
copy(L,L5,n);
copy(L,L6,n);
copy(L,L7,n);
for(int i=1;i<=n;i++)
{
L6.elem[i-1]=L.elem[i];
L7.elem[i-1]=L.elem[i];
}
printf("请输入要使用的排序方法\n1直接排序，2选择排序，3起泡排序，4希尔排序\n5快速排序，6归并排序");
while(flag)
{
scanf("%d",&m);
switch(m)
{
case 1:
printf("**********直插排序**********: \n");
InsertSort(L);
show(L);
printf("\n");
break;
case 2:
printf("**********选择排序**********: \n");
SelectSort(L1);
show(L1);
printf("\n");
break;
case 3:
printf("**********起泡排序**********: \n");
qipao(L2);
show(L2);
printf("\n");
break;
case 4:
printf("**********希尔排序**********: \n");
shell(L7.elem,n);
show1(L7);
break;
case 5:
printf("**********快速排序*********: \n");
QuickSort(L4);
show(L4);
printf("\n");
break;
case 6:
printf("**********归并排序**********: \n");
MergeSort(L6.elem,n);
show1(L6);
break;
default:
printf("误操作!\n");
}
}
}
数据结构课程设计——排序方法
需积分: 9 185 浏览量
2010-06-13
14:05:46
上传
评论
收藏 721KB RAR 举报
数据结构课程设计——排序方法.rar （20个子文件） 
数据结构课程设计——排序方法 任务书 
3.doc 60KB 1.doc 61KB 2.doc 61KB 论文 3.doc 107KB 1.doc 108KB 2.doc 109KB
数据结构演示稿9.ppt 511KB 源程序 
jjj.opt 48KB jjj.ncb 49KB jjj.dsw 514B Debug jjj.pch 224KB vc60.pdb 52KB vc60.idb 41KB jjj.pdb 481KB
jjj.exe 204KB jjj.obj 23KB jjj.ilk 413KB jjj.plg 682B jjj.cpp 7KB jjj.dsp 3KB资源评论
