leign

Contact: Email: leign.du@gmail.com MSN: dujiali1987@msn.cn
<2024年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

统计

  • 随笔 - 12
  • 文章 - 12
  • 评论 - 8
  • 引用 - 0

常用链接

留言簿

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

常用排序算法总结

 

 

1、冒泡排序

重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2、选择排序

每次找出最小/最大,确定一个位置

选择排序的交换操作介于0(n 1)次之间。选择排序的比较操作为n(n 1) / 2次之间。选择排序的赋值操作介于03(n 1)次之间。

比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2 交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

3、SHELL排序(分组插入)

也称为递减增量排序算法,是插入排序的一种高速而安定的改良版。

对有n个元素的可比较资料,先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

4、插入排序

在已有序列将元素逐个插入到适应的位置

缺点:需移动元素位置

改进:二分查找插入

5、快速排序

快速排序使用分治法Divide and conquer)策略来把一个序列(list)分为两个子序列sub-lists

步骤为:

Ø 从数列中挑出一个元素,称为 "基准"pivot),

Ø 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。

Ø 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

Ø 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

6、归并排序(分治法)

 

算法描述

Ø 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

Ø 设定两个指针,最初位置分别为两个已经排序序列的起始位置

Ø 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位

Ø 重复步骤3直到某一指针达到序列尾

Ø 将另一序列剩下的所有元素直接复制到合并序列尾

7、堆排序

选择排序的升级,减小比较次数,利用堆性质,每次找出最大和最小,交换位置后再次构造堆,直到排好序。

Ø 初始化操作:将R[1..n]构造为初始堆;

Ø 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)

Ø 重复

8、箱排序

箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0]R[1]R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)

分配过程的时间是O(n);收集过程的时间为O(m) (采用链表来存储输入的待排序记录)或O(m+n)。因此,箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n),则箱排序的时间是线性的,即O(n)

posted on 2009-10-15 14:32 leign 阅读(512) 评论(1)  编辑 收藏 引用

评论

# re: 常用排序算法总结 2011-09-23 20:14 90后非主流

但是这个算法总会结束,因为在每次的迭代www.zlss8.com
  回复  更多评论    

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理