排序算法学习报告

1、排序算法学习报告一、 学习内容所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的 相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这 种排序方法是不稳定的。要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有 一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。常见的排序算法2. 1插入排序插入排序是这样实现的：首先新建一个空列表，用于

2、保存已排序的有序数列（我们称之为有序列表）O从原数列中取出一个数，将其插入有序列表中，使其仍旧保持有序状态。重复2号步骤，直至原数列 为空。插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了逐步扩大成果的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。【示例】：初始关键字4938 65 97 76 13 27 49J=2 (38)J=3 (65)J=4 (97)J=5 (76)J=6(13)J=7 (27)J=8 (49)3838383813132713 2765977613274965977613274965977613274965769713274949657

3、6972749494949493865 76 9749493838 49 49 65 76 972.2冒泡排序冒泡排序是这样实现的：首先将所有待排序的数字放入工作列表中。从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的 下一位交换。重复2号步骤，直至再也不能交换。冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法【示例】：4913131313131313384927272727272765384938383838389765384949494949769765494949494913769765656565652727769

4、77676767649494976979797972. 3选择排序选择排序是这样实现的：设数组内存放了 n个待排数字，数组下标从1开始，到n结束。i=l从数组的第i个元素开始到第n个元素，寻找最小的元素将上一步找到的最小元素和第i位元素交换。如果i二n -1算法结束，否则回到第3步【示例】：初始关键字49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后13 27 38 97 76 49 65 49第四趟排序后13 27 38 49 49 97 65 76第五趟排序后13

5、2738 49 4997 97 76第六趟排序后132738 49 497676 97第七趟排序后132738 49 497676 97最后排序结果132738 49 497676 972. 4快速排序基本思想：在当前无序区RE1.H中任取一个数据元素作为比较的基准（不妨记为X）,用此 基准将当前无序区划分为左右两个较小的无序区：Rl1-1和RI+1H,且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即 Rl. . 1-1 X. KeyW RI+1.H （1 I H），当 Rl. . 1-1和 RI+1. .H 均非空时

6、，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。【示例】：初始关键字4938 65 97 76 13 27 49第一次交换后27 38 65 97 76 1349 49第二次交换后27 38 49 97 76 136549 J向左扫描，位置不变，第三次交换后27 3813 97 76 49 65 49 I向右扫描，位置不变，第四次交换后27 3813 49 76 97 65 49 J 向左扫描27 38 13 49 76 97 65 49（一次划分过程） 初始关键字49 38 65 97 76 13 27 4965 49 -趟排序之后27 38 13 49 76 97

7、二趟排序之后13 27 38 49 4965 7697 三趟排序之后13 27 38 49 4965 76 97最后的排序结果13 27 38 49 49 65 76 972. 5堆排序基本思想：堆排序是一树形选择排序，在排序过程中，将RC1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。堆的定义：N个元素的序列KI, K2, K3,，Kn.称为堆，当且仅当该序列满足特性：Ki K2i Ki K2i+1 （1 I N/2）堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10, 15,

8、56, 25, 30, 70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。排序过程：堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨 利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆 顶记录，将它和无序区中的最后一个记录交换。这样，正好和直 接选择排序相反，有序区是在原记录区 的尾部形成并逐步向前扩大到整个记录区。2. 6希尔排序希尔(Shell)排序的基本思想是：先取

9、一个小于n的整数di作为第一个增量把文件的全部记录 分成di 个组。所有距离为di的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二 个增量d2dl重复上述的分组和排序，直至所取的增量di=l,即所有记录放在同一组中进行直接插入 排序为止。该方法实质上是一种分组插入方法。一般取dl= n/2, di+1二di/2。如果结果为偶数，贝U加1,保证di为奇数。2. 7归并排序归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序 列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它 们两两合并。直到得到长

10、度为n的有序表，排序结束。归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为0(n)故其时间复杂度无论是在最好情况下还是在 最坏情况下均是O(nl og2 n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅 助空间复杂度为0( n),显然它不是就地排序。3常见排序算法比较序号排序类别时间复杂度空间复杂度稳定1插入排序0( n2)1V2希尔排序0( n2)1X3冒泡排序0( n2)1V4选择排序0( n2)1X5快速排序0(Nlog n)0(log n)X6堆排序0(Nlog n)1X7归并排序0(Nl

11、og n)0(n)V稳定性分析首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai二Aj, Ai原来在位置前，排序后Ai还是要在A j位置前。其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排 序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排 序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排 序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)o回到主题，现在分

12、析一下常见的排序算法的稳定性，每个都给出简单的理由。冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交 换一下的； 如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所 以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。(2) 选择排序选择排序是给每个位置选择当前元素最小的，里面给第二个元素选择第二小的，依次类推，直到第 因为只剩下它一个最大的元素了。那么，在一趟选择, 现在一个和当前元素相等的元素后面，比如给第一个位置选择最小

13、的，在剩余元素n-1个元素，第n个元素不用选择了，如果当前元素比一个元素小，而该小的元素又出那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。(3) 插入排序插入排序是在一个己经有序的小序列的基础上，一次插入一个元素。当然，冈寸开始这个有 序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入 的元素和已经有 序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如 果碰见一个和插入元素相等

14、的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的 前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。(4) 快速排序快速排序有两个方向，左边的i下标一直往右走，当ai acenter_index。如果 i 和 j 都走不动了，i二 j,交换 ai和 aj,重复上面的过程，直到ij。交换aj和aLcenter_index,完成一趟快速排序。在中枢元素和aj交换 的时候，很有可能把前面的元素的稳定性打乱，比如序列为5334389 10 11现在中枢元素5和3 （第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是 一个不稳定的排

15、序算法，不稳定发生在中枢元素和aj交换的时刻。（5）归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也 没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没 有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列 的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。希尔排序（shell）希尔排序是按照

16、不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入 排序的兀素个数很少，速度很快；当兀素基本有序了，步长很小，插入排序对于有序的序列效率很高。 所以，希尔排序的时间复杂度会比o（nA2）好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的 元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。堆排序我们知道堆的结构是节点i的孩子为2*i和2*i+l节点，大顶堆要求父节点大于等于其2个子节 点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始

17、和 其子节点共3个值选择最大（大顶堆）或者最小（小顶堆）,这3个元素之间的选择当然不会破坏稳定性。 但当为n /2-1, n /2-2,1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交 换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。综上，得出结论：选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排 序、归并排序是稳定的排序算法。二、心得体会刚接触到算法这门课的时候，对算法没什么具体的概念，总感觉学习这门课和之前的两门程序设计 课程应该没什么区别

18、，无非就是编程而已，但慢慢的我发现，算法不止是那么简 单。Pascal语言的创始 人N. Wirth用这样一个公式来总结算法的地位:算法+数据结构二程序通过上面这个被广大程序员普遍认同的公式可以看出，算法在程序设计中所占的重要位 置，算法是 程序的灵魂是完全正确的。一般的程序设计方法也就是编程步骤主要有以下的几个方面：分析问题、设计算法、编 写程序和调 试程序。其中设计算法作为整个程序调试的基础，只有先设计出巧妙的算法思想，才能保证在之后的程 序能高效的执行，编写代码只不过是用某种语言来实现算法的一个具体 表现形式而己。就好比排序算 法，其实我们已经学过好几种排序的算法，之前一直没怎么注意它们的区别，要用到排序的时候想到哪 个或者哪个比较熟手就用那个，经过这次的整理、比较及分析我对这几个排序算法有了更深入的了解及 新的看法，同时自己也稍作了总结：插入、冒泡排序的速度较慢，但参加排序的序列局