文档章节

常见排序算法

robinfly
 robinfly
发布于 2017/07/23 19:23
字数 286
阅读 13
收藏 0

冒泡排序

  • 时间复杂度 : 最差 O(n^2)、平均O(n^2)
  • 空间复杂度:最佳0、最差O(n)、平均O(1)
  • 稳定

快速排序

  • 时间复杂度:最差O(n^2)、平均O(n*log2n)
  • 空间复杂度:最差 O(n) 冒泡情况、最优O(n logn)
  • 不稳定:例如,a = [1, 2, 2, 3, 5]以 a[2]为基准,大于等于a[2]的排右边,则a[1]与a[2]的相对位置发生变化,使其不稳定。

桶排序

基本思想

  1. 把大量数据切分成基本有序的数据块(桶),
  2. 对桶中的数据作比较排序

基数排序

基本思想:将待排数据中的每组关键字进行桶排序

计数排序

基本思想:对每一个元素记录它出现的次数,就能确定一个数所处位置,

性能比较

  1. 基数排序时间复杂度是O(d*n),桶排序O(n)
  2. 基数排序不做任何比较,需要的桶不多(10个);桶排则可能会做比较、桶也可能也会比较多
  3. 未完......

参考

© 著作权归作者所有

共有 人打赏支持
robinfly
粉丝 2
博文 55
码字总数 11354
作品 0
海淀
程序员
私信 提问
PHP常见排序算法学习

题记: 常见的排序算法有:冒泡排序法,快速排序法,选择排序法,插入排序法,此处作为自己最近面试准备进行的学习笔记,同时也希望能帮到你。 需求:将一个有多个数字的数组进行从小到大的排...

moTzxx
2017/10/27
0
0
[仅供个人参考系列]个人整理基础的排序、查找等算法相关笔记

1.常见排序算法的时间、空间复杂度 2.具体算法的实现 快速排序(根据定位pivot元素的方法,分为简单版和技巧版) 简单版: 复杂版:(请参考剑指offer上79页的相关写法) 直接插入算法: 堆排...

jayxujia123
2018/03/28
0
0
PHP常见排序算法整理学习

题记: 常见的排序算法有:冒泡排序法,快速排序法,选择排序法,插入排序法,此处作为自己最近面试准备进行的学习笔记,同时也希望能帮到你。 需求:将一个有多个数字的数组进行从小到大的排...

u011415782
2017/10/24
0
0
常见排序算法的稳定性分析和结论

常见排序算法的稳定性分析和结论 这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然...

长平狐
2013/01/06
1K
0
常见排序算法 4--简单选择排序

简单排序算法的时间复杂度为n2空间负责度为1 下面上代码。 select——sort.h ///* 简单的选择排序通过n-1次比较,在n-i +1个元素中,找到最小的记录,然后将其与第i个元素交换这样当i=n时,即...

qmiwang
2012/04/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

精读《论语》读后感作文3600字

精读《论语》读后感作文3600字: 学而篇第一:子曰:“学而时习之,不亦说乎?有朋友自远方来,不亦悦乎?人不知,而不愠,不亦君子乎? 朱熹解:即学而又时时习之,则学者熟,而衷心喜悦,其...

原创小博客
28分钟前
0
0
CPU内存结构

开局一张图 由于CPU频率太快了,为解决直接读取内存的数据上的延迟,在CPU和内存之间,存在3级缓存。 CPU在解决和缓存不一致上采用两种方式: 缓存一致性协议 总线锁机制 CPU CPU的一个时钟周...

春哥大魔王的博客
31分钟前
1
0
记一次centos 7内核升级事故

情景 公司做等保3测评,在进行系统漏洞检测时发现内核存在漏洞,需要进行升级。 名称 版本 升级前内核 CentOS Linux (3.10.0-327.el7.x86_64) 7 (Core) 升级后内核 CentOS Linux (3.10.0-957...

阿dai
56分钟前
8
0
PowerDesigner操作

1.去掉生成DDL里的注释 Database -> Edit Current DBMS -> Script -> Syntax -> BlockComment,去掉BlockComment里面的value内容。...

了凡川
今天
3
0
Django集成Markdown编辑器【附源码】

专注内容写作的你一定不要错过markdown 简单介绍 markdown是一种标记语言,通过简单的标记语法可以使普通的文本内容具有一定的格式,使用非常简单,学习成本极低 目前各大Blog平台都已支持m...

运维咖啡吧
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部