技术控

    今日:126| 主题:49289
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 深入浅出交换类排序算法(冒泡排序,快速排序)

[复制链接]
旧瘾 发表于 2016-10-3 15:31:32
185 6

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1) 冒泡排序

   冒泡排序在众多排序算法中算比较简单的一个, 基本思想是, 重复的进行整个数列的排序, 一次比较两个元素( 两两排序 ),如果它们顺序不符合就交换, 重复这样直到数列没有再需要交换的数为止(结束条件) .就好像气泡一样, 轻的气泡会往上漂浮,在不断漂浮的过程中,发生了两两交换过程, 所以叫冒泡排序.
   
深入浅出交换类排序算法(冒泡排序,快速排序)-1 (最大的,漂浮,元素)

  其实也可以用生活中的例子理解, 就比如: 在军训排队时, 按个子高的和个子矮的的顺序进行排列, 个子高的和个子矮的会进行两两进行比较.
  我们来大致看下算法的流程:
   选一组序列 4, 3 , 5, 6, 2, 1 (极端情况)
  从头开始进行冒泡排序,1号和2号进行交换,  4 > 3, 所以需要进行交换:
  ->3, 4, 5, 6, 2, 1

   2号和3号进行交换, 4<5 , 不交换
  -> 3, 4, 5, 6, 2, 1

   3号和4号进行交换, 5<6 , 不交换
  -> 3, 4, 5, 6, 2, 1

   4号和5号进行交换, 6>2 ,交换
  ->3, 4, 5, 2, 6, 1

   5号和6号进行交换, 6>1 ,交换
  ->3, 4, 5, 2, 1, 6

  第一轮冒泡排序结束, 把最大的数交换到最后一位, 如此循环, 直到没有需要交换的元素为止! 冒泡排序才结束.
  代码实现如下:
  [code]void BubbletSort(int*a,int len) {
    int m;
    for (bool bSwap=true; bSwap; len--) {
        bSwap = false;
        for (int j=1;j             if (a[j-1]>a[j]) {   //交换值
                m=a[j];
                a[j]=a[j-1];
                a[j-1]=m;
                bSwap=true;
            }
        }
    }
}[/code]  其实冒泡排序整体看来是非常"傻"的, 有很多可以优化的余地, 比方说,每次比较如果发现较小的元素在后面,就交换两个相邻的元素,而如果我只扫描元素, 记下最小元素, 等一次扫描完后, 再交换两者为止, 这样最小元素就排到了前面, 每扫描一次,只需要一次真正的交换, 而刚才的冒泡可能需要交换多次, 刚才说的算法优化其实就是选择排序, 以后我会细说, 他属于选择排序的范畴.
  我们来考虑下冒泡算法的复杂度:

   在时间复杂度上, 若待排序的序列为完全逆序, 则每次都需要进行元素之间的交换, 所以时间复杂度为O(
深入浅出交换类排序算法(冒泡排序,快速排序)-2 (最大的,漂浮,元素) n^2),若待排序为顺序, 也就是不需要交换元素, 但是需要扫描,所以还是需要O(
友荐云推荐




上一篇:Trace - adds logging and metrics to net trace
下一篇:PHP 7 deployment at Dailymotion
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

efyh5yCf 发表于 2016-10-7 03:47:00
向楼主学习
回复 支持 反对

使用道具 举报

xymeleax 发表于 2016-10-14 20:00:07
只想优雅转身,不料华丽撞墙。
回复 支持 反对

使用道具 举报

youbowen 发表于 2016-11-1 06:44:56
介是神马?!!
回复 支持 反对

使用道具 举报

zkkxgy00 发表于 2016-11-3 08:05:52
世界末日我都挺过去了,看到旧瘾我才知道为什么上帝留我到现在!
回复 支持 反对

使用道具 举报

董逍 发表于 2016-11-11 18:58:13
楼猪V5啊
回复 支持 反对

使用道具 举报

代双 发表于 2016-11-18 01:26:22
为毛老子总也抢不到沙发?!!
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表