文档章节

八种排序算法的时间复杂度复杂度

 陈刚生
发布于 09/21 15:18
字数 1250
阅读 18
收藏 0

1、稳定性 归并排序、冒泡排序、插入排序。基数排序是稳定的 选择排序、快速排序、希尔排序、堆排序是不稳定的   2、时间复杂度 最基础的四个算法:冒泡、选择、插入、快排中,快排的时间复杂度最小O(n*log2n),其他都是O(n2) 排序法 平均时间 最差情形 稳定度 额外空间 备注 冒泡 O(n2)     O(n2) 稳定 O(1) n小时较好 选择 O(n2) O(n2) 不稳定 O(1) n小时较好 插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好 基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9), R是基数(个十百) Shell O(nlogn) O(ns) 1 a[center_index]。如果i和j都走不动了,i j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。 (5)归并排序     归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。 (6)基数排序    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。 (7)希尔排序(shell)     希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。 (8)堆排序    我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法 ---------------------

https://weavi.com/10845159
https://weavi.com/10862512
https://weavi.com/10862510
https://weavi.com/10862509

本文来自 q2213065359 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/q2213065359/article/details/82801717?utm_source=copy

© 著作权归作者所有

共有 人打赏支持
粉丝 3
博文 18
码字总数 26607
作品 0
菜鸟学习历程【15-1】直接插入排序

排序就是按照递增或者递减的次序整理文件中的记录。 排序分为稳定排序和不稳定排序,什么是稳定,什么又是不稳定? 例如:3 15 8 8 6 9 在上述6个数字中的排序过程中,如果将两个8的位置交换...

leessang_bo
2017/12/02
0
0
深度剖析八大经典排序算法—C++实现(通俗易懂版)

内容会持续更新,有错误的地方欢迎指正,谢谢! 引言 该博客的示例代码均以递增排序为目的~ 学习建议:切忌看示例代码去理解算法,而是理解算法原理写出代码,否则会很快就会忘记。 算法分类 ...

billcyj
2017/11/06
0
0
前端 排序算法总结

前言 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较你和一个连快排都不会写的人的时候,...

zimo
2017/09/21
0
0
[译] 排序算法入门 — Go 语言实现

[译] 排序算法入门 — Go 语言实现 Go语言学习园地博客2017-07-0915 阅读 go算法排序 排序算法是一种采用列表或数组并以特定顺序对其元素进行重新排序的算法。有几十种不同的排序算法,如果你...

Go语言学习园地博客
2017/07/09
0
0
八种排序算法原理及Java实现-收藏起来面试必备

排序算法分为内部排序和外部排序,内部排序把数据记录放在内存中进行排序,而外部排序因排序的数据量大,内存不能一次容纳全部的排序记录,所以在排序过程中需要访问外存。 经常提及的八大排...

小刀爱编程
10/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

区块链教程以太坊源码分析core-state源码分析(一)

兄弟连区块链教程以太坊源码分析core-state源码分析,core/state 包主要为以太坊的state trie提供了一层缓存层(cache) database主要提供了trie树的抽象,提供trie树的缓存和合约代码长度的缓...

兄弟连区块链入门教程
25分钟前
0
0
使用putty上传文件

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: :: 使用putty上传文件 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: ::linux 用户名 set linux_us......

shzwork
26分钟前
1
0
摹客首家发布Adobe XD插件

10月19日,摹客iDoc发布了支持Adobe XD的插件,这是中国国内首款基于Adobe XD 正式API的插件。 设计师在Adobe XD 中安装并使用此插件,可以将设计稿上传到摹客iDoc,并使用iDoc的全部协作设计...

mo311
26分钟前
0
0
MetInfo最新网站漏洞如何修复以及网站安全防护

metinfo漏洞于2018年10月20号被爆出存在sql注入漏洞,可以直接拿到网站管理员的权限,网站漏洞影响范围较广,包括目前最新的metinfo版本都会受到该漏洞的攻击,该metinfo漏洞产生的主要原因是...

网站安全
27分钟前
0
0
git统计代码行数

$ npm install -g cloc$ cloc . 2193 text files. 1533 unique files. 760 files ignored.github.com/AlDanial/cloc v 1.78 ......

moon888
27分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部