C++ 冒泡排序数据结构、算法及改进算法
程序代码如下：
// BubbleSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <cmath>
#include <iostream>
using namespace std;
#define MAXNUM 20
template<typename T>
void Swap(T& a, T& b)
{
int t = a;
a = b;
b = t;
}
template<typename T>
void Bubble(T a[], int n)
{//把数组a[0:n-1]中最大的元素通过冒泡移到右边
for(int i =0 ;i < n-1; i++)
{
if(a[i] >a[i+1])
Swap(a[i],a[i+1]);
}
}
template<typename T>
void BubbleSort(T a[],int n)
{//对数组a[0:n-1]中的n个元素进行冒泡排序
for(int i = n;i > 1; i--)
Bubble(a,i);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[MAXNUM];
for(int i = 0 ;i< MAXNUM; i++)
{
a[i] = rand()%(MAXNUM*5);
}
for(int i =0; i< MAXNUM; i++)
cout << a[i] << " ";
cout << endl;
BubbleSort(a,MAXNUM);
cout << "After BubbleSort: " << endl;
for(int i =0; i< MAXNUM; i++)
cout << a[i] << " ";
cin.get();
return 0;
}
但是常规的冒泡，不管相邻的两个元素是否已经排好序，都要冒泡，这就没有必要了，所有我们对这点进行改进。设计一种及时终止的冒泡排序算法：
如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列好了，没有必要再继续进行冒泡排序了。代码如下：
// BubbleSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <cmath>
#include <iostream>
using namespace std;
#define MAXNUM 20
template<typename T>
void Swap(T& a, T& b)
{
int t = a;
a = b;
b = t;
}
template<typename T>
bool Bubble(T a[], int n)
{//把数组a[0:n-1]中最大的元素通过冒泡移到右边
bool swapped = false;//尚未发生交换
for(int i =0 ;i < n-1; i++)
{
if(a[i] >a[i+1])
{
Swap(a[i],a[i+1]);
swapped = true;//发生了交换
}
}
return swapped;
}
template<typename T>
void BubbleSort(T a[],int n)
{//对数组a[0:n-1]中的n个元素进行冒泡排序
for(int i = n;i > 1 && Bubble(a,i); i--);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[MAXNUM];
for(int i = 0 ;i< MAXNUM; i++)
{
a[i] = rand()%(MAXNUM*5);
}
for(int i =0; i< MAXNUM; i++)
cout << a[i] << " ";
cout << endl;
BubbleSort(a,MAXNUM);
cout << "After BubbleSort: " << endl;
for(int i =0; i< MAXNUM; i++)
cout << a[i] << " ";
cin.get();
return 0;
}
改进后的算法，在最坏的情况下执行的比较次数与常规冒泡一样，但是最好情况下次数减少为n-1。
相关文章
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理，感兴趣的小伙伴们可以参考一下...2016-03-10
- 本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码，都是非常的不错，有需要的小伙伴可以参考下...2016-06-12
- 这篇文章主要介绍了c# 冒泡排序算法，需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了GOLANG版的冒泡排序和快速排序分享,需要的朋友可以参考下...2020-05-11
- 这篇文章主要介绍了C语言对数组元素进行冒泡排序的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-04
- 冒泡排序和快速排序算法在开发应用中各有优点了，下面我们来看几个关于php排序的几个例子。 使用PHP描述冒泡排序和快速排序算法，对象可以是一个数组。 使用PHP描...2016-11-25
- c语言实现插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、希尔排序示例,需要的朋友可以参考下...2020-04-25
- 冒泡排序我们排序算法中的许多中的其中一样了，这里我们一起来了解一下php实现冒泡排序实现方法与原理，具体如下。 一个程序应包括： 对数据的描述：在程序中要指定数...2016-11-25
- 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。...2020-04-25
- 这篇文章主要介绍了c#冒泡排序示例分享,需要的朋友可以参考下...2020-06-25
PHP常用排序算法实例小结【基本排序，冒泡排序，快速排序，插入排序】
小编推荐的这篇文章介绍了PHP常用排序算法实例小结，基本排序，冒泡排序，快速排序，插入排序，非常实用，有兴趣的同学快来看看吧。 代码如下复制代码classbevin{public$pub...2017-07-06- 这里给大家介绍的是通过某个方法实现判断命令行中输入的数字是几个，这样再用冒泡法排序的时候就不用担心输入的是几个数字，用到的知识主要是冒泡法排序...2020-04-25
- 冒泡排序为最基本的排序算法之一,其时间复杂度为O(n^2),这里我们就来简单看一下冒泡排序算法及Ruby版的简单实现,首先还是先来了解算法原理:...2020-06-30
- 冒泡排序是php中众多排序中的一个最简单的排序方法了下面一聚教程小伙伴就同各位介绍一个冒泡排序的例子，希望能帮助到各位。 冒泡排序简介： 冒泡排序（Bubble Sort），是...2016-11-25
- 这篇文章主要介绍了c#冒泡排序算法示例,需要的朋友可以参考下...2020-06-25
- 冒泡排序是一种计算机科学领域的较简单的排序算法，这篇文章主要介绍了c++冒泡排序示例,需要的朋友可以参考下...2020-04-25
- 本篇文章是对使用c语言实现冒泡排序,选择排序,快速排序的代码进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- 这篇文章主要给大家介绍了关于Java中冒泡排序的原生实现方法(正序与逆序)的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-11-23
- 本篇文章是对冒泡排序的三种实现方法进行了详细的介绍，需要的朋友可以过来参考下。希望对大家有所帮助...2020-04-25
- 这篇文章主要介绍了java数组算法例题代码详解(冒泡排序,选择排序),本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-07-16