还剩22页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》排序THE FIRSTLESSON OFTHE SCHOOLYEARCONTENTS目录•排序概述•插入排序•选择排序•冒泡排序•快速排序01排序概述排序的定义排序的定义将一组数据按照一定的顺序排列,以便更好地满足某些特定的需求或目的排序通常用于数据的检索、分析和处理,是计算机科学和数据处理领域中非常重要的基础技术之一排序的分类根据不同的分类标准,排序可以分为多种类型常见的分类标准包括排序的稳定性、时间复杂度、空间复杂度、是否使用额外空间等根据稳定性,排序可以分为稳定排序和不稳定排序;根据时间复杂度,排序可以分为线性时间复杂度排序和非线性时间复杂度排序;根据空间复杂度,排序可以分为原地排序和需要额外空间的排序等排序的算法复杂度要点一要点二要点三算法复杂度时间复杂度空间复杂度算法复杂度是衡量算法性能的重要指时间复杂度表示算法执行所需的时间,空间复杂度表示算法所需的最大存储标,包括时间复杂度和空间复杂度通常用大O表示法来表示常见的排空间空间复杂度也用大O表示法来时间复杂度表示算法执行所需的时间,序算法时间复杂度包括On^
2、表示常见的排序算法空间复杂度包空间复杂度表示算法所需的最大存储Onlogn、On等其中,On^2括O
1、Ologn、On等其中,空间算法复杂度越低,算法的性能表示算法的时间复杂度与输入数据量O1表示算法的空间复杂度为常数,越好的平方成正比,如冒泡排序;即不需要额外的存储空间,如冒泡排Onlogn表示算法的时间复杂度与输序、选择排序等;Ologn表示算法入数据量的对数成正比,如归并排序、的空间复杂度与输入数据量的对数成快速排序等;On表示算法的时间复正比,如二分查找等;On表示算法杂度与输入数据量成正比,如计数排的空间复杂度与输入数据量成正比,序、基数排序等如归并排序、快速排序等01插入排序插入排序的原理时间复杂度On^2,最坏情况下为On^2,最好情况下为On空间复杂度O1插入排序的步骤
011.将数组分为已排序和未排序两部分,初始时已排序部分包含一个元素
022.从未排序部分取出元素,并在已排序部分找到合适的插入位置插入
033.重复步骤2,直到未排序部分元素为空插入排序的优缺点优点实现简单,稳定,时间复杂度在最好情况下为On缺点比较次数较多,特别是当数据量较大时,效率较低01选择排序选择排序的原理选择排序的基本思想是在未排序的序列中找到最小(或最01大)元素,存放到排序序列的起始位置,然后再从剩余未排序的元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾以此类推,直到所有元素均排序完毕选择排序的关键在于每次从未排序的元素中找到最小(或02最大)元素,并与已排序序列的末尾元素进行交换选择排序的时间复杂度为On^2,其中n为待排序元素的03数量选择排序的步骤
011.找到未排序部分的最小(或最大)元素,将其与未排序部分的第一个元素交换位置
022.找到未排序部分的最小(或最大)元素,将其与未排序部分的最后一个元素交换位置
033.重复步骤1和步骤2,直到未排序部分为空选择排序的优缺点优点选择排序算法实现简单,对于小型数据集具有一定的效率缺点选择排序的时间复杂度为On^2,对于大规模数据集效率较低,不适合实际应用此外,选择排序在数据分布不均的情况下表现较差,无法保证稳定的排序性能01冒泡排序冒泡排序的原理冒泡排序的基本原理是比较相邻的两个元素,如果顺序错误则交换它们,直到没有需要交换的元素为止在每一轮比较中,最大的元素会被“冒泡”到数组的末尾,因此得名“冒泡排序”冒泡排序的步骤遍历整个数组,比较相邻的两个元素,如果顺序错误01则交换它们02重复步骤1,直到没有需要交换的元素为止03重复步骤1和2,直到整个数组有序冒泡排序的优缺点优点实现简单,不需要额外的存储空间缺点时间复杂度高,对于大规模数据的排序效率较低01快速排序快速排序的原理快速排序是一种分而治之的排序算法,通过选择一个基准元素,将待排序序列划分为两个子序列,一个子序列的所有元素都比基准元素小,另一个子序列的所有元素都比基准元素大,然后对这两个子序列递归进行快速排序,从而达到整个序列有序快速排序的基本思想是利用分治策略,将问题分解为若干个子问题,然后递归地解决这些子问题,最后将子问题的解合并得到原问题的解快速排序的步骤合并有序序列划分序列D将两个已排序的子序列合并为一个有序序将待排序序列划分为两个子序列,一个子列序列包含所有小于基准的元素,另一个子序列包含所有大于基准的元素CB递归排序子序列选择一个基准元素A对划分的两个子序列分别进行快速排序通常选择待排序序列的第一个元素作为基准元素快速排序的优缺点优点平均时间复杂度为Onlogn,最坏情况下时间复杂度为On^2,但在实际应用中,快速排序通常具有较好的性能快速排序在处理大数据集时,由于其内部循环可以在缓存中完成,因此具有较好的空间效率快速排序的优缺点•快速排序是一种原地排序算法,不需要额外的存储空间快速排序的优缺点01缺点02快速排序在选择基准元素时存在一定的随机性,可能会导致最坏情况的出现03快速排序在处理特定数据集时可能不如其他算法高效,例如已经部分有序的数据集感谢观看THANKSTHE FIRSTLESSON OFTHE SCHOOLYEAR。