文档章节

常见排序算法

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
粉丝 1
博文 55
码字总数 11354
作品 0
海淀
程序员
PHP常见排序算法学习

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

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

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

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

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

u011415782
2017/10/24
0
0
Java实现几种常见排序方法(下)

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。 /** 插入排序<br/> <ul> <li>从第一个元素开始,该元...

晨曦之光
2012/03/09
0
0
常见排序算法的稳定性分析和结论

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

长平狐
2013/01/06
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
27分钟前
1
0
php foreach

<?php// 数组的引用$a=array(1,2,3,4,5);foreach($a as $key=>&$value){$value=$value*2;}print_r($a);echo " $key -------------------$value\r\n";/** * ...

小张525
35分钟前
1
0
12-利用思维导图梳理JavaSE-多线程

12-利用思维导图梳理JavaSE-多线程 主要内容 1.线程概念 2.线程开发 3.线程的状态 4.线程的同步和死锁 5.Java5.0并发库类 QQ/知识星球/个人WeChat/公众号二维码 本文为原创文章,如果对你有一...

飞鱼说编程
58分钟前
0
0
JAVA集合之ArrayList

一、前言 Java 集合类提供了一套设计良好的支持对一组对象进行操作的接口和类,JAVA常用的集合接口有4类,分别是: Collection:代表一组对象,每一个对象都是它的子元素 Set:不包含重复元素...

木木匠
今天
3
0
转:XMLHttpRequest2 新技巧

”XMLHttpRequest 的异步调用网上找的例子运行没问题,但稍微改了一点点就报错”InvalidStateError: XMLHttpRequest has an invalid context“。断断续续 搞了3天终于通了,可以接收二进制文...

SamXIAO
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部