文档章节

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

 陈刚生
发布于 09/21 15:18
字数 1250
阅读 30
收藏 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

© 著作权归作者所有

共有 人打赏支持
粉丝 4
博文 25
码字总数 38557
作品 0
私信 提问
深度剖析八大经典排序算法—C++实现(通俗易懂版)

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

billcyj
2017/11/06
0
0
菜鸟学习历程【15-1】直接插入排序

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

leessang_bo
2017/12/02
0
0
八大排序算法-概要

常见的算法大概有8种,是我们需要掌握的。这些排序又可以分为排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,...

驛路梨花醉美
2016/06/20
8
0
[译] 排序算法入门 — Go 语言实现

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

Go语言学习园地博客
2017/07/09
0
0
前端 排序算法总结

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

zimo
2017/09/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring boot中如何获取profiles环境

  实现ApplicationContextAware @Componentpublic class QiNiuPropertiesConfig implements ApplicationContextAware { /// 获取当前环境public String getActiveProfile() { ret......

writeademo
5分钟前
0
0
机器学习中的End-to-End到底是怎么回事?

简单讲就是,Input--->系统(这里指神经网络)--->Output(直接给出输入,NN神经网络就给出结果,一气喝成!!!) 借用一段对话:(http://dy.163.com/v2/article/detail/C3J6F2NJ0511AQHO....

火力全開
6分钟前
0
0
maven多个模块只编译并且只打包指定的模块

在多module的maven项目中,如果每次打包整个工程显得有些冗余和笨重。 命令:mvn clean package install -pl 模块的名称 -am

lifes77
7分钟前
0
0
eosjs中文手册【2.0】

访问地址:eosjs 2.0 中文手册 - 汇智网

汇智网教程
12分钟前
0
0
vue-cli 3 分环境打包

在vue-cli3的项目中, npm run serve时会把process.env.NODE_ENV设置为‘development’; npm run build 时会把process.env.NODE_ENV设置为‘production’; 此时只要根据process.env.NODE_...

灰白发
19分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部