请选择 进入手机版 | 继续访问电脑版

技术控

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

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

[复制链接]
旧瘾 发表于 2016年10月3日 15:31
315 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

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

   在时间复杂度上, 若待排序的序列为完全逆序, 则每次都需要进行元素之间的交换, 所以时间复杂度为O( 深入浅出交换类排序算法(冒泡排序,快速排序)-2-技术控-最大的,漂浮,元素 n^2),若待排序为顺序, 也就是不需要交换元素, 但是需要扫描,所以还是需要O( 深入浅出交换类排序算法(冒泡排序,快速排序)-3-技术控-最大的,漂浮,元素 n)的时间复杂度, 平均情况下时间复杂度为O( 深入浅出交换类排序算法(冒泡排序,快速排序)-4-技术控-最大的,漂浮,元素 n^2) .
   在空间复杂度上, 需要辅助空间只有一个m(如上面代码), 所以空间复杂度为O(1).
  2) 快速排序

   如果大家还记得折半插入排序的过程:在一个有序序列中,插入关键字和折半序列的中间关键字进行比较, 若小则在关键字左边,若大则在关键字右边,而快速排序和折半插入排序有异曲同工之妙, 差别在于折半插入排序插入的序列自身是个有序序列, 选取中间关键字时 两边已经有序. 而快速排序在于它不一定是有序的,它的操作过程是:随便选取一个关键字(一般选取第一个), 让所有关键字和它进行比较一次,小的放在左边, 大的放在它右边.然后递归地对左边和右边进行排序。把该区间内的所有数依次与关键字比较,我们就可以在线性的时间里完成分割的操作。
  我们来看下算法的步骤:

   初始状态:【49,38,65,97,76,13,27,49'】
   一次划分后:【27,38,13】 49 【76,97,65,49'】
   分别进行快速排序:【13】 27 【38】 【49',65】76【97】
   有序序列:【13,27,38,49,49',65,76,97】
  上面是算法的大致步骤,一般完成分割操作有很多有技巧性的实现方法,比如最常用的一种是定义两个指针,一个从前往后找找到比关键字大
  的,一个从后往前找到比关键字小的,然后两个指针对应的元素交换位置并继续移动指针重复刚才的过程。这只是大致的方法,具体的实现还
  有很多细节问题。
  我们来看一下一轮快排序的细节步骤:
  原始序列(i和j分别指向序列的最低和最高位置):
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-5-技术控-最大的,漂浮,元素

  选取第一个数49作为比较排序关键字.
  1.使用j,从序列最右端开始扫描遇到比49小的则停止.
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-6-技术控-最大的,漂浮,元素

  2.将27交换到i的位置
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-7-技术控-最大的,漂浮,元素

  3.使用i,从序列最左端开始扫描遇到比49大的数则停止
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-8-技术控-最大的,漂浮,元素

  4.将65交换到j的位置
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-9-技术控-最大的,漂浮,元素

  5.再使用j向前扫描遇到比49小的13停止,并把13交换到i位置.
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-10-技术控-最大的,漂浮,元素

  6.使用i向后扫描遇到比49大的97停止 并交换到j的位置
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-11-技术控-最大的,漂浮,元素

   7.继续使用j向前扫描遇到比49小的并停止,这时发现i和j相遇,代表扫描结束 .
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-12-技术控-最大的,漂浮,元素

  8.最后把49放置在ij的位置:
   

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

深入浅出交换类排序算法(冒泡排序,快速排序)-13-技术控-最大的,漂浮,元素

   从上面的一轮快排可以看出, 49把整个序列划分为两个部分, 小于49的在它左边, 大于49的在它右边. 根据算法思想再分别把49两边的序列进行快排一次. 另外从整个排序过程来看, 先对整个序列进行一次快排, 然后再对其中子序列再进行快排, 如此反复直到有序为止. 整个过程是个递归的思想.所以代码比较好写. 我们来实现一下.
  1. //head=>序列的开头
  2. //tail=>序列的结尾
  3. void quickSort(int array[], int head, int tail) {

  4.     if (head > tail) {
  5.       return;
  6.     }

  7.     //i,j指向头和尾巴
  8.     int i=head;
  9.     int j=tail;
  10.     int iPivot=array[i]; /**< 选取枢轴 */

  11.     while (i<j) {
  12.         //使用j,从序列最右端开始扫描,直到遇到比枢轴小的数
  13.         while ((i<j) && (iPivot <= array[j])) {
  14.           j--;
  15.         }
  16.         //交换位置
  17.         if (i<j) {
  18.           array[i++]=array[j];
  19.         }

  20.         //使用i,从序列最左端开始扫描,直到遇到比枢轴小的数枢轴大的数
  21.         while ( (i<j) && (array[i] <= iPivot) ) {
  22.           i++;
  23.         }
  24.         //交换位置
  25.         if (i<j) {
  26.           array[j--]=array[i];
  27.         }
  28.     }

  29.     //最后填入枢轴位置
  30.     array[j]=iPivot;
  31.     //这里就是对枢轴两边序列进行排序的递归调用
  32.     quickSort(array, head, i-1);
  33.     quickSort(array, i+1, tail);
  34. }
复制代码
  代码已经严格测试过,一般不会有问题. 下面我们来看下 时间复杂度空间复杂度 .
   快速排序有个特点, 待排序列越接近无序,算法效率越高 ,也就是在基本有序的情况下时间复杂度为O( 深入浅出交换类排序算法(冒泡排序,快速排序)-14-技术控-最大的,漂浮,元素 n^2),最好情况下为O( 深入浅出交换类排序算法(冒泡排序,快速排序)-15-技术控-最大的,漂浮,元素 nlog_2n),平均复杂度为O( 深入浅出交换类排序算法(冒泡排序,快速排序)-16-技术控-最大的,漂浮,元素 nlog_2n),从所有内排序来看,快排是所有内排序中平均复杂度最好的. 另外空间复杂度也为O( 深入浅出交换类排序算法(冒泡排序,快速排序)-17-技术控-最大的,漂浮,元素 n^2).因为上面的算法实现是递归进行的, 递归需要栈空间 .



上一篇:Trace - adds logging and metrics to net trace
下一篇:PHP 7 deployment at Dailymotion
efyh5yCf 发表于 2016年10月7日 03:47
向楼主学习
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

我要投稿

推荐阅读


回页顶回复上一篇下一篇回列表
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )

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

返回顶部 返回列表