欢迎访问优讯网!
您当前的位置:首页 > 爱编程

C++实现双向冒泡排序算法

时间:2020-04-28 09:27:41  来源:优讯网  作者:小卡司  浏览次数:
这篇文章主要为大家详细介绍了C++实现双向冒泡排序算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

本文实例为大家分享了C++实现双向冒泡排序算法的具体代码,供大家参考,具体内容如下

一、概念(来源于百度百科)

传统冒泡算法原理

冒泡排序算法的运作如下:(从后往前)

1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤,除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

双向冒泡算法原理

双向冒泡排序算法的运作如下:

1.传统冒泡气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行,如此完成一次排序的动作

2.使用left与right两个旗标来记录左右两端已排序的元素位置。

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

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

往右排序: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时,则排序完成。

二、实现程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <ctime>
  
const int MAX = 30;
  
// 交换两个数
void Swap(int &x, int &y) {
  int temp;
   
  temp = x;
  x = y;
  y = temp;
}
  
// 双向冒泡排序
void twoBubbleSort(int arr[], int len) {
  int left, right, shift, i; // shift为记录左右两端已排序的元素位置
   
  left = 0;
  right = len - 1;
  shift = 1;
  while(left < right) { // 往右排序
    for(i = left; i < right; i++) {
      if(arr[i] > arr[i+1]) { // 第一个数比第二个数大,交换
        Swap(arr[i], arr[i+1]);
        shift = i;
      }
    }
    right = shift;
    for(i = right-1; i >= left; i--) { // 向左排序
      if(arr[i] > arr[i+1]) { // 第一个数比第二个数大,交换
        Swap(arr[i], arr[i+1]);
        shift = i + 1;
      }
    }
    left = shift;
  }
}
  
int main(int argc, const char * argv[]) {
  // insert code here...
  int arr[MAX], i;
   
  srand((int)time(NULL)); // 设置时间为随机点
  std::cout << "排序前:";
  for(i = 0; i < MAX; i++) {
    arr[i] = rand() % 100;
    std::cout << arr[i] << " ";
  }
   
  // 调用双向冒泡排序函数
  twoBubbleSort(arr, MAX);
   
  std::cout << "\n排序后:";
  for(i = 0; i < MAX; i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}

运行结果:

以上就是本文的全部内容,希望对大家的学习有所帮助

来顶一下
返回首页
返回首页

原文链接:https://www.jb51.net/article/185596.htm


推荐资讯
如何下载旧版centos iso镜像 如何下载迷你mini版的centos镜像
如何下载旧版centos i
计算机的正确使用姿势 电脑痴如何正确的使用电脑
计算机的正确使用姿势
好用的后台管理的前端框架模版H-ui H-ui框架模版分享
好用的后台管理的前端
微信电脑多开方法 无需辅助电脑版微信双开方法分享
微信电脑多开方法 无
相关文章
栏目更新
栏目热门