Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7374085
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14605
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: C/C++

2011-12-05 22:29:24

作者:gfree.wind@gmail.com
博客:blog.focus-linux.net   linuxfocus.blog.chinaunix.net
 
 
本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
======================================================================================================

基于比较的排序算法,应该是最符合人们直觉的方法。在各种算法的技术书上,已经证明了基于比较的排序算法的时间最优复杂度为O(nlogn)。

下面是几种常见的基于比较的排序算法:

1. 选择排序:这应该是最直观的排序方法。在排序n个元素时,第一次遍历,找到最小的元素,将其与第一个元素互换;第二次遍历,找到次小的元素,将其与第二个元素交换;直至剩下最后一个元素。

2. 冒泡排序:这应该是我们学到的第一种排序算法。基本思想就是,通过依次比较相邻的两个元素,如后值比前值小,则交换这两个值,小值被交换到前面,大值被交换到后面。这样一次遍历后,最大值被放到最后。而小值被交换到n-1前。然后再次遍历前n-1,n-2,直至最后2个元素。整个儿过程,小值随着不断的遍历过程,逐渐被交换到前面,很像气泡逐渐从水底逐渐冒出。所以被称为冒泡算法。

3. 插入排序:这个算法的思想很直观。按照《算法导论》中的解释,这个算法可以参照我们平时打扑克的情形。当抓取一张牌的时候,按顺序比较手牌,将其插入到恰当的位置。这样保证了手中所有的牌依然有序。当已排序的值数量较多时,由于已经保证了有序,那么在确定新值插入位置的时候,可以通过二分查找的方法来去确定插入位置。

4. 希尔排序:在冒泡算法中,所以小值只能以步长为1的速度向前面移动。希尔排序在步长上作了优化,开始以一个较大的m步长进行分组,每组进行插入排序,这样就实现了步长为m的移动。然后逐渐缩小步长m直至1。所以根本思想是尽可能的将元素移动较远的位置代替移动一位。

5.归并排序:该思想利用的是解决问题的一个常用思想,divide-and-conquer,即分而治之的思想。将n个元素每次2分,变为两个n/2个元素组,直至1个元素——1个元素,自然是排好序了。然后,再两两合并元素组,最终合并为一个元素组。归并算法,因为需要归并,所以必然需要一个额外的n空间来实现归并。

6.快速排序:同样是分而治之的思想,将原始数据分为2组。但是与归并算法直接将原始数据分为两部分不同的是,快排选择一个中值,新的两个子组,一个子组所有的元素都小于中值,另外一个子组所有的元素都大于等于中值,直至元素个数为1。当元素个数为1时,实际上快排已经完成了排序。这点与归并排序也不同,快排在子组完成以后,无需额外的操作。很明显,快排的效率依赖于中值的选择。如果中值可以将数据分为两个数量相等的子组,那么效率则为最高的。快排无需额外的存储空间,可以in-place进行排序。

7.堆排序:该思想是将原始元素视为一个平衡二叉树。然后要求父节点必须大于子节点的规则,调整该平衡二叉树。由于是平衡二叉树,所以数据被完美的等分。这样根节点即为最大值。这时,堆排序完成了最大值的选择。为排序,则将根节点与最后一个子节点交换。此时,树的规则被破坏,需要从根节点逐级verify规则。



阅读(12048) | 评论(0) | 转发(5) |
给主人留下些什么吧!~~