🏆 作者简介,愚公搬代码 🏆《头衔》:华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主,腾讯云内容共创官,掘金优秀博主,51CTO博客专家等。 🏆《近期荣誉》:2023年华为云十佳博主,2022年CSDN博客之星TOP2,2022年华为云十佳博主等。
🏆《博客内容》:.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
常见的排序算法有以下几种:
术语 | 说明 |
---|---|
数据元素 | 要排序的数据的基本单位,可以是数字、字符、对象等 |
关键字 | 数据元素中用于排序的属性或值,可以是元素本身或元素的某个特定属性 |
升序 | 按照关键字的大小从小到大进行排序 |
降序 | 按照关键字的大小从大到小进行排序 |
稳定性 | 如果两个关键字相等的元素在排序后的序列中的相对位置保持不变,排序算法是稳定的;否则,排序算法是不稳定的 |
内部排序 | 排序过程中所有数据都能够全部加载到内存中进行排序 |
外部排序 | 排序过程中数据量太大,无法一次性加载到内存中,需要借助外部存储设备进行排序 |
比较排序 | 排序算法通过比较关键字的大小进行排序 |
非比较排序 | 排序算法不直接通过比较关键字的大小进行排序,而是利用元素的其他特性进行排序,如计数排序、桶排序和基数排序 |
原地排序 | 排序过程中只使用了常数级别的额外空间 |
时间复杂度 | 描述算法的耗时程度,即算法执行所需的时间 |
空间复杂度 | 描述算法所需的额外空间 |
直接插入排序是一种简单直观的排序算法,它的思想是将一个序列分为有序和无序两部分,每次从无序部分中取出一个元素,插入到有序部分的正确位置上,直到整个序列有序为止。
具体步骤如下:
时间复杂度:
希尔排序是一种基于插入排序的排序算法,也称为缩小增量排序。它通过逐步减小增量的方式分组并对元素进行比较和交换,最终实现整体的有序。
希尔排序的算法步骤如下:
希尔排序的时间复杂度取决于选取的增量序列,最好的情况下可以达到O(nlogn),最坏的情况下为O(n^2)。
简单选择排序是一种简单直观的排序算法,它的基本思想是每次从待排序的数据中选择最小(或最大)的元素,然后放到已排序序列的末尾,直至所有元素排序完毕。
具体的排序过程如下:
简单选择排序的时间复杂度为O(n^2),其中n为待排序序列的长度。虽然简单选择排序的时间复杂度较高,但对于小规模的数据排序还是比较高效的。
堆排序是一种基于二叉堆数据结构的排序算法。它的时间复杂度为O(nlogn),空间复杂度为O(1)。
堆排序的具体步骤如下:
堆排序适用于在多个元素中找出前几名的方案设计,因为堆排序是选择排序,而且选择出前几名的效率很高。
冒泡排序是一种简单直观的排序算法。它重复地遍历要排序的列表,通过比较相邻元素并交换它们,将列表中的最大元素逐渐“冒泡”到列表的末尾。在每一次遍历中,比较相邻的两个元素,如果它们的顺序不正确,则交换它们的位置。重复这个过程,直到整个列表排序完成。
具体算法步骤如下:
冒泡排序的时间复杂度为O(n^2),其中n是列表的长度。由于每次遍历都会将当前未排序部分的最大元素“冒泡”到末尾,因此需要遍历n次。每次遍历中需要比较相邻的元素并可能交换它们的位置,最坏情况下需要比较和交换(n-1)次,因此总的比较和交换次数为n*(n-1)/2,即O(n^2)。
冒泡排序是一种稳定的排序算法,即相等元素的相对位置在排序后不会改变。
快速排序是一种高效的排序算法,它基于分治的思想。
快速排序的基本思想是选择一个基准元素(通常选择数组的第一个元素),将数组分成两个子数组,使得左子数组的所有元素均小于基准元素,右子数组的所有元素均大于基准元素,然后对这两个子数组分别进行快速排序,最后将左子数组、基准元素和右子数组合并起来。
具体的实现步骤如下:
快速排序的时间复杂度为O(nlogn),其中n为数组的长度。
第一趟排序结束,得到2,11,15,20,9,5 23 56,45,35 然后对左右子数列进行同样的操作。
2 11,15,20,9,5 23 35,45 56
2 5,9 11 20,15 23 35 45 56
2 5 9 11 15 20 23 35 45 56
归并排序是一种分治算法,它将一个数组分成两个子数组,对每个子数组进行递归排序,然后将两个子数组合并为一个有序的数组。
具体步骤如下:
合并两个有序的子数组的步骤如下:
归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。它是一种稳定的排序算法,适用于处理大规模数据和外部排序。
对第三次归并,将52与28比较,28小,放入新表头,52再与33比较,33放入新表,52再与72比较,52放入新表,57再与72比较,57放入新表
基数排序是一种非比较型的排序算法,它按照元素的各个位的值来进行排序。基数排序可以用于整数或者字符串的排序。
基数排序的基本思想是:将待排序的元素分配到有限数量的桶中,然后按照桶的顺序依次取出元素构成有序序列。桶的数量一般和基数的范围有关。
具体的算法步骤如下:
基数排序的时间复杂度取决于数据的位数和数据范围,一般情况下为O(d*(n+r)),其中d是最大值的位数,n是元素个数,r是基数的范围。基数排序是一种稳定的排序算法。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。