[Arch] Java数据结构与算法 - 简单排序

博客首页 » Arch Java数据结构与算法 - 简单排序

发布于 19 Jul 2015 23:30
标签 blog
对于有序的数据,可以通过二分法之类的方式,极大地提高效率。简单的排序算法有冒泡、选择、插入。

冒泡排序(Bubble Sort)

如水中冒泡一样,两个循环,外循环依次指定每一个元素,内循环重复比较大小,交换相邻的元素。

(N-1)+(N-2)+…+1=N*(N-1)/2

  • 比较次数 N^2/2 (当N»1时,忽略1)
  • 交换次数 N^2/4 (若数据完全随机)
  • 算法效率 O(N^2)

基本判断方法,内外嵌套循环,则O(N^2)的可能性大。因为外循环N次,内循环N次或几分之N次。

奇偶排序:对奇数和偶数分别使用冒泡,可以在多处理器中并行。

选择排序(Select Sort)

选择最小的,排在一端,再在剩下的元素中选择最小的,排在其次,直至选择完所有元素。

  • 比较次数 N^2/2
  • 交换次数 N/2 (若数据完全随机)
  • 算法效率 O(N^2)

因为当N很大时,比较次数占主要因素。当然如果交换时间比比较时间大很多,选择比冒泡还是有优势的。

插入排序(Insert Sort)

局部有序:保持一个排好顺序的局部
被标记队员:以特定队员为标记,左侧是排序的,右侧是未排序的
通过把每一个队员,插入到有序队列中,只移动队列中的一部分队员,腾出空位。

  • 比较次数 N^2/2/2 因为有序,所以比较次数再除2
  • 复制次数 大致等于比较次数(比交换要高效)
  • 算法效率 O(N^2),如果数据已经有序,则只需要 O(N)

稳定性

当排序时,有一部分元素的值是相同的,对于这部分如果排序后,依然是原来顺序,没有改变,则这个算法是稳定的。例:按身高排序后,再按省排序,排序后,省内依然是身高顺序。

总结比较

三个算法都可以就地不需要额外存储空间,其中,插入排序较快。大量排序,快速排序算法更好。


本页面的文字允许在知识共享 署名-相同方式共享 3.0协议和GNU自由文档许可证下修改和再使用,仅有一个特殊要求,请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。


系列文章

文章列表

  • Arch Java数据结构与算法 - 简单排序

这篇文章对你有帮助吗,投个票吧?

rating: 0+x

留下你的评论

Add a New Comment