原创力文档- 1、本文档共30页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
常用算法排序
排序算法概述
冒泡排序
选择排序
插入排序
快速排序
归并排序
目录
排序算法概述
排序是指将一组数据按照一定的顺序排列，以便进行查找、检索等操作。
排序的定义
排序的顺序可以是升序或降序，升序是指从小到大排列，降序是指从大到小排列。
排序的顺序
如果两个元素相等，排序后它们的位置不会改变，则称该排序算法是稳定的。
排序的稳定性
按照比较方式
01
比较排序和非比较排序。比较排序是指通过元素之间的比较来确定位置，而非比较排序是指不通过元素之间的比较来确定位置。
按照时间复杂度
02
线性时间复杂度排序和非线性时间复杂度排序。线性时间复杂度排序是指时间复杂度为O(n)，非线性时间复杂度排序是指时间复杂度大于O(n)。
按照空间复杂度
03
原地排序和需要额外空间的排序。原地排序是指在原有数组上进行排序，不需要额外空间；需要额外空间的排序是指需要开辟额外的存储空间来存储临时数据。
01
02
03
04
时间复杂度
衡量算法执行效率的重要指标，表示算法执行所需的时间与数据量之间的关系。
空间复杂度
衡量算法所需额外空间的重要指标，表示算法执行过程中所需额外空间的大小。
稳定性
衡量算法在处理相等元素时是否保持原有顺序的重要指标。
可读性
衡量算法可理解性和可维护性的重要指标，良好的可读性可以提高代码的可读性和可维护性。
冒泡排序
冒泡排序的基本思想是通过相邻元素之间的比较和交换，使得每一轮循环都能将当前未排序部分中最大的元素“冒泡”到未排序部分的末尾。
具体来说，从第一个元素开始，依次比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置。这样一轮循环下来，最大的元素就会被“冒泡”到未排序部分的末尾。
冒泡排序的算法实现通常使用一个循环结构，循环遍历未排序部分的所有元素，依次比较相邻的两个元素并进行交换。
具体的算法实现可以描述为：对于未排序部分中的每一个元素，如果它比它后面的元素大，则交换它们的位置。这样一轮循环下来，最大的元素就会被“冒泡”到未排序部分的末尾。重复这个过程，直到整个数组都排好序为止。
选择排序
选择排序的基本思想是在未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置。
然后再从剩余未排序的元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
01
02
03
找到未排序部分的最小（或最大）元素，存放到排序序列的起始位置。
第一步
第二步
第三步
再从剩余未排序的元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
03
02
01
时间复杂度
选择排序的时间复杂度为O(n^2)，其中n为待排序元素的数量。因为选择排序需要多次遍历待排序序列，并在每次遍历中执行n次比较操作。
空间复杂度
选择排序的空间复杂度为O(1)，因为选择排序只需要常数级别的辅助空间，不需要额外的存储空间。
插入排序
插入排序的基本思想是将数组分为已排序和未排序两部分，初始时已排序部分包含一个元素，然后从未排序部分取出元素，并在已排序部分找到合适的插入位置插入，并保持已排序部分一直有序，重复此过程，直到未排序部分元素为空。
插入排序在每一步中都通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序的算法实现通常采用迭代的方式进行，即通过for循环从第二个元素开始遍历数组，对于当前元素，将其与已排序部分的元素逐个比较，找到合适的位置后插入。
在具体实现上，可以采用in-place的插入排序算法，即通过交换元素的方式将已排序部分向后移动，为新元素腾出空间。
插入排序算法的时间复杂度为O(n^2)，其中n为数组的长度。
插入排序的时间复杂度为O(n^2)，其中n为数组的长度。这是因为在最坏情况下，需要比较n*(n-1)/2次才能完成排序。
插入排序的空间复杂度为O(1)，因为只需要用到常数级别的额外空间。
快速排序
选择一个基准元素，将数组分为两个子数组，一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素。
选择基准元素
对两个子数组递归地执行快速排序。
递归排序子数组
将两个已排序的子数组合并成一个已排序的数组。
合并已排序的子数组
时间复杂度
平均情况下，快速排序的时间复杂度为O(nlogn)。在最坏情况下，时间复杂度为O(n^2)。
空间复杂度
快速排序是一个原地排序算法，不需要额外的存储空间，空间复杂度为O(logn)。
归并排序
归并排序是一种分治算法，它将一个无序数组分割成两个较小
文档评论（0）