请你说一说你知道的排序算法及其复杂度
-
参考回答:
1、冒泡排序:
从数组中第一个数开始,依次遍历数组中的每一个数,通过相邻比较交换,每一轮循环下来找出剩余未排序数的中的最大数并“冒泡”至数列的顶端。
稳定性:稳定
平均时间复杂度:O(n ^ 2)
2、插入排序:
从待排序的n个记录中的第二个记录开始,依次与前面的记录比较并寻找插入的位置,每次外循环结束后,将当前的数插入到合适的位置。
稳定性:稳定
平均时间复杂度:O(n ^ 2)
3、希尔排序(缩小增量排序):
希尔排序法是对相邻指定距离(称为增量)的元素进行比较,并不断把增量缩小至1,完成排序。
希尔排序开始时增量较大,分组较多,每组的记录数目较少,故在各组内采用直接插入排序较快,后来增量di逐渐缩小,分组数减少,各组的记录数增多,但由于已经按di−1分组排序,文件叫接近于有序状态,所以新的一趟排序过程较快。因此希尔 排序在效率上比直接插入排序有较大的改进。
在直接插入排序的基础上,将直接插入排序中的1全部改变成增量d即可,因为希尔排序最后一轮的增量d就为1。
稳定性:不稳定
平均时间复杂度:希尔排序算法的时间复杂度分析比较复杂,实际所需的时间取决于各次排序时增量的个数和增量的取值。时间复杂度在O(n ^ 1.3)到O(n ^ 2)之间。
4、选择排序:
从所有记录中选出最小的一个数据元素与第一个位置的记录交换;然后在剩下的记录当中再找最小的与第二个位置的记录交换,循环到只剩下最后一个数据元素为止。
稳定性:不稳定
平均时间复杂度:O(n ^ 2)
5、快速排序
1)从待排序的n个记录中任意选取一个记录(通常选取第一个记录)为分区标准;
2)把所有小于该排序列的记录移动到左边,把所有大于该排序码的记录移动到右边,中间放所选记录,称之为第一趟排序;
3)然后对前后两个子序列分别重复上述过程,直到所有记录都排好序。
稳定性:不稳定
平均时间复杂度:O(nlogn)
6、堆排序:
堆:
1、完全二叉树或者是近似完全二叉树。
2、大顶堆:父节点不小于子节点键值,小顶堆:父节点不大于子节点键值。左右孩子没有大小的顺序。
堆排序在选择排序的基础上提出的,步骤:
1、建立堆
2、删除堆顶元素,同时交换堆顶元素和最后一个元素,再重新调整堆结构,直至全部删除堆中元素。
稳定性:不稳定
平均时间复杂度:O(nlogn)
7、归并排序:
采用分治思想,现将序列分为一个个子序列,对子序列进行排序合并,直至整个序列有序。
稳定性:稳定
平均时间复杂度:O(nlogn)
8、计数排序:
思想:如果比元素x小的元素个数有n个,则元素x排序后位置为n+1。
步骤:
1)找出待排序的数组中最大的元素;
2)统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
3)对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
4)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
稳定性:稳定
时间复杂度:O(n+k),k是待排序数的范围。
9、桶排序:
步骤:
1)设置一个定量的数组当作空桶子; 常见的排序算法及其复杂度:
2)寻访序列,并且把记录一个一个放到对应的桶子去;
3)对每个不是空的桶子进行排序。
4)从不是空的桶子里把项目再放回原来的序列中。
时间复杂度:O(n+C) ,C为桶内排序时间。
-
请你来介绍一下各种排序算法及时间复杂度
2020-01-30 关注 0 浏览591 1答案
-
你知道哪些排序算法,这些算法的时间复杂度分别是多少,解释一下快排?
2020-01-28 关注 0 浏览659 1答案
-
你最熟悉什么算法?给我说一下原理或者排序过程?它的优缺点是什么?你知道什么排序算法,介绍他们的实现方法,时间复杂度和空间复杂度,是否稳定,快排基准点怎么选择,
2020-01-27 关注 0 浏览1265 1答案
-
请你说一说洗牌算法?
2020-01-30 关注 0 浏览550 1答案
-
请你说一说你知道的自动化测试框架
2020-01-26 关注 0 浏览608 1答案
-
下列排序算法空间复杂度最小的是:
2022-03-03 关注 0 浏览29 1答案
-
下列空间复杂度最高的排序算法是:()
2022-03-03 关注 0 浏览21 1答案
-
下列哪种排序算法的最坏时间复杂度与平均时间复杂度不同?
2022-03-03 关注 0 浏览38 1答案
-
以下哪种排序算法平均时间复杂度最低()
2022-03-03 关注 0 浏览49 1答案
-
下列排序算法中,平均时间复杂度为O(n^2)的排序算法有哪些
2022-03-02 关注 0 浏览105 1答案