数据结构之排序总结(C语言)

//数据结构实验课程之手工执行一下排序算法， //写出每一趟排序结束时的关键码状态 #include <stdio.h>

#include <stdlib.h>

#define maxsize 20

//结构体的定义

typedef struct

{

int L[maxsize+1];

int length;

}list;

//以下是八种排序方法的子函数的说明 void display(list m);//输出函数

void menu(list m);//菜单函数

void straight(list m);//直接插入排序

void shell(list m);//希尔排序（增量d[1]=5） void bubble(list m);//起泡排序

void quick(list m);//快速排序

void selection(list m);//简单选择排序

void heap(list m);//堆排序

void merg(list m);//归并排序

void radix(list m);//基数排序

void shellinsert(list *m,int num);

void qsort(list *m,int low,int high);

int partition(list *m,int low,int high);

int selectmin(list *m,int num);

void heapadjust(list *m,int s,int n);

void msort(int sr[],int tr1[],int s,int t);

void mer(int sr[],int tr[], int i,int m,int t);

//主函数

void main()

{

list a;

int i;

char ch;

printf("Firstly, let's create the list.\n");

printf("please input the length of the list:\n"); scanf("%d",&a.length);

printf("please input the keyword of the list:\n"); for(i=1;i<=a.length;i++)

{

scanf("%d",&a.L[i]);

}

display(a);

getchar();

printf("\nLet's go to the menu\n");

getchar();

system("cls");

{

menu(a);

printf("\nDo you want to continue?(Y/N)\n");

fflush(stdin);

scanf("%c",&ch);

getchar();

system("cls");

}while(ch=='y'||ch=='Y');

}

void display(list m)

{

int i;

printf("\nThe list is following:\n");

for(i=1;i<=m.length;i++)

{

printf("--%d--",m.L[i]);

}

//菜单界面

void menu(list m)

{

int number;

scanf("%d",&number);

switch (number)

{

case 1:

straight(m);break;

case 2:

shell(m);break;

case 3:

bubble(m);break;

case 4:

quick(m);break;

case 5:

selection(m);break;

case 6:

heap(m);break;

case 7:

merg(m);break;

case 8:

radix(m);break;

default:

printf("Your choice is wrong!\n"); }

}

void straight(list m)

{

int i,j,num=1;

display(m);

for(i=2;i<=m.length;i++)

{

if(m.L[i]<m.L[i-1])

{

m.L[0]=m.L[i];

m.L[i]=m.L[i-1];

for(j=i-2;m.L[0]<m.L[j];j--) {

m.L[j+1]=m.L[j];

}

m.L[j+1]=m.L[0];

}

getchar();

printf("\n^o^o^o^o^ ( %d ) ^o^o^o^o^ display(m);

} ",num++);

}

void shell(list m)

{

int dlta[3]={5,3,1};

int i,num=1;

display(m);

for(i=0;i<3;i++)

{

shellinsert(&m,dlta[i]);

getchar();

printf("\n^o^o^o^o^ ( %d ) ^o^o^o^o^ ",num++); display(m);

}

void shellinsert(list *m,int num)

{

int i,j;

for(i=num+1;i<=m->length;i++)

{

if(m->L[i]<m->L[i-num])

{

m->L[0]=m->L[i];

for(j=i-num;j>0&&((m->L[0])<(m->L[j]));j-=num) {

m->L[j+num]=m->L[j];

}

m->L[j+num]=m->L[0];

}

void bubble(list m)

{

int i,j,t,num=1;

display(m);

for(i=1;i<m.length;i++)

{

for(j=1;j<=m.length-i;j++)

{

if(m.L[j]>m.L[j+1])

{

t=m.L[j];

m.L[j]=m.L[j+1];

m.L[j+1]=t;

}

getchar();

printf("\n^o^o^o^o^ ( %d ) ^o^o^o^o^ ",num++);

display(m);

}

void quick(list m)

{

qsort(&m,1,m.length);

display(m);

}

void qsort(list *m,int low,int high)//递归算法

{

int pivotloc;

if(low<high)

{

pivotloc=partition(m,low,high);

qsort(m,low,pivotloc-1);

qsort(m,pivotloc+1,high);

}

int partition(list *m,int low,int high) //将比枢轴大的数移到枢轴右侧，小的移到左侧 {

int num;

num=m->L[low];

m->L[0]=m->L[low];

while(low<high)

{

while(low<high&&m->L[high]>=num)

{

--high;

}

m->L[low]=m->L[high];

while(low<high&&m->L[low]<=num)

{

++low;

}

m->L[high]=m->L[low]; }

m->L[low]=m->L[0]; return low;

}

void selection(list m)

{

int i,j,num,a=1;

display(m);

for(i=1;i<m.length;i++) {

j=selectmin(&m,i); if(j!=i)

{

num=m.L[i]; m.L[i]=m.L[j]; m.L[j]=num; }

getchar();

printf("\n^o^o^o^o^ ( %d ) display(m);

}

int selectmin(list *m,int num) {

int i,j,min;

j=num;

min=m->L[num];

for(i=num;i<=m->length;i++) {

if(min>m->L[i]) {

min=m->L[i]; j=i;

}

return j;

}

void heap(list m)

{ ^o^o^o^o^ ",a++);

int i,j,t,num=1;

j=m.length;

display(m);

for(i=m.length/2;i>0;i--)//建成大顶堆

{

heapadjust(&m,i,m.length);

}

display(m);

for(i=m.length;i>0;i--)

{

t=m.L[1];

m.L[1]=m.L[i];

m.L[i]=t;

heapadjust(&m,1,--j);

getchar();

printf("\n^o^o^o^o^ ( %d ) ^o^o^o^o^ ",num++);

display(m);

//因为该无序表已经建成了大顶堆，故将L[1[与L[i]交换后，2到i-1依旧符合堆的定义

}//所以只需要一次筛选就行了。

}

void heapadjust(list *m,int s,int n)

{

int i,num;

for(i=2*s;i<=n;i*=2)

{

if(i<n&&(m->L[i]<m->L[i+1])) //注意：i<n，不能等于，否则在最后一步会出错，及1-2筛选时。完全二叉树有一个

{ //性质就是，如果节点数为奇数则没有孩子会成对出现，如果为偶数，则会单个出现。

i++;

}

if(m->L[i]<=m->L[s]) break;

num=m->L[s];

m->L[s]=m->L[i];

m->L[i]=num;

s=i; //s=s*2;例如对2-n筛选时，当结点2与其左右孩子比较完了之后，

}

//还需要结点4与其左右孩子比较

}

void merg(list m)

{ list n;

n=m;

display(m);

msort(m.L,n.L,1,m.length);

printf("\nThe result is:\n");

display(n); //数组名作为形参传递给子函数时，是使用的地址传递，list n是经过重新排序的表。

}

void msort(int sr[],int tr1[],int s,int t) //运用了一个递归函数，将顺序表逐渐分割成子表 {

int num;

int tr2[maxsize]={0};

if(s==t)

{

tr1[s]=sr[s];

}

else

{

num=(s+t)/2;

msort(sr,tr2,s,num);

msort(sr,tr2,num+1,t);

mer(tr2,tr1,s,num,t);

}

void mer(int sr[],int tr[], int i,int m,int t) //对子表进行排序的函数，新生成的表的数组为tr[]

{

int j,k;

for(j=m+1,k=i;i<=m&&j<=t;k++)

{

if(sr[i]<sr[j])

{

tr[k]=sr[i];

i++;

}

else

{

tr[k]=sr[j];

j++;

}

while(i<=m)

{

tr[k++]=sr[i++];

}

while(j<=t)

{

tr[k++]=sr[j++];

}

void radix(list m)

{

int i,j,t;

display(m);

for(i=1;i<m.length;i++)

{

for(j=1;j<m.length;j++)

{

if((m.L[j]/100)>(m.L[j+1]/100))

{

t=m.L[j];

m.L[j]=m.L[j+1];

m.L[j+1]=t;

}

getchar();

printf("\n^o^o^o^o^ ( 1 ) ^o^o^o^o^ "); display(m);

for(i=1;i<m.length;i++)

{

for(j=1;j<m.length;j++)

{

if((m.L[j]/100)==(m.L[j+1]/100))

{

if(((m.L[j]/10)%10)>((m.L[j+1]/10)%10)) {

t=m.L[j];

m.L[j]=m.L[j+1];

m.L[j+1]=t;

}

} printf("\n^o^o^o^o^ ( 2 ) ^o^o^o^o^ "); display(m); for(i=1;i<m.length;i++) { for(j=1;j<m.length;j++) { if(((m.L[j]/100)==(m.L[j+1]/100))&&(((m.L[j]/10)%10)>((m.L[j+1]/10)%10))) { if((m.L[j]-((m.L[j]/100)*100))%10>(m.L[j]-((m.L[j+1]/100)*100))%10) { t=m.L[j]; m.L[j]=m.L[j+1]; m.L[j+1]=t; } } } } printf("\n^o^o^o^o^ ( 3 ) ^o^o^o^o^ "); display(m);

相关推荐

数据结构之排序总结(C语言)

专栏推荐