【数据结构】排序算法：希尔、归并、快速、堆排序
08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.csdn.net/xiaowei_cqu/article/details/7747205
归并排序归并排序是采用分治的思想将两个已排序的表合并成一个表
归并排序算法的基本思想是：先将一个表分成两个表（当个数是奇数时，使左表的元素比右表多一）。对两个表分别进行归并排序，然后将两个已排序好的表合并。合并的思路就像将两罗纸牌混成一摞，每次取顶上最小的纸牌。
【相关实验】
1.仍旧使用上述的Sortable_list
2.根据归并排序的思想，每次子表仍旧使用归并排序，可以通过递归实现。所以编写递归函数recursive_merge_sort()，要把已排序好的子表合并，所以编写合并子表的辅助函数merge（）
3.为了输出每趟排序结果，在归并时merge中加入traverse(print_out) //但因为递归调用的问题，很多次我们还是看不到过程
快速排序快速排序是对冒泡排序的一种改进。
快速排序算法的基本思想是：每一趟排序中找一个点pivot，将表分割成独立的两部分，其中一部分的所有Record都比pivot小，另一部分比pivot大，然后再按此方法对这两部分数据分别进行快速排序。
【相关实验】1.仍旧使用上述的Sortable_list。
2.根据快速排序的思想，每趟排序将表分成两部分然后仍旧进行快速排序，所以可以通过递归实现，而为了调用递归函数，我们首先编写给定要排序范围的参数的函数recursive_quick_sort(int low,int high)//之所以不将开始的quick_sort直接写作递归函数，是为了避免输入参数而方便用户调用。另外需要一个partition函数，返回每趟排序之后的分点。
3.为了输出每趟排序，我的想法是在每次递归中使用traverse（print_out）输出，但却不是想象的结果。因为递归是每次递归出来之后才执行函数print_out，除了前几次可以看到结构，后来都是在排序好之后…所以我们仍旧通过swap函数实现输出。
堆排序堆排序是先将表中Record按大堆（或小堆）存放，使选取最大的Record变的极为容易，每次选取之后再提升堆。实现排序。
继续：
【相关实验】1.仍旧使用上述的Sortable_list。
2.编写heap_sort()函数。按思路，首先应该建堆，然后取堆顶元素，之后对剩下元素重新建堆（提升堆），所以我们需要编写build_heap()函数，其通过inster_heap函数将元素一个个插入堆中。
最后实现heap_sort函数。
3.我们在每次插入堆时调用traverse(print_sort)实现对每趟排序的输出。
结果分析【希尔排序】1.希尔排序是直接插入的一种改进，在效率上较直接插入排序有较大的改进。
直接插入排序每次只能将Record移动一个位置，即增量increment为1，而希尔排序开始时增量较大，分组较多，每组Record数目少，故各组内直接插入较快；increment递减之后分组逐渐减少，Record增多，但由于已经在increment较大时进行过排序，表更接近于有序状态，新一趟的排序也较快。
2.我在实验中子表的排序是通过定义一个新表，然后调用直接插入函数。但这种方法效率并不高，而且浪费空间；直接对子表进行直接插入的排序是一种更好的方法。
3.希尔排序复杂度为：O(nlog2n) d =1希尔与直接插入排序基本一致
4.希尔排序是不稳定的排序算法，即相等元素的顺序可能改变
【归并排序】1.归并排序在实现上用链式表更为合理，因为合并中需要定义新的表，即使我们通过动态定义再删除，以节省不必要的空间，这些工作仍是有些费时。而链式表只是返回指针，对节点Node的Node<Node_entry>*next部分进行操作，不需要数据的移动。但同时链式表的使用也需要对指针有熟悉的掌握，很容易出错，先画图再编码往往会有更清晰的思路。
2.归并排序的复杂度为：O(nlog2n)
3.归并排序是稳定的排序算法，即相等元素的顺序不会改变
【快速排序】1.复杂度：最好 O(nlog2n)，最坏 O(n2)
2.快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。
3.快速排序是一种不稳定的排序算法
【堆排序】1.实现堆排序很重要的一个操作就是建堆
要将初始表调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。显然只有一个结点的树是堆，而在完全二叉树中，所有序号大于n/2的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为n/2，…，1的结点作为根的子树都调整为堆即可。
2.堆[排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，堆排序的最坏时间复杂度为O(nlog2n)。
3.堆排序是不稳定的排序算法
4.由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序每次在大堆中直接选择出顶即最大的元素，这与选择排序极为相似，但他们是不同的，堆排序的性能更为优越。因为选择排序中，为了从表中选出最小的记录，必须进行n-1次比较，然后在剩余表中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。
转载请注明出处：http://blog.csdn.net/xiaowei_cqu/article/details/7770838
