依旧的博客

技术学习

C++博客 首页 新随笔 联系 聚合 管理
  17 Posts :: 1 Stories :: 2 Comments :: 0 Trackbacks
如果有一个随机排列的整数表,怎样将它排序呢?这是生活中也经常碰到的问题。比如给一组牌排序,我们通常会怎样做呢?

不断从原序列中取出元素来排成一个新序列,在新序列形成的时候保证它有序,这就是插入排序的办法。插入排序需要有空间存放和操作新序列,这可以在原序列的空间中满足。插入排序需要大量的比较和移动,量级是O(n*n)。我们也可以每次从现有元素中取出最小元素,这样新序列排下来自然是有序的,这就是选择排序的办法。选择排序需要O(n*n)的比较,最坏最好情况下都一样。这是一个缺点,和与之对称的插入排序比较,选择排序对原序列的情况缺乏适应性,冒泡排序是对此的改进。冒泡排序也基本使用原序列的空间,每次在现有元素中进行比较以寻找最小元素,并通过交换逐步把它移到相应位置。冒泡排序在原序列的基础上逐步调整得到新序列,它可以更加适应原序列的情况,在最好情况下时间为O(n)。这三种排序是最基本的,其它方法都是从各种角度对它们进行改进。

三种基本排序都着眼于从原序列形成新序列的过程。这是最基本的,但还可以把整个过程用分治或渐进的思想来处理。具体的改进方法有多种,希尔排序,快速排序,归并排序等等,我们现在可以欣赏它们的思想,但是当初每种方法的发现都是重要的成果,需要对排序问题有扎实的认识,也需要创造的灵感。

希尔排序把原序列分组,每一组进行插入排序,从较小的分组开始逐渐扩大,直到整个序列作为一组。分组元素是间隔选取的,较小的分组排序完成后,整个序列就在一个较大的尺度上有序了,随着分组的扩大,序列在越来越小的尺度上有序,直到完全有序。希尔排序利用插入排序对乐观情况的适应性,自顶向下渐进处理,避免了直接在小尺度上进行处理的盲目性。

归并排序反映出一种自底向上的分治思想,其时间为O(n*log(n))。

快速排序采用了自顶向下的分治思想,其做法和归并排序有某种对称性。

基数排序也是自顶向下的分治思想,它从关键字本身衡量问题的解决程度。


posted on 2006-05-03 17:40 依旧的博客 阅读(411) 评论(0)  编辑 收藏 引用 所属分类: 编程

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