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。

赞 (0)

相关推荐

  • C++ 数据结构之水洼的数量算法

    C++ 数据结构之水洼的数量算法 题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼. 使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止. 则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N). 代码: /* * main.cpp * * Created on: 2014.7.12 *本栏目更多精彩内容:http://ww

  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • C++ 数据结构完全二叉树的判断

    C++ 数据结构完全二叉树的判断

    C++ 数据结构完全二叉树的判断 完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二

  • C++ 数据结构 堆排序的实现

    C++ 数据结构 堆排序的实现

    堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下

  • C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • C++语言数据结构 串的基本操作实例代码

    C++语言数据结构 串的基本操作实例代码

    C语言数据结构 串的基本操作实例代码 输出结果: 实现代码: #include<iostream> using namespace std; typedef int Status; #define Max 20 #define OK 1 #define ERROR 0 #define OVERLOE -2 typedef struct//堆分配表示串 { char *ch; int length; }HString; //====================================

  • C++数据结构之文件压缩（哈夫曼树）实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • C++ 冒泡排序数据结构、算法及改进算法

    程序代码如下: 复制代码 代码如下: // BubbleSort.cpp : 定义控制台应用程序的入口点.//#include "stdafx.h"#include <cmath>#include <iostream>using namespace std;#define  MAXNUM 20template<typename T>void Swap(T& a, T& b){    int t = a;    a = b;    b

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • JS实现的冒泡排序，快速排序，插入排序算法示例

    JS实现的冒泡排序，快速排序，插入排序算法示例

    本文实例讲述了JS实现的冒泡排序,快速排序,插入排序算法.分享给大家供大家参考,具体如下: 一.冒泡排序 大致分两步: 1.依次对比相邻2个数字,前者比后者大就调换位置 2.重复第一步操作,直到所有数字都按顺序排列 function bubbleSort(arr){ for(var i=1; i<arr.length; i++){ for(var j=0; j<arr.length-i; j++){ if(arr[j]>arr[j+1]){ arr[j]=[arr[j+1],arr[j+

  • java数据结构与算法之插入算法实现数值排序示例

    本文实例讲述了java数据结构与算法之插入算法实现数值排序.分享给大家供大家参考,具体如下: 写在这里做个纪念,关键是要理解插入点,在插入点,初始的in和out都在这个插入点,然后通过in自减对数组进行重新排序 public static void insertSort(){ for(int out=1; out<a.length; out++){ int temp = a[out]; int in = out; while(in>0&& a[in-1]>temp){ a

  • JavaScript数据结构与算法之检索算法实例分析【顺序查找、最大最小值、自组织查询】

    JavaScript数据结构与算法之检索算法实例分析【顺序查找、最大最小值、自组织查询】

    本文实例讲述了JavaScript数据结构与算法之检索算法.分享给大家供大家参考,具体如下: javascript数据结构与算法---检索算法(顺序查找.最大最小值.自组织查询) 一.顺序查找法 /* * 顺序查找法 * * 顺序查找法只要从列表的第一个元素开始循环,然后逐个与要查找的数据进行比较. * 如果匹配到了,则结束查找. * 如果到了列表的结尾也没有匹配到,那么这个数据就不存在于这个列表中. * */ function seqSearch(arr, data) { for (var i

  • JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】

    JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】

    本文实例讲述了JavaScript数据结构与算法之检索算法.分享给大家供大家参考,具体如下: javascript数据结构与算法---检索算法(二分查找法.计算重复次数) /*只需要查找元素是否存在数组,可以先将数组排序,再使用二分查找法*/ function qSort(arr){ if (arr.length == 0) { return []; } var left = [];//存储小于基准值 var right = [];//存储大于基准值 var pivot = arr[0]; fo

  • Java数据结构之常见排序算法（上）

    目录 认识排序 常见排序的分类 直接插入排序 希尔排序(缩小增量排序) 选择排序 堆排序 认识排序 在学校中,如果我们要参加运动会,或者军训的时候,会按照身高从矮到高进行站队,比如上课老师手上拿的考勤表,通常是按照学号从低到高进行排序的.再比如编程语言排行榜,也是在排序. 生活中有相当多的排序场景,由此可知,排序还是很重要的, 本章就会介绍常见的一些排序算法. 所谓排序呢,就拿我们上面的举例来说,会按照某个或某些关键字的大小,递增或者递减排列起来的操作,这就是排序,这里面也涉及到排序的稳定性,举

  • java 排序算法之希尔算法

    java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

  • java实现最短路径算法之Dijkstra算法

    java实现最短路径算法之Dijkstra算法

    前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无

  • Java贪心算法之Prime算法原理与实现方法详解

    Java贪心算法之Prime算法原理与实现方法详解

    本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

随机推荐