存档

文章标签 ‘排序算法’

算法系列之 计数排序

2013年11月12日 没有评论

计数排序

之前讲的各种排序算法:插入排序、选择排序、冒泡排序、归并排序、快速排序、堆排序和希尔排序等,这些排序算法复杂度都不是线性的。
有没有可能找到一种线性的排序算法? 答案是肯定的。只要我们不比较,不交换元素,而在扫描到元素的时候,就能确定此元素在有序序列中的位置,就可以达到线性算法复杂度。这种排序叫计数排序。
它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。
阅读全文…

分类: 算法 标签:

算法系列之 希尔排序

2013年11月12日 没有评论

希尔排序

希尔排序是一种分组插入排序,是插入排序的一种更高效的改进版本.
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
  •      插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  •      但插入排序一般来说是低效的, 因为插入排序每次都只能将数据移动一位

阅读全文…

分类: 算法 标签:

算法系列之 堆排序

2013年11月11日 没有评论

二叉堆的性质

  1. 二叉堆是一颗完全二叉树,最后一层的叶子从左到右排列,其它的每一层都是满的
  2. 最小堆父结点小于等于其每一个子结点的键值,最大堆则相反
  3. 每个结点的左子树或者右子树都是一个二叉堆

阅读全文…

分类: 算法 标签:

算法系列之 快速排序优化

2013年11月8日 没有评论

继上篇说了快速排序的实现原理:通过选择左边第一个数为轴值,分区让轴值左边的数都小于等于轴值并且右边都大于轴值,返回轴值并对左序列跟右序列进行递归处理

如果要排序的序列是基本有序的,这时选择左边第一个数为轴值,递归都只是对右边序列进行递归,会导致快速排序算法时间复杂度为N*N。 阅读全文…

分类: 算法 标签:

算法系列之五 快速排序

2013年11月8日 没有评论

快速排序的基本思想是:

1、选择轴值:pivot
2、分割,并返回轴值位置:将序列划分为两个子序列L和R,使得L中所有记录都小于或等于轴值,R中记录都大于轴值
3、递归处理:对子序列L和R递归进行快速排序 阅读全文…
分类: 算法 标签:

算法系列之四 归并排序

2013年11月3日 没有评论

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
阅读全文…

分类: 算法 标签:

算法系列之三 冒泡排序

2013年10月29日 没有评论

冒泡排序是从待排序的序列中,比较相邻的前后二个数据,如前面元素值大于后面元素值则交换位置,第1趟下来最大的元素就沉在数组的第n-1的位置,起到全部待排序的元素处理完 阅读全文…

分类: 算法 标签:

算法系列之二 插入排序

2013年10月28日 没有评论

插入排序是通过不断扩大排序序列的长度来实现的,对于每一个待排序的元素,按其关键字大小插入到前面已经排好序的子序列中的适当位置,形成更长的有序子序列。
当每一个待排序的元素都这样子被循环迭代处理后,排序完成。
阅读全文…

分类: 算法 标签: