文档章节

常见排序算法

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
常见排序算法的稳定性分析和结论

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

长平狐
2013/01/06
1K
0
Java实现几种常见排序方法(下)

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

晨曦之光
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

new Date() 在Safari下的 Invalid Date问题

问题复现 var timeStr = '2018-11-11 00:00:00';var time = new Date(timeStr);// error: Invalid Date... 在safari浏览器下,time为Invalid Date, 导致后面代码执行错误; 其他浏览器诸...

会写代码的husky
12分钟前
1
0
0009-如何升级Cloudera Manager和CDH

1.文档编写目的 本文档讲述如何升级Cloudera Manager和CDH,通过本文档,您将学习到以下知识: 1.如何对Cloudera Manager进行停机升级 2.如何对CDH进行停机升级 3.如何在不影响集群作业的情况...

Hadoop实操
22分钟前
0
0
vue2中引用 better-scroll的方法

文章主要介绍了vue2中引用better-scroll和使用 better-scroll的方法,使用时有三个要点及注意事项在文中给大家详细介绍 ,需要的朋友可以参考下 使用时有三个要点: 一:html部分 <div class...

前端攻城老湿
32分钟前
0
0
浅谈教你如何掌握Linux系统

linux能做什么?相信绝大数人都有这样的疑问。可以玩吃鸡吗?可以玩lol吗? 如果你是以娱乐的名义来评价linux的可用性,对不起,linux可能不适合你,因为linux是一个工具,他是教你聪明的,不...

linuxprobe16
38分钟前
0
0
java中线程池的生命周期

线程池生命周期包括: RUNNING:接收新的任务并处理队列中的任务 SHUTDOWN:不接收新的任务,但是处理队列中的任务 STOP:不接收新的任务,不处理队列中的任务,同时中断处理中的任务 TIDYING:所...

小刀爱编程
46分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部