数据结构课程设计(快速排序).docx

数据结构课程设计 数据结构课程设计报告 快速排序详析专业物联网工程学生姓名方振华班级152学号1510706205指导教师刘 骞完成日期2016年12月22日目 录一、简介1二、算法说明1三、测试结果7四、分析与探讨9五、数据异常测试案例15六、小结17七、参考文献18八、源程序清单18快速排序详析1、 简介排序是计算机程序设计中常用的数据处理操作。经过一学期数据结构的学习，我们学到很多种排序方法，如插入排序、交换排序、选择排序、归并排序、技术排序等。经过分析与对比，我们总结出一种快速排序的优化版本，并对其设计思想和具体实现进行详解。2、 算法说明1、各种排序算法方法性能比较图1：各种排序算法方法性能比较（1）就时间性能而言，快速排序，堆排序和归并排序都有较好的时间性能。相对而言，快速排序速度最快，不过快速排序在最坏情况下，时间性能达到了O（n2），不如堆排序和归并排序快。（2）就空间性能而言，直接插入排序，冒泡排序，简单选择排序，堆排序要求的辅助空间比较小。其中直接插入排序，冒泡排序，简单选择排序比较简单，容易实现，但时间性能较差。快速排序是一种有效的排序算法。虽然算法在最坏的情况下运行时O(n2)，但由于平均运行时间为O（nlogn），并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法，其基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键词比另一部分记录的关键词小，则可分别对这两部分记录进行排序，以达到整个序列有序。2、步骤快速排序基本算法Quicksort(S)由以下4个步骤组成：(1).如果S中的元素数目为0或一，则返回。(2).选择S中的任意一个元素v,v叫做支点(Pivot)。(3).将S-v(剩下的元素在S中)分成两个分开的部分。所有小于v的元素和所有大于v的元素。(4).依次返回Quicksort(L)，v和Quicksort的结果基本的快速排序算法可以应用递归实现，关键的细节包括支点的选取和如何分组。该算法允许把任何元素作为支点。支点把数组分为两组，图2展示了算法的基本过程。图2：算法基本过程3、分析最好情况：快速排序的最好情况是支点把集合分成两个同等大小的子集并且在递归的每个阶段都这样划分。然后就有了两个一般大小的递归调用和线性的分组开销。在这种情况下运行的时间复杂度是O（nlog2n）。最坏情况：假设在每一步的递归调用中支点都恰好是最小的元素。这样小元素的集合L就是空的而大元素集合R拥有除了支点以外的所有元素。设T（N）是对N各元素惊醒快速排序所需的运行时间按并假设对0或1各元素排序的时间刚好是1个时间单位。那么对由于N1当每次都运气很差地最小的元素作为支点得到的原型时间满足T（N）=T(N-1)+N.即对N各项进行排序的时间等于递归排序大元素子集中的N-1各项所需要的时间加上进行分组的N个单位的开销。最终得出T（N）=T(1)+2+3+N=N(N+1)/2=O(N2) 支点选择：错误方式：比较常见的不明智的选择就是把第一个元素作为支点。但如果输入是已经预先排过序的，或者是倒序的，该支点给出的分组就很糟，因为它是一个末端的元素；而且这种情况会在迭代中继续出现，会以O(N2)的时间复杂度而告终，所以选择第一个元素作为支点不是好的策略。 中位选择：把中间元素即待排序序列中间位置的元素作为支点是合理的选择。当输入已经排过序时这种选择在每次递归调用中都会给出理想的支点。 中值划分：在上诉选择中使用中间值作为支点可以消除非随机输入时出现的退化情况。但这是一种消极的选择，就是说仅仅是试图避免一个坏的支点而并没有去尝试选择一个更好的支点。中值划分是一种选择比平均情况更好的支点的尝试。在中值划分中，一种比较简单而有效的策略是选择待排序列的第一个、中间一个以及最好一个记录这3个值的中值作为支点。同样道理，也可以从待排序列中等距离地选取5各值，并将这5各值的中值作为支点。 4、 程序设计本实验的目的是设计并实现一种快速排序Quicksort的优化版本，并且比较在下列组合情况下算法的性能表现 (1) cutoff值从020。Cutoff值的作用是只有当数组的长度小于等于这个值时才使用另一种简单排序方法对其排序否则使用Quicksort算法排序。 (2) 选定支点的方法分别是“第一个元素”“三个元素的中值”“五个元素的中值”。 程序主要由6部分组成，分别是：（1）程序入口main函数；（2）Quicksort,快速排序算法的实现部分；（3）MedianOf3,选择三个值的中值作为中点；（4）MedianOf5,选择五个值的中点作为支点；（5）Swap,简单地交换两个元素的值；（6）Insertion,在数组长度小于cutoff值时使用插入排序来代替快速排序。3、 测试结果改完相关错误后运行代码，运行结果（如图4所示），在相关文件中新建文本文件，文件命名为”input.txt“。在文本文件中，打入输入数据，得出下列截图（图）。图三：建立input并输入回到程序，程序运行。图四：程序运行输入数据并确定。图五：程序运行完毕查看output文件。4、 分析与探讨重点函数分析：Main函数：int main()int i, group = 0, numbOFelements, elements, Amount;int Array10000;int cutoff = 0;FILE *InputPTR, *OutputPTR; /* input和output文件指针 */InputPTR = fopen(input.txt, r+);OutputPTR = fopen(output.txt, w+);if (InputPTR = NULL) /* 检查input文件是否存在 */W+;InitGameBoard();putin();if (median != 1) & (median != 3) & (median != 5)N+;putin();start = GetTickCount();Amount = fscanf(InputPTR, %d, &numbOFelements); /* 读取每次迭代的元素的个数 */while (Amount != EOF) /* 当读到的不是文件的末尾 */start1 = GetTickCount();group+;fprintf(OutputPTR, Case number: %dnNumber of elements: %dn,group, numbOFelements); /*输出的格式 */for (i = 0;inumbOFelements;i+) fscanf(InputPTR, %d, &Arrayi); /*将输入读入到数组中 */fgetc(InputPTR);fgetc(InputPTR);QuickSort(Array, 0, numbOFelements - 1, cutoff, median); /*给数组排序 */for (i = 0;inumbOFelements;i+)fprintf(OutputPTR, %d , Arrayi); /*打印排序后的数组 */stop1 = GetTickCount();tim1 = stop1 - start1;fprintf(OutputPTR, n 本组数据消耗时间为:%d ms , tim1);tim = tim1+tim;Amount = fscanf(InputPTR, %d, &numbOFelements);fprintf(OutputPTR, nn);fclose(InputPTR);fclose(OutputPTR);stop = GetTickCount();InitGameBoard();return 0;Main函数主要内容：打开input.txt和output.txt文件；读入数的个数n；从文件中顺序读入n个数，并放到数组中；应用Quicksort对该数组排序；将排序后的数输出到文件output.txt中；读入下一组数的个数，继续上述过程；关闭文件。QuickSort函数：void QuickSort(int Array, int min, int max, int cutoff, int median)/*median=1时使用第一个值作为支点median=3时使用三个值的中值作为支点median=5时使用五个值的中值作为支点*/int low, high, Pivot;if (max - min) = 0)return; /* 如果数组中没有元素 */if (min + cutoff = median) /* 检查cutoff值是否合适 */if (median = 1) Swap(&Arraymin, &Arraymax);Pivot = Arraymax;else if (median = 3) /* 调用函数MedianOf3 */Pivot = MedianOf3(Array, min, max);else if (median = 5) /*调用函数MedianOf5 */Pivot = MedianOf5(Array, min, max);low = min; high = max;for (; ; )while (Arraylow Pivot) /* 跳过比支点大的值 */if (low high) /* 交换两个值 */Swap(&Arraylow, &Arrayhigh);else /* 如果指针重叠了，则跳出循环 */break;Swap(&Arraylow, &Arraymax);QuickSort(Array, min, low - 1, cutoff, median); /* 分成两部分递归调用快速排序 */QuickSort(Array, low + 1, max, cutoff, median);else InsertionSort(Array, min, max); /* 对剩余的数组进行插入排序 */Quicksort函数 参数：待排数组，待排段的起点位置，待排段的终点位置，cutoff值，支点选择方法 If数组时空的 Exit If待排数段的元素个数大于等于cutoff值，且元素个数大于等于支点选择方法所要求的元素个数根据支点选择方法选择一个元素作为支点 设置low为起点值、high为终点值 While low=high While low位置的值小于支点值 Low+ ；While high位置的值大于支点值 High；If lowhigh 交换low、high两个元素 将low位置的元素与支点元素交换 Quicksort递归调用左半段 Quicksort递归调用右半段 Else 应用直接插入排序法对数组元素排序 MedianOf3：选择三个值的中值作为中点；MedianOf5：选择五个值的中点作为支点；Swap：简单地交换两个元素的值；Insertion：在数组长度小于cutoff值时使用插入排序来代替快速排序。5、 数据异常测试案例1. 没有配置input文件解决方法：在特定文件夹创建input文件并输入数值保存。2. 输入数值有误解决方法；回到input文件输入正确的数值。6、 小结通过这次课程设计，进一步加深了我对各种排序算法的认识，特别是快速排序算法。每种排序算法都有其不足，我们在编写程序时要用其长处。不足之处我们可以使用其他算法进行替换。从而在时间上获得更好的效益。虽然这次课程设计已经有现成的代码但是我从代码中学到了一些东西，比如对文件的读写操作。以前我很少会将程序的输出结果以文本的格式存放起来。我觉得我在数据结构这门课上还需要花很多的时间，以前只学习理论知识，现在应用到实践真的花费了很大的力气，还需继续努力。我同时体会到了团队合作的重要性，从最初的查阅资料到最后的程序的成功运行，与其说是学习，不如说它是合作精神和毅力的考验。经过这次课程设计，我们不仅学到了很多知识和技能，更重要的是团队的合作。最后，在这次的实训过程中，我们深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我们不会灰心，我们会在以后的日子里努力弥补我们的不足。7、 参考文献1何钦铭 陈根才 数据结构课程设计 浙江大学出版社 2007年8月2 谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月3 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月8、 源程序清单#define _CRT_SECURE_NO_DEPRECATE#undef UNICODE#undef _UNICODE#include#include#include#include#include#include#include#include#define SIZE 10000 /* 数组最大的容量 */#define NameMaxLength 12 /设定用户名的最大字符数为：NameMaxLength-2#define PsdMaxLength 10 /设定密码的最大字符数#define boxbkclr 0xfedcbd /绘制消息框和登录框的主题填充颜色#define drawFieldbkclr 0xFFFFFF /窗口区域的背景填充颜色/*-与算法相关的函数和定义-*/int MedianOf3(int a, int low, int high);int MedianOf5(int a, int low, int high);void Swap(int *a, int *b);void QuickSort(int a, int left, int right, int cutoff, int median);void InsertionSort(int a, int low, int high);int median;int cutoff;/*-与界面相关的函数和定义-*/void DrawMsgBox();void InitGameBoard();void putin();void InputName(); /输入账号void InputPsd(); /输入密码int xb00 = 0, xb01 = 0, xb02 = 0, xb03 = 0, xb04 = 0, xb05 = 0;/控件（按钮或输入框）的位置坐标int yb00 = 0, yb01 = 0, yb02 = 0, yb03 = 0, yb04 = 0, yb05 = 0;/控件（按钮或输入框）的位置坐标int T = 0;int W = 0;int N = 0;int start, start1, stop, stop1;int tim=0,tim1;char IptNameNameMaxLength = , , , , , , ,0 ;char IptPsdPsdMaxLength = , , , , , , ,0 ;int ResponseMouse(int xb0, int yb0, int xb1, int yb1, int xb2, int yb2, int xb3, int yb3, int xb4, int yb4, int xb5, int yb5)int place = -1;MOUSEMSG m;/定义鼠标消息while (true)m = GetMouseMsg();/获取一条鼠标消息if (m.uMsg = WM_LBUTTONDOWN)if (xb0 = -1)/在绘图区域任意点击place = 0;break;/单击第一个对象if (m.xxb0) & (m.xyb0) & (m.yxb2) & (m.xyb2) & (m.yyb3)place = 2;break;/单击第三个对象return place;/返回鼠标点击的对象/*-主函数-*/int main()int i, group = 0, numbOFelements, elements, Amount;int Array10000;int cutoff = 0;FILE *InputPTR, *OutputPTR; /* input和output文件指针 */InputPTR = fopen(input.txt, r+);OutputPTR = fopen(output.txt, w+);if (InputPTR = NULL) /* 检查input文件是否存在 */W+;InitGameBoard();putin();if (median != 1) & (median != 3) & (median != 5)N+;putin();start = GetTickCount();Amount = fscanf(InputPTR, %d, &numbOFelements); /* 读取每次迭代的元素的个数 */while (Amount != EOF) /* 当读到的不是文件的末尾 */start1 = GetTickCount();group+;fprintf(OutputPTR, Case number: %dnNumber of elements: %dn,group, numbOFelements); /*输出的格式 */for (i = 0;inumbOFelements;i+) fscanf(InputPTR, %d, &Arrayi); /*将输入读入到数组中 */fgetc(InputPTR);fgetc(InputPTR);QuickSort(Array, 0, numbOFelements - 1, cutoff, median); /*给数组排序 */for (i = 0;iamid) Swap(&alow, &amid);if (alowahigh) Swap(&alow, &ahigh);if (amidahigh) Swap(&amid, &ahigh);Swap(&amid, &ahigh); /* 交换排序后的中间元素和最后元素的值 */return ahigh;/*支点（pivot）选择五个值的中值的算法*/int MedianOf5(int a, int low, int high)int i, temp, j, largest;int Step;Step = (high - low) / 4; /* 设定步长为四分之一，这样便能选出五个元素 */for (j = 0; j4; +j)largest = high - j*Step; /*每次迭代选择不同的值作为最大值 */for (i = j + 1; ialargest)largest = high - i*Step; /* 设定新的最大值 */Swap(&ahigh - j*Step, &alargest); /* 将每次找到的最大值放在每次对应的位置 */Swap(&ahigh - Step - Step, &ahigh); /* 将选定的支点放到最后面 */Swap(&ahigh - 3 * Step, &alow);return ahigh;/*交换两个元素*/void Swap(int *a, int *b)int temp = *a;*a = *b;*b = temp;/*插入排序*/void InsertionSort(int a, int min, int max)int j, i, temp;for (i = min;i min & aj - 1temp;j-)aj = aj - 1;aj = temp;/*快速排序*/void QuickSort(int Array, int min, int max, int cutoff, int median)/*median=1时使用第一个值作为支点median=3时使用三个值的中值作为支点median=5时使用五个值的中值作为支点*/int low, high, Pivot;if (max - min) = 0)return; /* 如果数组中没有元素 */if (min + cutoff = median) /* 检查cutoff值是否合适 */if (median = 1) Swap(&Arraymin, &Arraymax);Pivot = Arraymax;else if (median = 3) /* 调用函数MedianOf3 */Pivot = MedianOf3(Array, min, max);else if (median = 5) /*调用函数MedianOf5 */Pivot = MedianOf5(Array, min, max);low = min; high = max;for (; ; )while (Arraylow Pivot) /* 跳过比支点大的值 */if (low 0)settextstyle(25, 0, _T(楷体);setcolor(RED);outtextxy(50, 50, 输入的数值有误);N = 0;settextstyle(18, 0, _T(楷体);outtextxy(xb4 + 50, yb0 + 95, 以回车键确认);setcolor(0xD9D9D9);settextstyle(12, 0, _T(宋体);outtextxy(xb0 + 6, yb0 + 6, 请输入cutoff值);outtextxy(xb2 + 6, yb2 + 6, 请输入median值);setcolor(BLACK);setbkmode(TRANSPARENT);settextstyle(18, 0, _T(宋体);choice = ResponseMouse(xb00, yb00, xb01, yb01, xb02, yb02, xb03, yb03, xb04, yb04, xb05, yb05);if (choice = 1)InputName();InputPsd();void InputName()char NameNameMaxLength = , , , , , , , , , , ,0 ;char c;int i = 0;/下面2句用于覆盖用户名输入框中的提示文字setfillcolor(0xFFFFFF);fillrectangle(xb00, yb00, xb01, yb01);setbkcolor(0XFFFFFF);/设置输入文本的背景颜色为白色setbkmode(OPAQUE);/设置文本背景模式为不透明while (1)if (_kbhit()/判断是否检测到键盘输入，有则获取键入字符，无则闪烁光标c = _getch();/有键盘输入，则获取键入字符 /输入为Tab键或回车键，则表示用户输入结束，此时要去掉输入框中的竖线，并输出 /然后结束输入if (c = 9 | c =