常用排序算法原理简析

www.allocmem.com · · 407 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

前言

    本文只作一些概念性说明,后续会整理每种排序算法的具体实现。个人知识和能力有限,搜集整理和理解可能不到位,如有错误,欢迎指正

插入排序原理

图片来自维基百科 跑n-1趟,对于p=1到N-1趟,插入排序保证从位置0到位置p(数组也是从0开始计算)的数据是有序的,从后面每次拿一个数组往前面插,找到有序的位置(如此时51为被插入数,则在34到64之间)。需要使用两次for循环,时间复杂度为O(n^2)

希尔排序原理(缩减增量排序)

来自数据结构和算法分析第二版 简单粗暴 来自百度百科 http://note.youdao.com/yws/public/resource/5aec79159cf9ecb899c8e30052d4ac5b/xmlnote/WEBRESOURCE50284274774d52ac6216da18369535d3/2187 计算效率取决于选择的缩减增量序列,只要序列最后最小的为1,任何增量序列都是可行的。最坏时间复杂度为n^2,而使用2^k-1的Hibbard增量序列的最坏运行事件为N^1.5

堆(优先队列)排序原理

堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,小根堆相反(根可以理解为root),示例如下: 来自百度百科 利用堆本身的这种性质对数据进行排序,堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算,时间复杂度为O(nlogn)。

归并排序原理

迭代法如下: 递归法整体过程: 来自危机百科 合并两个已排序的表,三个指针比较大小后移动到新的空白数组中 最坏运行时间复杂度为O(nlogn),所使用的比较次数几乎是最优的,充分利用递归。

快速排序原理

来自数据结构和算法分析第二版 来自维基百科 来自百度百科 平均运行时间O(nlogn),最坏为O(n^2),最坏情况极难出现,其中的枢纽源选取最好使用随机的方式,或者使用中值(一般都使用这种),个人理解,和归并排序,归并最小的度是两个排序,而快排因为递归到最后一个,有一个中间值,一个左值,一个右值,所以是三个值。

冒泡排序原理

冒泡排序算法的运作如下: 1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 3. 针对所有的元素重复以上的步骤,除了最后一个。 4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 平均时间复杂度 O(n^2),当都有序的时候的复杂度为O(n)

选择排序

它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 时间复杂度 О(n²)

参考

  1. 《数据结构和算法分析–java语言描述第二版》
  2. https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
  3. http://baike.baidu.com/link?url=o5dfsnCX1oJg6Oms-5Sc7Wor25VhXWF_PUF5OI0rhQkv6MOVCGCa7b7zfO_RhIe2YFXjwpaBNyjiJ1Sz15DkzcjAqHIax5qOCxsVqJJNjiG5Cwbj8fSvF6daUBnXg4XP

本文来自:www.allocmem.com

感谢作者:www.allocmem.com

查看原文:常用排序算法原理简析

407 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传