数据结构（内部排序算法）实验报告.doc

广东工业大学实验报告_学院_专业_班 成绩评定_实验题目：数据结构（内部排序算法） 第一章 实验需求分析与方案排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且还直接影响着计算机的工作效率 。目前，最常见的排序算法有冒泡排序法、选择排序法、插入排序法、快速排序法等算法。这些排序算法各有自己的优缺点，不同的排序算法适应不同的情况。就算法的整体性能而言,目前很难提出一种适应所有的排序场合的最好的排序算法，每种算法都有自己不同的适用场合。使用插入排序法，交换排序法，选择排序法设计与实现算法程序完成线性表的排序号。通过测试分析说明各排序算法的优缺点。通过实验结果分析，总结插入排序法，交换排序法，选择排序法三类算法的特点。第二章 实验过程与结果a) 直接插入法算法l 算法实现程序：主程序：/直接插入排序算法#include /待排记录数据类型#define MAXSIZE 30 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型typedef structKeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1; /r0闲置或用作哨兵单元int length; /顺序表长度SqList;int c;/比较次数comparetimeint m;/移动次数movetime/Output内部排序算法输出函数void Output(SqList &L)for(int i=1;i=L.length;i+)printf( %d ,L.ri.key);printf(n);/InsertionSort直接插入排序算法void InsertionSort(SqList &L)/对顺序表L作直接插入排序。int c=0;/比较次数comparetimeint m=0;/移动次数movetimefor (int i=2;i=L.length;+i)if(L.ri.key L.ri-1.key) /，需将L.ri插入有序表L.r0 = L.ri; /复制哨兵m+;L.ri = L.ri-1; m+;for (int j=i-2; L.r0.key L.rj.key; -j,c+ )L.rj+1.key = L.rj.key; /记录后移m+;L.rj+1 = L.r0; /插入到正确位置m+;c+;m+;Output(L);printf(t移动次数m:%dn,m);printf(t比较次数c:%dn,c);/InsertionSortvoid main() printf(tt InserionSort直接插入排序算法n);printf(n); printf(tt 待排序顺序表L: 59 48 75 107 86 23 37 59 55 20n); printf(n);SqList L;L.r1.key=59; L.r2.key=48;L.r3.key=75; L.r4.key=107;L.r5.key=86; L.r6.key=23;L.r7.key=37; L.r8.key=59;L.r9.key=55; L.r10.key=20;L.length=10;printf(n);printf(对顺序表L进行排序:);printf(n); InsertionSort(L);printf(n);printf(t输出InsertionSort结果:n); Output(L);printf(n);l 运行结果l 排序过程比较和移动次数。插入排序算法具体操作为：将待排序数组分为两部分，第一部分包括这个数组中除最后一个元素外的所有元素，第二部分为最后一个元素，直到第一部分排好序后，再将第二部分插入到已排好序的第一部分中，如此递归，最终为第一部分为数组第一个元素，第二部分为数组第二个元素，二者排序完毕后继续将后面的元素插入，如此直至数组最后一个元素插入完毕，整个数组排序完毕。 排序过程中，数据的移动次数为37，比较次数为31。b) 折半插入法算法l 算法实现程序；主程序：/折半插入排序算法#include /待排记录数据类型#define MAXSIZE 30 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型typedef structKeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1; /r0闲置或用作哨兵单元int length; /顺序表长度SqList;int c;/比较次数comparetimeint m;/移动次数movetime/Output内部排序算法输出函数void Output(SqList &L)for(int i=1;i=L.length;i+)printf( %d ,L.ri.key);printf(n);/BinaryInsertionSort折半插入排序算法void BinaryInsertionSort (SqList &L) /对顺序表L作折半插入排序。 int c=0;/比较次数comparetimeint m=0;/移动次数movetime for (int i=2;i=L.length; +i,c+)L.r0 = L.ri; /将L.ri暂存到L.r0int low = 1;int high = i-1;while (low = high) /在rloe.high中折半查找有序插入的位置int mid = (low+high)/2; /折半if (L.r0.key= high+1; -j,c+) L.rj+1 = L.rj;/记录后移m+;L.rhigh+1 = L.r0; /插入m+;Output(L);/forprintf(t移动次数m:%dn,m);printf(t比较次数c:%dn,c);/BinaryInsertionSortvoid main() printf(tt BinaryInsertionSort折半插入排序算法n); printf(n); printf(tt 待排序顺序表L: 59 48 75 107 86 23 37 59 55 20n); printf(n);SqList L;L.r1.key=59; L.r2.key=48;L.r3.key=75; L.r4.key=107;L.r5.key=86; L.r6.key=23;L.r7.key=37; L.r8.key=59;L.r9.key=55; L.r10.key=20;L.length=10;printf(n);printf(对顺序表L进行排序:);printf(n); BinaryInsertionSort(L);printf(n);printf(t输出BinaryInsertionSort结果:n); Output(L);printf(n);l 运行结果l 排序过程比较和移动次数。折半插入排序算法的具体操作为：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为alow,末元素设置为ahigh，则轮比较时将待插入元素与am,其中m=(low+high)/2相比较,如果比参考元素小，则选择alow到am-1为新的插入区域(即high=m-1)，否则选择am+1到ahigh为新的插入区域（即low=m+1），如此直至low=high不成立，即将此位置之后所有元素后移一位，并将新元素插入ahigh+1。排序过程中，数据的移动次数为40，比较次数为38。c) 希尔排序算法l 算法实现程序主程序：/希尔排序算法#include /待排记录数据类型#define MAXSIZE 30 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型typedef structKeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1; /r0闲置或用作哨兵单元int length; /顺序表长度SqList;int c;/比较次数comparetimeint m;/移动次数movetime/Output内部排序算法输出函数void Output(SqList &L)for(int i=1;i=L.length;i+)printf( %d ,L.ri.key);printf(n);/Shells Sort希尔排序算法void ShellInsert(SqList &L, int dk)/对顺序表L作一趟希尔插入排序。for ( int i = dk+1;i = L.length;+i)if (L.ri.key 0 & (L.r0.key L.rj.key); j-=dk)L.rj+dk = L.rj; /记录后移，查找插入位置m+;c+;L.rj+dk = L.r0;/插入m+;c+;Output(L);c+;/ShellInsertvoid ShellsSort (SqList &L,int dlta,int t)/按增量序列dlta0.t-1对顺序表L作希尔排序。c=0;/比较次数comparetimem=0;/移动次数movetimefor (int k=0;k0&L0Lj;j=j-h) 这个循环中单独进行希尔比较，排列成有序，一轮过去后，步长就会改变，就进行下一轮的排序了。排序过程中，数据移动次数为38，比较次数为29。d) 起泡排序算法l 算法实现程序主程序：/冒泡排序算法#include /待排记录数据类型#define MAXSIZE 30 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型typedef structKeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1; /r0闲置或用作哨兵单元int length; /顺序表长度SqList;int c;/比较次数comparetimeint m;/移动次数movetime/Output内部排序算法输出函数void Output(SqList &L)for(int i=1;i=L.length;i+)printf( %d ,L.ri.key);printf(n);/BubbleSort冒泡排序算法void BubbleSort(SqList &L,int n) / 对顺序表L作冒泡排序int i,j,fini = 0;for (i = 1; i n & !fini; i+) fini = 1;for (j = 1; j L.rj+1.key) L.r0= L.rj;m+;L.rj = L.rj+1;m+;L.rj+1 = L.r0;m+;Output(L);fini = 0;printf(t移动次数m:%dn,m);printf(t比较次数c:%dn,c);/Bubblesortvoid main() printf(tt Bubblesort冒泡排序算法n); printf(n); printf(tt 待排序顺序表L: 59 48 75 107 86 23 37 59 55 20n); printf(n);SqList L;L.r1.key=59; L.r2.key=48;L.r3.key=75; L.r4.key=107;L.r5.key=86; L.r6.key=23;L.r7.key=37; L.r8.key=59;L.r9.key=55; L.r10.key=20;L.length=10;printf(n);printf(对顺序表L进行排序:);printf(n); BubbleSort(L,L.length);printf(n);printf(t输出BubbleSort结果:n);Output(L);printf(n);l 运行结果：l 排序过程比较和移动次数冒泡排序算法的操作为：首先将第一个元素和第二个元素进行比较，如果为逆序则将两个记录交换，然后比较第二个记录和第三个记录。以此类推，直到第n-1个记录和第n个记录进行过比较为止。上述过程称为第一趟冒泡排序，起结果使得最大的记录被交换到最后一个位置上。然后进行第二趟冒泡，对前n-1个记录进行同样的操作，则第二大的记录被交换到倒数第二的位置上。这样，第i趟冒泡排序就会将第n-i+1的记录交换到第n-i+1的位置上，则整个冒泡排序过程需要经过k趟排序，1=k=i，判断结束的条件为“在一趟排序过程中没有经行记录的交换操作”。同样可以数列底部作为起点开始，这样，小的元素就会像水中的气泡一样往上浮，每次最小的元素被交换到上部，所以称之为冒泡排序。排序过程中，数据移动次数为87，比较次数为45。e) 快速排序算法l 算法实现程序：主程序：/快速排序算法#include /待排记录数据类型#define MAXSIZE 30 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型typedef structKeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1; /r0闲置或用作哨兵单元int length; /顺序表长度SqList;int c;/比较次数comparetimeint m;/移动次数movetime/Output内部排序算法输出函数void Output(SqList &L)for(int i=1;i=L.length;i+)printf( %d ,L.ri.key);printf(n);/QuickSort快速排序算法int Partition(SqList &L, int low, int high) L.r0 = L.rlow;while (lowhigh) while (low high & L.r0.key = L.rhigh.key) -high;c+;L.rlow.key = L.rhigh.key;m+;Output(L);while (low high & L.rlow.key = L.r0.key) +low;c+;L.rhigh.key = L.rlow.key;m+;c+;L.rlow.key = L.r0.key;m+;return low;Output(L); / Partitionvoid QuickSort(SqList &L, int low, int high) / 对顺序表L中的子序列L.rlow.high进行快速排序int pivotloc;if (low high) pivotloc = Partition(L, low, high);QuickSort(L, low, pivotloc-1);QuickSort(L, pivotloc+1, high); Output(L); / QSortvoid QuickSort(SqList &L) / 对顺序表L进行快速排序c=0;/比较次数comparetimem=0;/移动次数movetimeQuickSort(L, 1, L.length);printf(t移动次数m:%dn,m);printf(t比较次数c:%dn,c); / QuickSortvoid main() printf(tt QuickSort快速排序算法n); printf(n); printf(tt 待排序顺序表L: 59 48 75 107 86 23 37 59 55 20n); printf(n);SqList L;L.r1.key=59; L.r2.key=48;L.r3.key=75; L.r4.key=107;L.r5.key=86; L.r6.key=23;L.r7.key=37; L.r8.key=59;L.r9.key=55; L.r10.key=20;L.length=10;printf(n);printf(对顺序表L进行排序:);printf(n); QuickSort(L);printf(n);printf(t输出QuickSort结果:n);Output(L);printf(n);l 运行结果：l 排序过程比较和移动次数快速排序操作为：具体分为三个步骤。假设待排序的序列为Lm.n。分解：序列Lm . n被划分成两个可能为空的子序列Lm . pivot-1和Lpivot+1 . n，使Lm . pivot-1的每个元素均小于或等于Lpivot，同时Lpivot+1. n的每个元素均大于Lpivot。其中Lpivot称为这一趟分割中的主元（也称为枢轴、支点）。解决：通过递归调用快速排序，对子序列Lm . pivot-1和Lpivot+1 . r排序。合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列Lm . n已排好序。排序过程中，数据的移动次数为28，比较次数为28。f) 简单选择排序算法l 算法实现程序：主程序：/简单选择排序算法#include /待排记录数据类型#define MAXSIZE 30 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型typedef structKeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1; /r0闲置或用作哨兵单元int length; /顺序表长度SqList;int c;/比较次数comparetimeint m;/移动次数movetime/Output内部排序算法输出函数void Output(SqList &L)for(int i=1;i=L.length;i+)printf( %d ,L.ri.key);printf(n);/SimpleSelectionSort简单选择排序算法void SimpleSelcetionSort(SqList &L) / 对顺序表L作简单选择排序c=0;/比较次数comparetimem=0;/移动次数movetime int i,j,k; for (i =1; i L.length; i+) k = i;for (j = i+1; j = L.length; j+,c+)if (L.rj.key L.rk.key) k=j;m+;Output(L);if(k!=j)L.r0.key = L.rk.key; L.rk.key = L.ri.key; L.ri.key =L.r0.key;c+;m+;Output(L); printf(t移动次数m:%dn,m);printf(t比较次数c:%dn,c); / SelectSortvoid main() printf(tt SimpleSelcetionSort简单选择排序算法n); printf(n); printf(tt 待排序顺序表L: 59 48 75 107 86 23 37 59 55 20n); printf(n);SqList L;L.r1.key=59; L.r2.key=48;L.r3.key=75; L.r4.key=107;L.r5.key=86; L.r6.key=23;L.r7.key=37; L.r8.key=59;L.r9.key=55; L.r10.key=20;L.length=10;printf(n);printf(对顺序表L进行排序:);printf(n);SimpleSelcetionSort(L);printf(n);printf(t输出SimpleSelcetionSort结果:n);Output(L);printf(n);l 运行结果：l 排序过程比较和移动次数简单选择排序算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。排序过程中，顺序表中的数据的移动次数为18次，比较次数为54。第三章 实验分析1、插入排序（Insertion Sort），其基本原理是将一个新数据插入到一组已经排好序的数据中，从而得到一个新的数据组，这组新数据组比原数据组元素增加1，而数据之间仍为有序数列。插入排序算法适用于少量数据排序，它的时间复杂度为（m2），是稳定的排序方法。2、折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为（n2）)，与直接插入排序算法相同。3、希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。Shell排序的时间性能优于直接插入排序，据统计分析其时间复杂度为O(n1.3) 。希尔排序是一种不稳定的算法。4、冒泡排序是就地排