C++ 冒泡排序数据结构、算法及改进算法_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。

时间: 2024-11-08 21:31:52

C++ 冒泡排序数据结构、算法及改进算法_C 语言的相关文章

OTSU算法及其改进算法学习

   这篇文章还是来自斯坦福课后作业hw2_3,主要是结合一个例子介绍otsu算法[亦称为大律算法,小日本]及其改进算法.    本文将先介绍老外的题目.解题思路及maltab解答,然后分析otsu算法步骤,末了给出opencv实现.     老外的题目:Binarization of Scanned Book Pages 题目大意: 网上图书服务,比如百度文库需要将大量藏书数字化.首先,书的每一页将被扫描.然后,这些扫描图片将被二值化,并通过字符识别引擎OCR处理,即图片转字符.对于传统书籍[

浅谈2路插入排序算法及其简单实现_C 语言

2路插入排序算法是在直接插入排序算法的基础上增加了一个辅助数组,其目的是减少排序过程中的移动次数,需要增加n个记录的辅助空间. 难点可能在于对取余的考虑吧,可以把辅助数组看成一个环状空间,这样就能更好的理解辅助空间中最大值和最小值的位置了. 算法整体思想还是很简单的,直接贴出可运行代码,注释还是挺清楚的,大家直接看就ok了 C语言实现示例 #include <stdio.h> #include <stdlib.h> void insert_sort(int *arr, int *t

常用排序算法整理分享(快速排序算法、希尔排序)_C 语言

整理了几个排序算法,通过测试来看,最快的还是快速排序算法,简直不是一个数量级的速度. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <stdbool.h>#include <time.h>#include <unistd.h> //一些排序算法整理//插入排序算法//直接插入排序voiddirect_insert_sort(int

C语言选择排序算法及实例代码_C 语言

选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

C++泛型算法的一些总结_C 语言

泛型算法的一些总结1.每个泛型算法的实现都独立于单独的容器,并且不依赖于容器存储的元素类型. 2.泛型算法从不直接添加或删除元素. 3.与容器的类型无关,只在一点上隐式地依赖元素类型:必须能够对元素做比较运算. A.需要某种遍历集合的方式:能够从一个元素向前移到下一个元素. B.必须能够知道是否到达了集合的末尾. C.必须能够对容器中的每一个元素与被查找的元素进行比较. D.需要一个类型来指示元素在容器中的位置,或者表示找不到该元素. 4.迭代器将算法和容器绑定起来.算法基于迭代器及其操作实现,

一些C语言中字符串的算法问题解决实例小结_C 语言

    字符串问题是面试中经常出现的问题,这类问题有很多,难以不一.下面是几道字符串的题目,网上都能找到解答,自己实现了一下,供网友参考.感觉算法重要的是要有正确的思路,实现起来不是问题.自己一定要多思考,这样收获可能会更多一点.         问题1:找两个字符串的最长公共子串.         具体描述,如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字

基于稀疏图上的Johnson算法的详解_C 语言

算法步骤简述: 1.计算图G加入新结点后的图G',加入的新结点0到所有原结点之间距离为0,同时形成新的边集E': 2.使用Bellman-Ford算法处理G',并形成0结点到各结点的最小距离d. 3.如果Bellman-Ford算法检测出有负权回路则提示FALSE并退出,否则继续. 4.对所有G'中的顶点v,根据0结点到v的最小距离,将h(v)设置为这个值. 5.对所有的边w(u,v),权值更新为w(u,v)+h(u)-h(v) 6.对图G中所有结点运行Dijkstra算法计算与其他顶点最短距离

深入全排列算法及其实现方法_C 语言

全排列在很多程序都有应用,是一个很常见的算法,常规的算法是一种递归的算法,这种算法的得到基于以下的分析思路.  给定一个具有n个元素的集合(n>=1),要求输出这个集合中元素的所有可能的排列.一.递归实现例如,如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)},显然,给定n个元素共有n!种不同的排列,如果给定集合是{a,b,c,d},可以用下面给出的简单算法产生其所有排列,即集合(a,b,c,

数据结构之堆详解_C 语言

1. 概述 堆(也叫优先队列),是一棵完全二叉树,它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆).它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等. 2. 堆的基本操作 堆是一棵完全二叉树,高度为O(lg n),其基本操作至多与树的高度成正比.在介绍堆的基本操作之前,先介绍几个基本术语: A:用于表示堆的数组,下标从1开始,一直到n PARENT(t):节点t的父节点,即floor(t/2) RIGHT(t):节点t的左孩子节点,即:2*t LEFT(t