随笔-80  评论-22  文章-0  trackbacks-0

实际应用中最常用的排序是快速排序和堆排序。所谓堆排序,就是将最小的一个值放到堆栈的顶部,这样就可以使最后出来的数完成排序。快速排序是不稳定的,堆排序是稳定的。所谓稳定,就是当两个值相等时,排序后两个值的顺序和排序前相同。以上两种排序使用的范围和情况是不同的,一般对于自然生成序列排序使用快速排序效率比较高,而对于已经有一定顺序的序列,使用堆排序比较合适,而且稳定的。

这里主要总结常用的5种排序,分别是快速排序,冒泡排序(也叫交换排序),选择排序,shell排序,插入排序。

下边分别介绍:

1快速排序,就是从一个序列中随意取一个数,然后对剩下的数进行分类,小的放到左边,大的放到右边。如此进行下去知道最后。N(n-1)/2.空间复杂度是o(n).

2冒泡排序,就是从第一个数开始和后一个数比较,然后依情况交换,然后再用第二个和第三个比较交换,如此反复,直到最后一个。一直进行n轮就可以完成排序。

3选择排序,就是将一个序列中的最小的放到第一个,然后再将剩下的数据用相同的方式分别放到后一位。它的空间复杂度是O(1).

4shell排序,就是将有一定间隔的数进行排序,并且间隔变小,也就是开始是n/2,然后继续变小,一般都是以一半为标准,直到最后间隔只有1,也就完成了排序。需要的空间复杂度是O(1).

5插入排序,就比如平时玩的扑克排,一般整理排的时候需要将排排序,当你拿到一张新排的时候,就要比较左边和右边,只有在左右中间的那个值的时候才说明排序成功。它需要的空间复杂度也是O(1).

Ps:空间复杂度就是需要另外占用的空间。

以上排序中,只有快速排序是O(n),其他都是O(1),因为只有快速排序需要另外再起存储空间,而其他都是在原来空间中增加一个空间就可以。

posted on 2009-07-18 20:53 Bluesea 阅读(282) 评论(0)  编辑 收藏 引用 所属分类: C/C++

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理