各种排序算法实现(经典)

各种排序算法的实现（经典）

一 实验目的

使学生掌握常用内部排序的基本概念和基本方法 使学生掌握常用内部排序方法的性能评价； 使学生掌握排序方法在实际问题中的应用；

二 实验环境

所需硬件环境为微机；

所需软件环境为Microsoft Visual C++ 6.0；

三 实验内容

此部分仅用写出要求的实验代码,并加上必要的注释 #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OVERFLOW -2 #define OK 1 #define FAILURE 0 #define TRUE 1 #define FALSE 0 #define ERROR -1

typedef int ElemType; typedef int Status;

1 数 据 结 构 实 验 报 告

void PrintElem(ElemType *e){ printf(\"%5d\#include #include \"ElemType.c\"

int p[6];//记录比较次数 int q[6];//记录移动次数

void InsertSort(int *L,int n)// 直接插入排序 { int i,j;

for(i=2;i<=n;i++) {if(L[i]for(j=i-2;L[0]void ShellInsert(int *L,int n,int dk)// 希尔排序 { int i,j;

for(i=dk+1;i<=n;i++) {if(L[i]for(j=i-dk;j>0&&L[0]2 数 据 结 构 实 验 报 告

{L[j+dk]=L[j];p[1]++;q[1]++;} L[j+dk]=L[0];q[1]+=2;} p[1]++; }}

void ShellSort(int *L,int n) // 希尔排序 { int dalt[6]={13,11,7,5,3,1}; int i;

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

ShellInsert(L,n,dalt[i]);}

void buddlesort(int *L,int n)// 冒泡排序 { int i,j,k,m;

for(i=n,k=1;i>1&&k;i--) { k=0;

for(j=1;jL[j+1])

{ m=L[j];L[j]=L[j+1]; L[j+1]=m;k=1;q[2]+=3;} p[2]++; }}}

int Partition(int *L,int low,int high) { int k; L[0]=L[low]; k=L[low]; while(low{ while(low=k) {high--;p[3]++;}

3 数 据 结 构 实 验 报 告

L[low]=L[high];

while(lowvoid QSort(int *L,int low,int high) { int k; if(low{ k=Partition(L,low,high); QSort(L,low,k-1); QSort(L,k+1,high); } }

void QuikSort(int *L,int n)// 快速排序 { QSort(L,1,n); }

void HeapAdjust(int *L,int s,int m)// 堆排序 { int j,t; t=L[s];

for(j=2*s;j<=m;j*=2) {if(j=L[j]) break; p[4]+=2;q[4]++; L[s]=L[j];s=j;}

4 数 据 结 构 实 验 报 告

L[s]=t;q[4]+=2;}

void HeapSort(int *L,int n) // 堆排序 { int i,t;

for(i=n/2;i>0;i--) HeapAdjust(L,i,n); for(i=n;i>1;i--)

{t=L[1];L[1]=L[i];L[i]=t;q[4]+=3; HeapAdjust(L,1,i-1); }}

void Merge(int *SR,int *TR,int i,int m,int n) { int j,k,t;

for(j=m+1,k=i;i<=m&&j<=n;++k) { if(SR[i]{TR[k]=SR[j]; j++;} q[5]++;p[5]++;} if(i<=m)

for(t=i;t<=m;t++) { TR[k]=SR[t];q[5]++; k++;} if(j<=n)

for(t=j;t<=n;t++) { TR[k]=SR[t];q[5]++;

5 数 据 结 构 实 验 报 告

k++;}}

void MSort(int *SR,int *TR1,int s,int t) { int *TR2=(int *)malloc(sizeof(int)*t); int m; if(s==t)

{TR1[s]=SR[s];q[5]++;} else

{ m=(s+t)/2;

MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t);}}

void MergeSort(int *L,int n)// .归并排序 {MSort(L,L,1,n); }

int main(){ //主函数1

int k,i,a[10]={5,8,1,11,23,41,16,44,14,9}; int L[101];

printf(\"原数字排列为：\"); for(i=0;i<10;i++) L[i+1]=a[i]; for(i=0;i<10;i++) printf(\"%d,\

printf(\"\\n-------------主菜单-------------\\n\"); printf(\"1.直接插入排序\\n\"); printf(\"2.希尔排序\\n\");

6 数 据 结 构 实 验 报 告

printf(\"3.冒泡排序\\n\"); printf(\"4.快速排序\\n\"); printf(\"5.堆排序\\n\"); printf(\"6.归并排序\\n\"); printf(\"7.退出\\n\");

printf(\"--------------------------------\\n\"); while(1)

{ printf(\"请选择选项：\"); scanf(\"%d\ switch(k)

{ case 1:printf(\"使用直接排序方法得到的结果是：\\n\"); InsertSort(L,10);for(i=0;i<10;i++) printf(\"\\n\");break;

case 2:for(i=0;i<10;i++) L[i+1]=a[i];printf(\"使用希尔排序方法得到的结果是：\\n\");

ShellSort(L,10);for(i=0;i<10;i++) printf(\"\\n\");break;

case 3:for(i=0;i<10;i++) L[i+1]=a[i];printf(\"使用冒泡排序方法得到的结果是：\\n\");

buddlesort(L,10);for(i=0;i<10;i++) printf(\"\\n\");break;

case 4:for(i=0;i<10;i++) L[i+1]=a[i];printf(\"使用快速排序方法得到的结果是：\\n\");

QuikSort(L,10);for(i=0;i<10;i++) printf(\"\\n\");break;

case 5:for(i=0;i<10;i++) L[i+1]=a[i];printf(\"使用堆排序方法得到的结果是：\\n\");

7 printf(\"%d,\

printf(\"%d,\

printf(\"%d,\

printf(\"%d,\

数 据 结 构 实 验 报 告

HeapSort(L,10);for(i=0;i<10;i++) printf(\"%d,\

case 6:for(i=0;i<10;i++) L[i+1]=a[i];printf(\"使用归并排序方法得到的结果是：\\n\");

MergeSort(L,10);for(i=0;i<10;i++) printf(\"%d,\

case 7:printf(\"已退出！\");exit(0);break; default:printf(\"\\nInput error!\"); }} return 0; }

#include//主函数2 #include

8 数 据 结 构 实 验 报 告

#include \"Sort.c\" int main(){ int L[101],i,k; for(i=0;i<100;i++)

L[i+1]=100 + rand() % (1000 - 100) ;

printf(\"\\n-------------主菜单-------------\\n\"); printf(\"1.直接插入排序\\n\"); printf(\"2.希尔排序\\n\"); printf(\"3.冒泡排序\\n\"); printf(\"4.快速排序\\n\"); printf(\"5.堆排序\\n\"); printf(\"6.归并排序\\n\"); printf(\"7.退出\\n\");

printf(\"--------------------------------\\n\"); while(1)

{ printf(\"请选择选项：\"); scanf(\"%d\ switch(k)

{case 1:InsertSort(L,100);printf(\"1.直接插入排序的比较次数和移动次数分别为：%d,%d\\n\

case 2:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;ShellSort(L,100);

printf(\"2.希尔排序的比较次数和移动次数分别为：%d,%d\\n\

case 3:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;buddlesort(L,100);

9 数 据 结 构 实 验 报 告

printf(\"3.冒泡排序的比较次数和移动次数分别为：%d,%d\\n\

case 4:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;QuikSort(L,100);

printf(\"4.快速排序的比较次数和移动次数分别为：%d,%d\\n\

case 5:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;HeapSort(L,100);

printf(\"5.堆排序的比较次数和移动次数分别为：%d,%d\\n\

case 6:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;MergeSort(L,100);

printf(\"6.归并排序的比较次数和移动次数分别为：%d,%d\\n\

case 7:printf(\"已退出！\");exit(0);break; default:printf(\"\\nInput error!\"); }} return 0; }

10 数 据 结 构 实 验 报 告

四 实验分析及问题思考

1. 分析和总结各种内部排序方法的优缺点；

直接插入排序

优点:移动元素次数少，只需要一个辅助空间 缺点：效率不高

冒泡排序

优点：比较简单，空间复杂度较低，是稳定的 缺点：时间复杂度太高，效率不好

简单选择排序

优点：所需移动记录的次数比较少，最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录 缺点：简单选择排序是不稳定排序

快速排序

优点：极快，数据移动少 缺点：不稳定

希尔排序

11 数 据 结 构 实 验 报 告

优点：快，数据移动少

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取

归并排序

优点：归并排序是稳定的排序方法

缺点：需要一个与原始序列同样大小的辅助序列

堆排序

优点：在最坏情况下时间复杂度也为O(nlogn)，并且它仅需一个记录大小供交换用的辅助存储空间

缺点：记录数较少时不提倡使用

基数排序

优点：基数排序法的效率高于其它的比较性排序法，稳定的排序

12 数 据 结 构 实 验 报 告

快速排序算法设计(10003809386j)

实验自评检查表 实验内容 自评结果（在对应格内打√） 不熟练 一般 比较熟练 熟练 简单排序方法先进排序方法直接插入排序 起泡排序 √ √ √ √ √ √ 简单选择排序 快速排序 希尔排序 归并排序 实验的心得体会

通过这次实验，我更加清楚地了解了各个算法的实现过程，学会应用随机数表，而且自己体会到了各个算法的时间复杂度。还了解了哨兵的实际作用，以后要在程序的精巧方面多多努力，还应该多看一些精巧的算法。

13