内部排序算法比较实验报告（c语言版）.doc

题目：编制一个演示内部排序算法比较的程序班级： 姓名： 学号： 完成日期： 一、需求分析1本演示程序对以下6种常用的内部排序算法进行实测比较：起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。2待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。3演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值。4最后对结果作出简单分析。二、概要设计1可排序表的抽象数据类型定义：ADT OrderableList数据对象：D=ai|aiIntegerSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList(n)操作结果：构造一个长度为n，元素值依次为1，2，,n的有序表。RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False,将表置为逆序或正序，然后将表进行d(0d8)级随机打乱。d为0时表不打乱，d越大，打乱程度越高。RecallList()操作结果：恢复最后一次用RandomizeList随机打乱得到的可排序表。ListLength()操作结果：返回可排序表的长度。ListEmpty()操作结果：若可排序表为空表，则返回Ture，否则返回False。BubbleSort( &c, &s)操作结果：进行起泡排序，返回关键字比较次数c和移动次数s。InsertSort( &c, &s)操作结果：进行插入排序，返回关键字比较次数c和移动次数s。SelectSort ( &c, &s)操作结果：进行选择排序，返回关键字比较次数c和移动次数s。QuickSort(&c, &s)操作结果：进行快速排序，返回关键字比较次数c和移动次数s。ShellSort(long &c, long &s)操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。HeapSort (&c, &s)操作结果：进行堆排序，返回关键字比较次数c和移动次数s。ListTraverse(visit()操作结果：依次对L中的每个元素调用函数visit()。ADT OrderableList2本程序包含两个模块：1）主程序模块void main()初始化；do 接受命令； 处理命令； while(“命令”！=“退出”)； 2）可排序表单元模块实现可排序表的抽象数据类型；各模块之间的调用关系如下：主程序模块可排序表单元模块 三、详细设计1根据题目要求和可排序表的基本操作特点，可排序表采用整数顺序表存储结构。/可排序表的元素类型#define MAXSIZE 10000/用作示例的顺序表的最大长度typedef int BOOL;typedef struct int key;/关键字项 RedType; /记录类型typedef struct LinkList RedType rMAXSIZE; int Length; /顺序表长度 LinkList;int RandArrayMAXSIZE;/内部操作void RandomNum() int i; srand(20000); for (i = 0; i MAXSIZE; i+) RandArrayi = (int)rand();/构建随机序列void InitLinkList(LinkList *L) /建立表 int i; memset(L, 0, sizeof(LinkList); RandomNum(); for (i = 0; i ri.key = RandArrayi;/赋值 L-Length = i;bool LT(int i, int j, int *CmpNum) /比较i与j大小，返回0或1 (*CmpNum)+; if (i j) return TRUE; else return FALSE;void Display(LinkList *L) /存储表到SortRes.txt文件中 FILE *f; int i; if (f = fopen(SortRes.txt, w) = NULL) printf(cant open filen); exit(0); for (i = 0; i Length; i+) fprintf(f, %dn, L-ri.key); fclose(f);/部分操作的伪码算法/希尔排序void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum) int i, j; RedType Temp; for (i = dk; i Length; i+) if (LT(L-ri.key, L-ri - dk.key, CmpNum) memcpy(&Temp, &L-ri, sizeof(RedType); for (j = i - dk; j = 0 & LT(Temp.key, L-rj.key, CmpNum); j -= dk) (*ChgNum)+; memcpy(&L-rj + dk, &L-rj, sizeof(RedType); memcpy(&L-rj + dk, &Temp, sizeof(RedType); void ShellSort(LinkList *L, int dlta, int t, int *CmpNum, int *ChgNum) int k; for (k = 0; k rlow, sizeof(RedType); PivotKey = L-rlow.key; while (low high) while (low rhigh.key = PivotKey) high-; (*CmpNum)+; (*ChgNum)+; memcpy(&L-rlow, &L-rhigh, sizeof(RedType); while (low rlow.key rhigh, &L-rlow, sizeof(RedType); memcpy(&L-rlow, &Temp, sizeof(RedType); return low;void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum) int PivotLoc = 0; if (low Length - 1, CmpNum, ChgNum);/堆排序void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum) RedType Temp; int j = 0; s+; memcpy(&Temp, &L-rs - 1, sizeof(RedType); for (j = 2 * s; j = m; j *= 2) if (j rj - 1.key, L-rj.key, CmpNum) +j; if (!LT(Temp.key, L-rj - 1.key, CmpNum) break; (*ChgNum)+; memcpy(&L-rs - 1, &L-rj - 1, sizeof(RedType); s = j; memcpy(&L-rs - 1, &Temp, sizeof(RedType);void HeapSort(LinkList *L, int *CmpNum, int *ChgNum) int i = 0; RedType Temp; for (i = L-Length / 2-1; i = 0; i-) HeapAdjust(L, i, L-Length, CmpNum, ChgNum); for (i = L-Length; i 1; i-) memcpy(&Temp, &L-r0, sizeof(RedType); (*ChgNum)+; memcpy(&L-r0, &L-ri - 1, sizeof(RedType); memcpy(&L-ri - 1, &Temp, sizeof(RedType); HeapAdjust(L, 0, i - 1, CmpNum, ChgNum); /冒泡排序void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j; RedType temp; for (i = 1; i = MAXSIZE; i+) for (j = 1; j rj.key, L-rj + 1.key, CmpNum) (*ChgNum)+; memcpy(&temp, &L-rj, sizeof(RedType); memcpy(&L-rj, &L-rj + 1, sizeof(RedType); memcpy(&L-rj + 1, &temp, sizeof(RedType); /选择排序int SelectMinKey(LinkList *L, int k, int *CmpNum) int Min = k; for (; k Length; k+) if (!LT(L-rMin.key, L-rk.key, CmpNum) Min = k; return Min;void SelSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j; RedType temp; for (i = 0; i Length; i+) j = SelectMinKey(L, i, CmpNum); if (i != j) (*ChgNum)+; memcpy(&temp, &L-ri, sizeof(RedType); memcpy(&L-ri, &L-rj, sizeof(RedType); memcpy(&L-rj, &temp, sizeof(RedType); 3函数的调用关系图反映了演示程序的层次结构：mainsrandBubbleSort InsertSortSelectSort QuickSort ShellSort HeapSortInitLinkList RandomNum LT Display四、调试分析1对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序方法的比较测试，得到的测试数据具有较好的典型性和可比较性。通过设计和实现指定程序的随机乱序算法，对伪随机数序列的产生有了具体的认识和实践。2将排序算法中的关键字比较和交换分别由Less和Swap两个内部操作实现，较好的解决了排序算法的关键字比较次数和移动次数的统计问题。而赋值是直接统计的。3本实习作业采用循序渐进的策略，首先设计和实现可排序表的建立和随机操作，然后用插入排序验证各种内部辅助操作的正确性，进而逐个加入其他排序算法，最后完成对测试结果的显示。调试能力有了提高。五、用户手册1本程序的运行环境为DOS操作系统，执行文件为：内部排序算法比较.exe。2进入程序后即显示文本方式的用户界面：3输入1回车，即得直接插入排序的排序结果及其关键字比较次数和移动次数及时间输入2回车，即得希尔排序的排序结果及其关键字比较次数和移动次数及时间输入3回车，即得快速排序的排序结果及其关键字比较次数和移动次数及时间输入4回车，即得堆排序的排序结果及其关键字比较次数和移动次数及时间输入5回车，即得冒泡排序的排序结果及其关键字比较次数和移动次数及时间输入6回车，即得选择排序的排序结果及其关键字比较次数和移动次数及时间输入7回车，即得以上所有排序的排序结果及其关键字比较次数和移动次数及时间输入8回车，即退出该程序六、测试结果对结果的截屏如下：对各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，6种排序算法（快速排序采用“比中法”）的特点小结如下：测试插入排序希尔排序快速排序堆排序冒泡排序选择排序比较次数第三多越乱（逆）越多少乱否差异小少乱否差异小稍多乱否差异很小最多越乱（逆）越多越乱（逆）越多第二多与乱否无关移动次数第二多越乱（逆）越多约为快速排序的两倍第二少乱否差异较小稍多乱否差异很小最多越乱（逆）越多最少正和逆序少七、附录源程序文件名清单：052376_李明_内部排序算法比较.cpp /主程序#include #include #include #include #include #include #define MAXSIZE 5000#define TRUE 1#define FALSE 0typedef int BOOL;typedef struct int key; RedType;typedef struct LinkList RedType rMAXSIZE+1; int Length; LinkList;int RandArrayMAXSIZE+1;void RandomNum() int i; srand(2000); for (i = 1; i = MAXSIZE; i+) RandArrayi = (int)rand();void InitLinkList(LinkList *L) int i; memset(L, 0, sizeof(LinkList); RandomNum(); for (i = 1; i ri.key = RandArrayi; L-Length = i;bool LT(int i, int j, int *CmpNum) (*CmpNum)+; if (i j) return TRUE; else return FALSE;void Display(LinkList *L) FILE *f; int i; if (f = fopen(SortRes.txt, w) = NULL) printf(cant open filen); exit(0); for (i = 0; i Length; i+) fprintf(f, %dn, L-ri.key); fclose(f);/希尔排序void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum) int i, j; RedType Temp; for (i = dk; i Length; i+) if (LT(L-ri.key, L-ri - dk.key, CmpNum) memcpy(&Temp, &L-ri, sizeof(RedType); for (j = i - dk; j = 0 & LT(Temp.key, L-rj.key, CmpNum); j -= dk) (*ChgNum)+; memcpy(&L-rj + dk, &L-rj, sizeof(RedType); memcpy(&L-rj + dk, &Temp, sizeof(RedType); void ShellSort(LinkList *L, int dlta, int t, int *CmpNum, int *ChgNum) int k; for (k = 0; k rlow, sizeof(RedType); PivotKey = L-rlow.key; while (low high) while (low rhigh.key = PivotKey) high-; (*CmpNum)+; (*ChgNum)+; memcpy(&L-rlow, &L-rhigh, sizeof(RedType); while (low rlow.key rhigh, &L-rlow, sizeof(RedType); memcpy(&L-rlow, &Temp, sizeof(RedType); return low;void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum) int PivotLoc = 0; if (low Length - 1, CmpNum, ChgNum);/堆排序void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum) RedType Temp; int j = 0; s+; memcpy(&Temp, &L-rs - 1, sizeof(RedType); for (j = 2 * s; j = m; j *= 2) if (j rj - 1.key, L-rj.key, CmpNum) +j; if (!LT(Temp.key, L-rj - 1.key, CmpNum) break; (*ChgNum)+; memcpy(&L-rs - 1, &L-rj - 1, sizeof(RedType); s = j; memcpy(&L-rs - 1, &Temp, sizeof(RedType);void HeapSort(LinkList *L, int *CmpNum, int *ChgNum) int i = 0; RedType Temp; for (i = L-Length / 2-1; i = 0; i-) HeapAdjust(L, i, L-Length, CmpNum, ChgNum); for (i = L-Length; i 1; i-) memcpy(&Temp, &L-r0, sizeof(RedType); (*ChgNum)+; memcpy(&L-r0, &L-ri - 1, sizeof(RedType); memcpy(&L-ri - 1, &Temp, sizeof(RedType); HeapAdjust(L, 0, i - 1, CmpNum, ChgNum); /冒泡排序void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j; RedType temp; for (i = 1; i = MAXSIZE; i+) for (j = 1; j rj.key, L-rj + 1.key, CmpNum) (*ChgNum)+; memcpy(&temp, &L-rj, sizeof(RedType); memcpy(&L-rj, &L-rj + 1, sizeof(RedType); memcpy(&L-rj + 1, &temp, sizeof(RedType); /选择排序int SelectMinKey(LinkList *L, int k, int *CmpNum) int Min = k; for (; k Length; k+) if (!LT(L-rMin.key, L-rk.key, CmpNum) Min = k; return Min;void SelSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j; RedType temp; for (i = 0; i Length; i+) j = SelectMinKey(L, i, CmpNum); if (i != j) (*ChgNum)+; memcpy(&temp, &L-ri, sizeof(RedType); memcpy(&L-ri, &L-rj, sizeof(RedType); memcpy(&L-rj, &temp, sizeof(RedType); void SelectSort() printf(1. 插入排序n); printf(2. 希尔排序n); printf(3. 快速排序n); printf(4. 堆排序n); printf(5. 冒泡排序n); printf(6. 选择排序n); printf(7. 以上所有排序方式n); printf(8. 退出程序nn); printf(Please Select the Operate:);void AllAbove(LinkList *L, int *CmpNum, int *ChgNum) int TempTime, i,j; int SpendTime; int dlta3 = 7, 3, 1 ; int Indata1 = 1 ; for (i = 1; i ri.key = RandArrayi;/随机数列复位 printf(n插入排序:n); TempTime = (int)GetTickCount(); ShellSort(L, Indata, 1, &CmpNum0, &ChgNum0); SpendTime = (int)GetTickCount() - TempTime; printf(nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNum0, ChgNum0,SpendTime); for (i = 1; i ri.key = RandArrayi;/随机数列复位 printf(n希尔排序:n); TempTime = (int)GetTickCount(); ShellSort(L, dlta, 3, &CmpNum1, &ChgNum1); SpendTime = (int)GetTickCount() - TempTime; printf(nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNum1, ChgNum1,SpendTime); for (i = 1; i ri.key = RandArrayi;/随机数列复位 printf(n快速排序:n); TempTime = (int)GetTickCount(); QuickSort(L, &CmpNum2, &ChgNum2); SpendTime = (int)GetTickCount() - TempTime; printf(nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNum2, ChgNum2,SpendTime); for (i = 1; i ri.key = RandArrayi;/随机数列复位 printf(n堆排序:n); TempTime = (int)GetTickCount(); HeapSort(L, &CmpNum3, &ChgNum3); SpendTime = (int)GetTickCount() - TempTime; printf(nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNum3, ChgNum3,SpendTime); for (i = 1; i ri.key = RandArrayi;/随机数列复位 printf(n冒泡排序:n); TempTime = (int)GetTickCount(); BubbleSort(L, &CmpNum4, &ChgNum4); SpendTime = (int)GetTickCount() - TempTime; printf(nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNum4, ChgNum4,SpendTime); for (i = 1; i ri.key = RandArrayi;/随机数列复位 printf(n选择排序:n); TempTime = (int)GetTickCount(); SelSort(L, &CmpNum5, &ChgNum5); SpendTime = (int)GetTickCount() - TempTime; printf(nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNum5, ChgNum5,SpendTime);void main() int i,j; int select = 0; int dlta3 = 7, 3, 1; int Indata1 = 1; int CmpNum8, ChgNum8; int SpendTime = 0; int TempTime; LinkList L; InitLinkList(&L); memset(CmpNum, 0, sizeof(CmpNum); memset(ChgNum, 0, sizeof(ChgNum); do SelectSort(); for (i = 0; i MAXSIZE; i+) L.ri.key = RandArrayi;/随机数列复位 scanf(%d, &select); switch (select) case 1: printf(n插入排序:n);TempTime = (int)GetTickCount(); ShellSort(&L, Indata, 1, &CmpNumselect, &ChgNumselect); SpendTime = (int)GetTickCount() - TempTime;for(i=1;i=MAXSIZE;i+)printf(%5d ,L.ri.key);if(+j%10=0)printf(n); printf(nnCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNumselect,ChgNumselect, SpendTime); break; case 2: printf(n希尔排序:n); TempTime = (int)GetTickCount(); ShellSort(&L, dlta, 3, &CmpNumselect, &ChgNumselect); SpendTime = (int)GetTickCount() - TempTime; for(i=1;i=MAXSIZE;i+)printf(%5d ,L.ri.key);if(+j%10=0)printf(n);printf(nnCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn, CmpNumselect,ChgNumselect, SpendTime); break; case 3: printf(n快速排序:n); TempTime = (int)GetTickCount(); QuickSort(&L, &CmpNumselect, &ChgNumselect);