文档章节

排序——冒泡排序法

翼动动空
 翼动动空
发布于 2016/06/05 16:43
字数 1503
阅读 1572
收藏 5

一、冒泡排序法概述

    冒泡排序法的基本思想是:对待排序记录关键字从后往前(逆序)进行多遍扫描,当发现相邻两个关键字的次序与排序要求的规则不符时,就将这两个记录进行交换。这样,关键字较小的记录将逐渐从后面向前面移动,就像气泡在水中向上浮一样,所以该算法也称为气泡排序法。(提示:冒泡排序法也可使较大的记录排在前面)
    假设需要排序的记录有n个,其关键字保存在数组a中,使用冒泡排序法,需对数组a进行n-1次扫描,完成排序操作,具体过程如下:
(1)将A[n]与A[n-1]进行比较,若A[n]<A[n-1],则交换两元素的位置。
(2)修改数组下标,使需要比较的两个元素为A[n-1]和A[n-2],重复步骤1,对这两个元素进行比较。重复这个过程,直到对A[2]和A[1]进行比较完为止。完成第1遍扫描,如下图所示。

3)经过第1遍扫描后,最小的元素已经像气泡一样“浮”到最上面,即位于元素A[1]中了。接下来重复前面的步骤,进行第2遍扫描,只是扫描到A[3]与A[2]进行比较完为止(因为A[1]中已经是最小的数据,不用再进行比较)。
(4)通过n-1遍扫描,前n-1个数都已经排序完成,最后一个元素A[n]肯定就是最大的数了。至此,完成排序操作。(提示:在以上描述中,为了让读者容易理解,假设数组元素是保存在A[1]~A[n]中的,由于C语言的数组元素下标是从0开始的,因此,需要修改数组的下标)


下面以一组待排序的数据演示冒泡排序的过程,假设有6个需要排序的数据序列如下:
69,65,90,37,92,6
通过冒泡排序法对这6个数据进行排序,其排序过程如下图所示。


第1遍从下向上扫描,首先对最后两个元素A[5]和A[4]进行比较,因92>6,将6上浮到A[4],92下沉到A[5]。接着将A[4]中的6和A[3]比较,6仍然较小,继续上浮至A[3]……这样经过n-1次比较,6上浮到A[0],完成第1遍扫描。此时A[0]中保存着当前数列中的最小数。完成最小数的冒泡过程。

第2遍扫描仍然从A[5]开始,至A[1]时结束,将37上浮到A[1]。
类似的方法,在第3遍扫描时,65上浮到A[2]中,至此,所有数都已按从小到大的顺序排列,但程序还需要进行第4遍和第5遍的扫描,因为程序并不知道后面的数据是否为有序的。

二、冒泡排序法实现

(1)冒泡排序法

void BubbleSort(int a[], int n)
{
    int i, j, t;

    for (i=0; i<n; i++) {
        for (j=n-1; j>i; j--) {
            if (a[j-1] > a[j]) {
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
            }
        
        }
        
        printf("第%d遍:", i+1);
        for (j=0; j<n; j++)
            printf("%d ", a[j]);
        printf("\n");
    }

}

(2)数组显示

void ShowData(int arr[], int n)
{
    int i;
    for (i=0; i<n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return;
}

(3)冒泡排序法测试

#include <stdio.h>
#define ARRAYLEN 6

int main(int argc, char *argv[])
{
    int i;
    int a[ARRAYLEN] = {69, 65, 90, 37, 92, 6};

    printf("原数据:");
    ShowData(a, ARRAYLEN);

    BubbleSort(a, ARRAYLEN);
    printf("排序后:");
    ShowData(a, ARRAYLEN);

    return 0;
}

(4)运行结果

三、冒泡排序法改进

    从上面的BubbleSort函数的过程可以看出,使用冒泡排序法对n个数据进行排序,一共需要进行n-1次的比较。如果本来就是有顺序的数据,也需要进行n-1次比较。这就造成了冒泡排序法的算法虽然简单,但效率较差。
    为了提升冒泡排序法的效率,可对BubbleSort函数进行改进,当在某一遍扫描时,发现数据都已经按顺序排列了,就不再进行后面的扫描,而结束排序过程。
    如何知道数据已经按顺序排好了呢?从上图可以看出,当第3遍扫描后,数据已经按顺序排列好了,第4遍扫描时将没有数据进行交换。因此,可以设置一个标志变量flag,在每一遍扫描之前将其值设置为0,在扫描数据过程中,若有数据交换,则设置其值为1。在一遍扫描完成之后,判断flag的值,若其值为0,表示在这一遍扫描中已经没有数据进行交换,数据已经按顺序排列,就不需要再进行后续的扫描了。


编程经验:为了提高排序效率,引进了一个标志变量。即通过内存空间使用上的增多来使程序执行效率得到提升,这称为“以空间换时间”。

(1)改进冒泡排序法的实现

void BubbleSortNew(int a[], int n)
{
    int i, j, t, flag=0;

    for (i=0; i<n; i++) {
        for (j=n-1; j>i; j--) {
            if (a[j-1] > a[j]) {
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
                flag = 1;
            }
        
        }
        
        printf("第%d遍:", i+1);
        for (j=0; j<n; j++)
            printf("%d ", a[j]);
        printf("\n");


        if (flag == 0)
            break;
        else 
            flag = 0;
    }

}

(2)改进冒泡排序法测试

#include <stdio.h>
#define ARRAYLEN 6

int main(int argc, char *argv[])
{
    int i;
    int a[ARRAYLEN] = {69, 65, 90, 37, 92, 6};

    printf("原数据:");
    ShowData(a, ARRAYLEN);

    BubbleSortNew(a, ARRAYLEN);
    printf("排序后:");
    ShowData(a, ARRAYLEN);

    return 0;
}

(3)运行结果

可以看出来,当第3遍扫描后,数据已经按顺序排列好了,第4遍扫描时将没有数据进行交换,就不再进行后面的扫描,而结束排序过程。

© 著作权归作者所有

翼动动空
粉丝 16
博文 69
码字总数 36207
作品 0
成都
程序员
私信 提问
Java数据结构和算法(三)——冒泡、选择、插入排序算法

1、冒泡排序   这个名词的由来很好理解,一般河水中的冒泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大,这物理规律我不作过多解释,大家只需要了解即可。   冒泡算法...

architect刘源源
2018/02/23
41
0
算法分析(3)——冒泡排序真的慢吗?

  在初学编程的时候,曾经有两个问题让我感到迷惑,第一个是利用中间变量交换另外两个变量,另一个就是冒泡排序。但是后来发现,冒泡排序几乎是所有排序算法中最简并且容易实现的,实际上许...

我是8位的
03/05
0
0
【排序】八大排序算法简介及它们各自的特点总结

概述: 一般使用的八大排序算法是:插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、堆排序、基数排序,每个方法有其适合的使用场景,可以根据具体数据进行选择. 几个概念: ...

nibolyoung
07/01
0
0
php四种基础算法:冒泡,选择,插入和快速排序法

许多人都说 算法是程序的核心,一个程序的好于差,关键是这个程序算法的优劣。作为一个初级phper,虽然很少接触到算法方面的东西 。但是对于冒泡排序,插入排序,选择排序,快速排序四种基本算...

PHP86
2013/12/21
222
0
白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇

在我的博客对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法进行了详细的讲解,并做成了电子书以供大家下载。下载地址为:http://downlo...

长平狐
2012/12/10
66
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
今天
6
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
今天
9
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
今天
5
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
今天
7
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
今天
7
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部