前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++经典算法题-排序法 - 改良的气泡排序

C++经典算法题-排序法 - 改良的气泡排序

作者头像
cwl_java
发布2020-02-13 23:22:10
8810
发布2020-02-13 23:22:10
举报
文章被收录于专栏:cwl_Java

35.Algorithm Gossip: Shaker 排序法 - 改良的气泡排序

说明

请看看之前介绍过的气泡排序法:

代码语言:javascript
复制
for (i = 0; i < MAX - 1 && flag == 1; i++) {
            flag = 0;
            for (j = 0; j < MAX - i - 1; j++) {
                if (number[j + 1] < number[j]) {
                    SWAP(number[j + 1], number[j]);
                    flag = 1;
                }
            }
        }

事实上这个气泡排序法已经不是单纯的气泡排序了,它使用了旗标与右端左移两个方法来改进排序的效能,而Shaker排序法使用到后面这个观念进一步改良气泡排序法。

解法

在上面的气泡排序法中,交换的动作并不会一直进行至阵列的最后一个,而是会进行至MAX-i- 1,所以排序的过程中,阵列右方排序好的元素会一直增加,使得左边排序的次数逐渐减少,如我们的例子所示:

排序前:95 27 90 49 80 58 6 9 18 50

代码语言:javascript
复制
27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] ......
27 6 9 18 49 [50 58 80 90 95] ......
6 9 18 27 [49 50 58 80 90 95] ......
6 9 18 [27 49 50 58 80 90 95]

方括号括住的部份表示已排序完毕,Shaker排序使用了这个概念,如果让左边的元素也具有这样的性质,让左右两边的元素都能先排序完成,如此未排序的元素会集中在中间,由于左右两边同时排序,中间未排序的部份将会很快的减少。

方法就在于气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行, 如此完成一次排序的动作,而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。

一个排序的例子如下所示:

排序前:45 19 77 81 13 28 18 19 77 11

代码语言:javascript
复制
往右排序:19 45 77 13 28 18 19 77 11 [81]
向左排序:[11] 19 45 77 13 28 18 19 77 [81]

往右排序:[11] 19 45 13 28 18 19 [77 77 81]
向左排序:[11 13] 19 45 18 28 19 [77 77 81]

往右排序:[11 13] 19 18 28 19 [45 77 77 81]
向左排序:[11 13 18] 19 19 28 [45 77 77 81]

往右排序:[11 13 18] 19 19 [28 45 77 77 81]
向左排序:[11 13 18 19 19] [28 45 77 77 81]

如上所示,括号中表示左右两边已排序完成的部份,当left > right时,则排序完成。

代码示例

代码语言:javascript
复制
#include <stdio.h>
#include <stdlib.h> 
#include <time.h> 
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shakersort(int[]);
    int main(void) {
        int number[MAX] = {0}; int i;

        srand(time(NULL));
    } 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/01/17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 35.Algorithm Gossip: Shaker 排序法 - 改良的气泡排序
    • 说明
      • 解法
        • 代码示例
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档