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

技术控

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

[其他] 深入浅出选择类排序算法(简单选择排序,堆排序)

[复制链接]
圈子不同别硬融 发表于 2016-10-3 14:07:13
225 11

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

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

x
一.简单选择排序:

  简单选择排序的基本思想是:一次选定数组中的一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果min不等于i,说明假设错误,则交换min与i位置上的数。(也即每次从数列中找出一个最小的数放到最前面来,再从剩下的n-1个数中选择一个最小的,不断做下去。
   通俗的说:你要在你的班上选择女朋友(假定你有这个特权的话),你开始肯定会最喜欢的,然后再选择次喜欢的,然后继续在剩下的MM中找
  你比较喜欢的。这样就可以按你的要求排成一个序了,就这样理解。
  简单选择排序算法的关键:

  1.每一趟在n-i+1中选取最小的记录
  2.通过n-i次关键字进行比较
  3.总共需要n(n-1)/2次比较
  4.选择排序算法的时间复杂度是“死”的,也就是O(n^2)
  算法代码:

  1. void SelectSort(int* a, int len) {
  2.     int i,j,k;
  3.     for (i=1; i<len; i++) {    /**< 比较n-i次 i为指向无序区的开始位置  */
  4.         j=i;
  5.         for (k=i-1; j<len; j++)   {    /**< "A" k记下目前最小关键字的位置,每一轮进行比较取出最小值  */
  6.             if (a[j] < a[k])   {    /**< 如果排在前面的数字大于后面的就交换两者的key */
  7.                 k=j;
  8.             }
  9.         }
  10.         if (k>=i)  {    /**< /一轮结束后,把k认为的最小值和i进行交换  */
  11.             int m;
  12.             m = a[k];
  13.             a[k] = a[i-1];
  14.             a[i-1] = m;
  15.         }
  16.     }
  17. }
复制代码
从上面的代码可以看出,整个序列分为有序和无序部分, 在A循环中选取最小关键字,也即是有序序列进行更新的时刻.
   在这个算法中有两层循环, 外层循环执行n次, 内层循环执行n-1次 平均时间复杂度为O( n^2).代码中使用了一个临时变量m,空间复杂度为
  O(1).
  二. 堆排序:

  堆其实可以看成一个完全二叉树, 我们先温习下完全二叉树的定义:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树.
   

深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

  那么堆又是怎么回事呢, 堆分大小堆.
   大顶堆的需要在满二叉树的定义下再满足, 任何一个非叶结点的值, 都不大于其左右结点的值, 也就是父亲大孩子小.
   小顶堆的需要在满二叉树的定义下再满足, 任何一个非叶结点的值, 都不小于其左右结点的值, 也就是父亲小孩子大.
  根据上面的性质可以得出, 根节点要么最大, 要么最小. 从排序角度来看, 如果一个无序序列调整一个堆的数据结构,那么它必定是有序的. 这个调整的过程就是堆排序的过程.
  我们来取一组数据演示下堆排序的过程:
   原始序列:

深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

  我们先把这组数据建立一棵完全二叉树, 如图:
   

深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

  因为49’, 76, 13, 27为叶子结点,所以不需要对其进行调整, 我们直接从非叶子结点97, 38, 65, 49开始.
  1.先调整97, 发现97>49’, 满足大堆性质
  2.调整38, 发现38<97, 38<76, 父亲都小于孩子结点的值,需要调整, 和孩子结点中最大值97交换, 38和97交换, 发现38<49’, 继续交换.交换后结果为:
   

深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

  3.调整65, 发现65>13, 65>27 满足大顶堆性质, 不需要交换.
  4.调整49, 发现49<97, 49<65, 和较大的孩子97进行交换,交换后,发现49<76, 继续交换.结果为:
   

深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

  现在,已经没有需要调整的结点了, 也就是已经建立了一个大顶堆了.序列为:
   

深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

     因为是大顶堆, 所以根节点肯定是最大值了, 把根节点和最后一个结点进行交换, 就认为第一趟堆排序完成.然后除97这个序列再进行堆排序, 如此反复直到有序为止.
   来看下代码实现:
  
  1. ///< 大顶堆调整
  2. void HeapAdjust(int ziArray[], int iNonLeafIndex, int iLen)  {
  3.      
  4.     int iLeftChild = 2*iNonLeafIndex + 1;   
  5.     int iRightChild = 2*iNonLeafIndex + 2;  
  6.     int iMaxChild = iLeftChild;
  7.     while (iLeftChild < iLen) {
  8.         if (iRightChild < iLen) { ///< 说明有右儿子结点
  9.             if (ziArray[iLeftChild]<ziArray[iRightChild]) {
  10.                 iMaxChild = iRightChild; ///< 算出最大儿子结点Index
  11.             }
  12.         }
  13.         if (ziArray[iNonLeafIndex] < ziArray[iMaxChild]) {
  14.             int iTemp = ziArray[iNonLeafIndex];
  15.             ziArray[iNonLeafIndex] = ziArray[iMaxChild];
  16.             ziArray[iMaxChild] = iTemp;

  17.             iNonLeafIndex = iMaxChild;
  18.             iLeftChild = 2*iNonLeafIndex + 1;  
  19.             iRightChild = 2*iNonLeafIndex + 2;
  20.             iMaxChild = iLeftChild;

  21.         } else {
  22.             break;
  23.         }
  24.     }
  25.     int i = 0;
  26.     for(; i<iLen; i++)   {   
  27.         printf("%d ", ziArray[i]);
  28.     }
  29.     printf("\n");
  30.     return;   
  31. }   

  32. void HeapSort(int ziArray[], int iLen) {   
  33.     int i=0;   
  34.     ///< 建立初始堆
  35.     for (i=iLen/2; i>=1; i--) {   
  36.         printf("从非叶结点%d调整:", i);
  37.         HeapAdjust(ziArray, i-1, iLen);    ///< 从0开始
  38.     }

  39.     printf("\n%s\n", "递归调整过程:");
  40.     for (i=iLen-1; i>0; i--) {  
  41.         printf("取出本次调整的根结点:%d--", ziArray[0]);
  42.         ///<交换根结点和最后一个结点
  43.         int temp =ziArray[0];   
  44.         ziArray[0] = ziArray[i];   
  45.         ziArray[i] = temp;   
  46.         HeapAdjust(ziArray, 0, i);   
  47.     }   
  48.     return;   
  49. }   

  50. int main()   
  51. {   
  52.     int ziArray[] ={49,38,65,97,76,13,27,49};   

  53.     int iLen = sizeof(ziArray)/sizeof(int);
  54.     printf("%s\n", "原序列:");
  55.     int i = 0;
  56.     for(; i<iLen; i++)   {   
  57.         printf("%d ", ziArray[i]);
  58.     }
  59.     printf("\n");
  60.     HeapSort(ziArray, 8);   
  61.     printf("最后结果:");
  62.     for(i=0; i<8; i++)   {   
  63.         printf("%d ", ziArray[i]);
  64.     }   

  65.     return 0;   
  66. }
复制代码
  实现结果为:
  
  1. 原序列:
  2. 49 38 65 97 76 13 27 49
  3. 从非叶结点4调整:49 38 65 97 76 13 27 49
  4. 从非叶结点3调整:49 38 65 97 76 13 27 49
  5. 从非叶结点2调整:49 97 65 49 76 13 27 38
  6. 从非叶结点1调整:97 76 65 49 49 13 27 38

  7. 递归调整过程:
  8. 取出本次调整的根结点:97--76 49 65 38 49 13 27
  9. 取出本次调整的根结点:76--65 49 27 38 49 13
  10. 取出本次调整的根结点:65--49 49 27 38 13
  11. 取出本次调整的根结点:49--49 38 27 13
  12. 取出本次调整的根结点:49--38 13 27
  13. 取出本次调整的根结点:38--27 13
  14. 取出本次调整的根结点:27--13
  15. 最后结果:13 27 38 49 49 65 76 97
复制代码
   堆排序的时间复杂度是和完全二叉树的高度有关的. 完全二叉树的高度为O( log_2(n+1)),即结点最坏的调整堆的时间为O( log_2n),另外在调整堆的过程中, 完全二叉树从最下层最右边的非终端结点开始调整, 将它与其孩子进行比较和交换, 对于每个非终端结点来说,其实最多进行两次比较和交换操作,因此整个调整堆的最坏时间复杂度为O(n).所以最坏时间复杂度为O( nlog_2n).
    堆排序空间复杂度为O(1), 因为需要一个临时变量存储中间数据.快排的时间复杂度为O( nlog_2n),但是它的空间复杂度也为O( nlog_2n),而堆排序是O(1), 这个是堆排序的优势.
     原创文章,转载请注明出处: http://www.crazyshell.org/blog/?p=1049



上一篇:微信小程序版简易计算器
下一篇:[原]awk处理nginx日志
阿萨德法国货 发表于 2016-10-11 01:41:04
天灵灵地灵灵,这次一定是沙发!
回复 支持 反对

使用道具 举报

wmin0409 发表于 2016-10-11 02:06:57
如果你真的爱他,那么你必须容忍他部份的缺点。
回复 支持 反对

使用道具 举报

zyxin 发表于 2016-10-11 02:40:57
运气就是机会碰巧撞到了你的努力。
回复 支持 反对

使用道具 举报

李敏 发表于 2016-10-16 14:16:25
在街上看美女,高一点就是欣赏;低一点就是流氓。
回复 支持 反对

使用道具 举报

5zekvo3eny 发表于 2016-10-18 18:44:10
在乎的人不明白,明白的人不在乎。
回复 支持 反对

使用道具 举报

邻家大叔 发表于 2016-10-23 19:02:02
成全别人,恶心自己!
回复 支持 反对

使用道具 举报

kevinshi2010 发表于 2016-10-27 16:29:19
kevinshi2010今天只做了两件事,看帖和回帖
回复 支持 反对

使用道具 举报

董海伟 发表于 2016-10-28 14:52:38
很有看点!
回复 支持 反对

使用道具 举报

jflyr 发表于 2016-10-31 10:28:59
我可以轻视你,鄙视你,小看你,不看你.
回复 支持 反对

使用道具 举报

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

本版积分规则

我要投稿

推荐阅读

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

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

返回顶部 返回列表