还剩28页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
常用算法排序•排序算法概述目•冒泡排序•选择排序录•插入排序•快速排序•归并排序01排序算法概述排序的定义排序的定义排序是指将一组数据按照一定的顺序排列,以便进行查找、检索等操作排序的顺序排序的顺序可以是升序或降序,升序是指从小到大排列,降序是指从大到小排列排序的稳定性如果两个元素相等,排序后它们的位置不会改变,则称该排序算法是稳定的排序的分类按照比较方式01比较排序和非比较排序比较排序是指通过元素之间的比较来确定位置,而非比较排序是指不通过元素之间的比较来确定位置按照时间复杂度02线性时间复杂度排序和非线性时间复杂度排序线性时间复杂度排序是指时间复杂度为On,非线性时间复杂度排序是指时间复杂度大于On按照空间复杂度03原地排序和需要额外空间的排序原地排序是指在原有数组上进行排序,不需要额外空间;需要额外空间的排序是指需要开辟额外的存储空间来存储临时数据排序算法的性能指标01020304时间复杂度空间复杂度稳定性可读性衡量算法执行效率的重要衡量算法所需额外空间的衡量算法在处理相等元素衡量算法可理解性和可维指标,表示算法执行所需重要指标,表示算法执行时是否保持原有顺序的重护性的重要指标,良好的的时间与数据量之间的关过程中所需额外空间的大要指标可读性可以提高代码的可系小读性和可维护性02冒泡排序冒泡排序的基本思想冒泡排序的基本思想是通过相邻元素之间的比较和交换,使得每一轮循环都能将当前未排序部分中最大的元素“冒泡”到未排序部分的末尾具体来说,从第一个元素开始,依次比较相邻的两个元素,如果前一个元素比后一个元素大,则交换它们的位置这样一轮循环下来,最大的元素就会被“冒泡”到未排序部分的末尾冒泡排序的算法实现冒泡排序的算法实现通常使用一个循环结构,循环遍历未排序部分的所有元素,依次比较相邻的两个元素并进行交换具体的算法实现可以描述为对于未排序部分中的每一个元素,如果它比它后面的元素大,则交换它们的位置这样一轮循环下来,最大的元素就会被“冒泡”到未排序部分的末尾重复这个过程,直到整个数组都排好序为止冒泡排序的时间复杂度与空间复杂度冒泡排序的时间复杂度是On^2,其中n是数组的长度这是因为冒泡排序需要遍历整个数组多次,每次遍历都需要进行n次比较和交换操作冒泡排序的空间复杂度是O1,因为冒泡排序只需要常数级别的额外空间来存储循环变量等控制结构,不需要额外的存储空间来存储数据元素03选择排序选择排序的基本思想010203选择排序的基本思想是在未排然后再从剩余未排序的元素中以此类推,直到所有元素均排序的序列中找到最小(或最大)继续寻找最小(或最大)元素,序完毕的元素,存放到排序序列的起然后放到已排序序列的末尾始位置选择排序的算法实现010203第一步第二步第三步找到未排序部分的最小再从剩余未排序的元素中重复第二步,直到所有元(或最大)元素,存放到继续寻找最小(或最大)素均排序完毕排序序列的起始位置元素,然后放到已排序序列的末尾选择排序的时间复杂度与空间复杂度时间复杂度选择排序的时间复杂度为On^2,其中n为待排序元素的数量因为选择排序需要多次遍历待排序序列,并在每次遍历中执行n次比较操作空间复杂度选择排序的空间复杂度为O1,因为选择排序只需要常数级别的辅助空间,不需要额外的存储空间04插入排序插入排序的基本思想插入排序的基本思想是将数组分为已排序和未排序两部分,初始时已排序部分包含一个元素,然后从未排序部分取出元素,并在已排序部分找到合适的插入位置插入,并保持已排序部分一直有序,重复此过程,直到未排序部分元素为空插入排序在每一步中都通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入插入排序在实现上,通常采用in-place排序(即只需用到O1的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间插入排序的算法实现插入排序的算法实现通常采用迭代的方式进行,即通过for循环从第二个元素开始遍历数组,对于当前元素,将其与已排序部分的元素逐个比较,找到合适的位置后插入在具体实现上,可以采用in-place的插入排序算法,即通过交换元素的方式将已排序部分向后移动,为新元素腾出空间插入排序算法的时间复杂度为On^2,其中n为数组的长度插入排序的时间复杂度与空间复杂度插入排序的时间复杂度为On^2,其中n为数组的长度这是因为在最坏情况下,需要比较n*n-1/2次才能完成排序插入排序的空间复杂度为O1,因为只需要用到常数级别的额外空间05快速排序快速排序的基本思想分治法将数组分为两个子数组,分别对子数组进行排序,然后合并已排序的子数组递归快速排序是一个递归算法,每次递归都将数组分为更小的子数组,直到子数组的大小为1或0随机化为了减少最坏情况下的时间复杂度,可以使用随机化选择一个基准元素快速排序的算法实现选择基准元素选择一个基准元素,将数组分为两个子数组,一个子数组的所有元素都小于基准元素,另一个子数组的所有元素都大于基准元素递归排序子数组对两个子数组递归地执行快速排序合并已排序的子数组将两个已排序的子数组合并成一个已排序的数组快速排序的时间复杂度与空间复杂度时间复杂度空间复杂度平均情况下,快速排序的时间复杂度为快速排序是一个原地排序算法,不需要额外Onlogn在最坏情况下,时间复杂度为的存储空间,空间复杂度为OlognOn^206归并排序归并排序的基本思想归并排序是一种分治算法,它将一个无序数组分割成两个较小的子数组,分别对子数组进行排序,然后将有序的子数组合并成一个完整的排序数组基本思想是将问题分解为若干个较小的子问题,递归地解决这些子问题,然后将解决子问题的结果合并为解决原问题的结果归并排序的算法实现算法步骤
11.将数组分割成两个子数组,直到子数组的大小2为
12.对每个子数组递归地应用归并排序3归并排序的算法实现•将已排序的子数组合并成一个完整的排序数组归并排序的算法实现01具体实现
021.定义函数merge_sortarr,输入一个无序数组arr
032.如果arr的大小小于2,直接返回arr归并排序的算法实现
3.将arr分割成两个子数组left和right,大小分别为arr[0,mid]和arr[mid+1,n-
5.定义函数mergeleft,1],其中mid是arr的中间索right,输入两个已排序的子引数组left和right
4.递归调用merge_sortleft和merge_sortright,分别对两个子数组进行排序归并排序的算法实现
6.合并left和right为一个完整的排序数组result
7.在merge_sort函数中调用mergeleft,right,将已排序的子数组合并为一个完整的排序数组归并排序的时间复杂度与空间复杂度时间复杂度空间复杂度归并排序的时间复杂度为Onlogn,其归并排序的空间复杂度为On,这是因为中n是数组的大小这是因为在最坏的情在最坏的情况下,归并排序需要使用一个况下,归并排序需要对数组进行完全二VS额外的数组来存储合并过程中的临时数据,分,每次合并两个已排序的子数组需要大小与原数组相同On的时间复杂度,因此总的时间复杂度为Onlogn。