数据结构课程设计--单独实现各种排序.doc

湖北民族学院信息工程学院2011级计算机专业班数据结构课程设计设计报告 数据结构课程设计设计报告 课程设计题目 单独实现各种排序 学生姓名 学生学号 学院名称 信息工程学院指导教师 2013 年 5 月 4 日v 目录v 目录1v 需求分析3v 概要设计4 直接插入排序的设计思路4 折半插入排序的设计思路4 希尔排序的设计思路5 冒泡排序设计思路5 快速排序设计思路5 直接选择排序的设计思路6 堆排序的设计思路6 归并排序的设计思路8 基数排序的设计思路9v 详细设计11 直接插入排序11 折半插入排序12 希尔排序13 冒泡排序15 快速排序16 直接选择排序17 堆排序18 归并排序20 基数排序22v 调试分析25 直接插入排序25 折半插入排序26 希尔排序27 冒泡排序27 快速排序28 直接选择排序28 堆排序29 归并排序29 基数排序30v 数据结构课程设计总结31 课程设计的收获31 遇到的问题及解决思路32 对数据结构课程的思考32v 参考文献33第 1 页 共 33 页v 需求分析 排序时计算机程序设计中一种重要的操作，它的功能将包含多个数据元素的任意序列，重新排列成一个按关键字有序的序列。 由于待排序的元素数量不同，使得排序过程中的时空开销也不同。没有一种排序算法可以适合任何一种场合，每种排序算法都有适合的特殊环境，只有在这种特殊环境中才能发挥这种排序算法的优势。 排序在很多的场合都会用到，一个优秀的排序算法可以使程序的运行效率提高，节约时空资源。 其中对整数或者是实数的排序用得最多，大多数情况下都是要求对一组无序的数据按照数据值的大小以增序或者以降序排列数据。 例如对一组学生的成绩从高到低排序，以确定学生的名次。又如要求对员工的工资排序，以方便管理。在现实生活中要用到排序的地方不胜枚举，虽然很多高级程序设计语言都封装了排序的算法，用来也方便，程序员也容易掌握和运用，但是这些封装好了的排序算法将会一成不变的按照设计者当初设计时设计的步骤工作，无法在实际情况中进行优化，也就不以利于提高程序的总体效率，所以根据实际的情况编写实际的排序算法才是可行的。本次课程设计单独实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。v 概要设计 直接插入排序的设计思路直接插入排序是一种最简单的排序方法，他的基本操作是将一个数据元素直接插入到已排好序的一组数据中，从而得到一个新的元素数加一的有序表。 由于数据存储结构采用的是数组，所以插入一个元素就涉及到查找待插入元素的位置，移动其他元素，而数组头一个结点设为哨兵结点。如图1所示：在序列1，3，5，8中插入4 图1这样就有完成了一次插入，重复这种操作直到整个数组有序为止。 折半插入排序的设计思路 折半插入排序是在直接插入排序的基础上减少了比较和移动的次数从而提高算法的效率，因为待插入数据前面的所有数据已经有序了。先用两个指针low和high通过折半查找的方法确定待插入数据的位置，最后low所指向的位置即为待插入数据的位置，先将把待查入数据放到0号单元然后low以后的单元依次后移一位然后将0号单元的数据插入到low指向的单元中，重复这个操作直到整个数组有序。 希尔排序的设计思路 希尔排序的设计思想是：先将整个待排序数列分割成若干子序列，对子序列分别进行直接插入排序，待整个序列基本有序时再对整个数列进行一次直接插入排序。 冒泡排序设计思路冒泡排序很简单，首先将第一个数据的关键字和第二个数据的关键字比较，若为逆序，则将两个数据交换，然后比较第二个和第三个数据的关键字，以此类推，直到第n-1个数据和第n个数据进行比较。然后重复上述操作，第i次循环只进行到第n-i个为止，因为n-i以后的数据已经有序了。 快速排序设计思路 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分关键字均比另一部分关键字小，然后分别对这两部分继续排序直到整个有序。如图2所示：第一次找到3的位置3和6交换，1和4交换；第二次找到1的位置1和2交换，6的位置不变；第三次找到4的位置4和5交换，至此整个序列有序。 图2 直接选择排序的设计思路一趟直接选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个数据中选出关键字最小的数据，并和第i个数据交换，重复n-1次就得到了一个有序的序列。 堆排序的设计思路堆排序只需要一个数组就可以了，每个数据占一个存储空间。堆的定义如下：对n个元素的序列K1，K2，Kn当且仅当满足下列关系时称之为堆：Ki=K2i&Ki=K2i+1 或者 K2i=Ki&K2i+1=Ki前者称为最小堆，后者称为最大堆。 如图3所示：对序列8 ， 1 ， 7 ， 4， 5 ，3建堆如图4.1-4.5所示排序过程：最终为1，3，4，5，7，8 图3图4.1 图4.2 图4.3图4.4图4.5 归并排序的设计思路 假设初始序列为n个数据元素，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者为1的有序子序列，然后再两两归并直到得到一个长度为n的有序序列为止。这种排序称为2路归并排序。2路归并排序的核心操作就是将两个有序序列归并为一个有序序列。 如图5所示：图5原始序列为4，1，5，3，2。第一趟排序后将4，1合并，5，3合并后为1，4，3，5，2第二趟合并后将1，4和3，5合并后为1，3，4，5，2第三趟合并后将1，3，4，5和2合并为1，2，3，4，5。 基数排序的设计思路基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序。例如关键字k是数字且在0到999之间，则可以把每个十进制数字看成一个关键字，k由3个关键字（k1，k2，k3）组成，分别对应k的百位，十位，个位数字。所以如果有一个这样的数字序列，从低位关键字起按关键字的不同值将数据元素分配到09标记的队列中然后在收集，如此重复3次即可。基数的“基”就是每个关键字的取值范围，这里是10。假设每个关键字ki在0，2之间，则有三个队列。有序列：002，202，011，210，001，101则排序过程如图6.16.3所示： 图6.1第一趟排序之后的序列为：（以个位数字为关键字）210，011，001，101，002，202 图6.2第二趟排序之后序列为：（以十位数字为关键字）001，101，002，202，210，011 图6.3第三趟排序之后序列为：（以百位数字为关键字）001，002，011，101，202，210v 详细设计 直接插入排序int * array代表待排序的数组，length代表待排序数组的长度，array0设为监视哨。void InsertSort(int * array , int length) for(int i = 2 ; i = length ; i+) if(arrayi arrayi-1) array0 = arrayi; arrayi = arrayi-1; int j;/查找合适的位置并移动数据 for(j = i-2 ; array0 arrayj ; j-) arrayj+1 = arrayj;/在合适的位置插入数据 arrayj+1 = array0; 折半插入排序int * array代表待排序的数组，length代表待排序数组的长度void BInsertSort(int * array , int length) for(int i = 2 ; i = length ; i+) array0 = arrayi; int low = 1 , high = i-1; /折半查找插入的合适的位置 while(low = high) int mid = (low+high)/2; if(array0 = low ; j-) arrayj+1 = arrayj; /low的位置即array0的正确位置 arraylow = array0; 希尔排序int * array代表待排序的数组，length代表待排序数组的长度，increment代表增量void ShellInsert(int * array , int length , int increment)/间隔为增量的子序列使用直接插入排序 for(int i = increment+1 ; i = length ; i+) if(arrayi 0 & array0 =1) ShellInsert(array , length , increment); /逐步减小增量直至为1 increment /= 2; 冒泡排序int * array代表待排序的数组，length代表待排序数组的长度void BubbleSort(int * array , int length) for(int i = length , change = true; i 1 & change ; i-) change = false; for(int j = 1 ; j arrayj+1) change = true; swap(arrayj , arrayj+1); 快速排序int * array代表待排序的数组，length代表待排序数组的长度，将p到r之间比arrayr小的数据已到arrayr前，比arrayr大的移到后面，并返回arrayr的正确位置。int Partition(int * array , int p , int r) int x = arrayr; /下标小于等于i的数据都比x小，否则比x大 int i = p-1; for(int j = p ; j r ; j+) if(arrayj = x) i+; swap(arrayi , arrayj); swap(arrayi+1 , arrayr); /返回第一个比x大的位置，即arrrayr的合适位置 return i+1;/快速排序主函数void QuickSort(int * array , int p , int r) if(p r) int q = Partition(array , p , r); QuickSort(array , p , q-1); QuickSort(array , q+1 , r); 直接选择排序 int * array代表待排序的数组，length代表待排序数组的长度，找到从bgn到length之间最小的数据的位置int SelectMinKey(int * array , int length , int bgn) int min = arraybgn , j = bgn; for(int i = bgn+1 ; i arrayi) min = arrayi; j = i; return j;/选择排序主函数void SelectSort(int * array , int length) for(int i = 1 ; i length ; i+) int j = SelectMinKey(array , length , i); /将最小的数据交换到位置i if(i != j) swap(arrayi , arrayj); 堆排序int * array代表待排序的数组，heapLength代表堆的长度，i代表第i个结点，保持最大堆的性质void MaxHeapify(int * array , int heapLength , int i) int l = i*2; int r = i*2+1; /父结点和左右儿子中最大值的位置 int largest; if(l arrayi) largest = l; else largest = i; if(r = heapLength & arraylargest = 1 ; i-) MaxHeapify(array , heapLength , i);/堆排序主函数void HeapSort(int * array , int length) BuildMaxHeap(array , length); int heapLength = length; for(int i = length ; i = 2 ; i-) /将堆顶的数据和堆最后个数据交换，堆顶的数据最大 swap(array1 , arrayheapLength); /堆的大小减一 heapLength-; /调整堆使之始终满足最大堆的性质 MaxHeapify(array , heapLength ,1); 归并排序将有序的ary1i.m和ary1m+1,n合并为有序的ary2i.nvoid Merge(int * ary1 , int * ary2 , int i , int m , int n) int j , k; for(j = m+1 , k = i ; i = m & j = n ; k+) if(ary1i ary1j) ary2k = ary1i+; else ary2k = ary1j+; if(i = m) for(; i = m ; i+) ary2k+ = ary1i; if(j = n) for(; j = n ; j+) ary2k+ = ary1j; /将arySources.t归并为有序的aryResults.tvoid MergeSort(int * arySource , int * aryResult , int s , int t) if(s = t) aryResults = arySources; else int m = (s+t)/2 , aryTmp9; /将arySources.m归并为有序的aryTmps.m MergeSort(arySource , aryTmp , s , m); /将arySourcem+1.t归并为有序的aryTmpm+1.t MergeSort(arySource , aryTmp , m+1 , t);/将aryTmps.m，aryTmpm+1.t归并为有序的aryResults.t Merge(aryTmp , aryResult , s , m , t); 基数排序元素的存储结构，为方便计算将关键值设为string类型struct Data string key;/数据的关键字 int next;/下一个数据的位置 array12;/每个队列的头指针和为指针int front10 , trail10;/创建静态链表void CreateLinkList(string key , int index , int pre) arraypre.next = index; arrayindex.key = key; arrayindex.next = 0;/获得数据的第i位数（将字符变为整数）int order(int i , string key) return keyi-0;分配函数，按数据的第i位关键字将数据放入相应的队列中void Distribute(int i) memset(front , 0 , sizeof(front); for(int p = array0.next ; p ; p = arrayp.next) int j = order(i , arrayp.key); if(!frontj) frontj = trailj = p; else arraytrailj.next = p; trailj = p; 收集函数，合并各个队列中的数据，顺序从0号队列到9号队列void Collect() int i = 0; /找到第一个非空的队列 while(i 10 & !fronti) i+; array0.next = fronti; int tmp = traili; for(i+; i = 0 ; i-) Distribute(i); Collect(); v 调试分析 直接插入排序输入数据：49，38，65，97，76，13，27，49正确结果：13，27，38，49，49，65，76，97本算法时间复杂度为：O(n2)运行结果： 折半插入排序输入数据：49，38，65，97，76，13，27，49正确结果：13，27，38，49，49，65，76，97本算法时间复杂度：O(n2)运行结果： 希尔排序输入数据：49，38，65，97，76，13，27，49，55，04正确结果：4，13，27，38，49，49，55，65，76，97时间复杂度：O(n(3/2)运行结果： 冒泡排序输入数据：49，38，65，97，76，13，27，49正确结果：13，27，38，49，49，65，76，97时间复杂度：O(n2)运行结果： 快速排序输入数据：49，38，65，97，76，13，27，49正确结果：13，27，38，49，49，65，76，97时间复杂度：O(nlogn)运行结果： 直接选择排序输入数据：49，38，65，97，76，13，27，49正确结果：13，27，38，49，49，65，76，97时间复杂度：O(n2)运行结果： 堆排序输入数据：4，1，3，2，16，9，10，14，8，7正确结果：1，2，3，4，7，8，9，10，14，16时间复杂度：O(nlogn)运行结果： 归并排序输入数据：49 38 65 97 76 13 27正确结果：13 27 38 49 65 76 97时间复杂度：O(nlogn)运行结果：调试问题思考和算法改进： 由于在归并排序主函数中用了3个数组arySource，aryResult，aryTmp，开始的时候aryTmp定义成全局变量结果程序老是运行错误，最后在每次递归调的用排序主函数本身时重新定义aryTmp，这样问题就解决了，因为全局aryTmp在递归调用的时候会把前面的结果覆盖掉。但是如果在数据量小的时候这样做还是可行的，如果一旦数据量非常大了递归调用会非常的耗时，而且每次递归调用都要临时开一个数组aryTmp这样非常浪费空间，一个好的改进思路就是把这个递归的算法该为非递归的。 基数排序输入数据：278，109，063，930，589，184，505，269，008，083正确结果：008，063，083，109，184，269，278，505，589，930时间复杂度： 对于n个数据元素（假设每个数据元素含d个关键字，每个关键字的取值范围为rd个值）进行基数排序的时间复杂度为O(d(n+rd)，其中每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集。运行结果：v 数据结构课程设计总结 课程设计的收获 通过本次课程设计，我再次复习并掌握了各种排