`

数据结构-排序: 交换排序(冒泡排序法)

阅读更多

数据结构-排序: 交换排序(冒泡排序法)

冒泡排序(Bubble Sorting)的基本思想是:设待排序n个元素存放在数组a[n]中,无序区范围初始为(a(0),a(1),a(2),...,a[n-1]),冒泡 排序方法是在当前无序区内,从最上面的元素a[0]开始,对每两个相邻的元素a[i+1]和a[i](i=0,1,...,n-1)进行比较,且使值较小 的元素换至值较大的元素之上(若a[i]>a[i+1],则a[i]和a[i+1]的值互换),这样经过一趟冒泡排序后,假设最后下移的元素为 a[k],则无序区中值较大的几个元素到达下端并从小到大依次存放在a[k+1],a[k+2],...a[n-1]中,这样无序区范围变为 (a[0],a[1],a[2],...,a[k])。在当前无序区内进行下一趟冒泡排序。这个过程一直到某一趟排序中不出现元素交换的动作,排序结束。 整个排序过程最多执行n-1遍。这种排序方法是通过相邻元素之间的比较与交换,使值较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单 元),就象水底下的气泡一样逐渐向上冒。故称为冒泡排序法。
1、排序方法

 将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数 组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
(1)初始
  R[1..n]为无序区。

(2)第一趟扫描
  从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n- 1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key<R[j].key,则交换 R[j+1]和R[j]的内容。
 第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。

(3)第二趟扫描

  扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……
 最后,经过n-1趟扫描可得到有序区R[1..n]
注意:
  第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。

2、冒泡排序过程示例
 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【参见动画演示

3、排序算法
(1)分析
 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。
 若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为 此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟 排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。

(2)具体算法

using System;
using System.Collections.Generic;
using System.Text;

namespace ExEbullitionSorter
{
class EbullitionSorter
{
public void Sort(int[] arr)
{
int i, j, temp;
bool done = false;
j = 1;
while ((j < arr.Length) && (!done))//判断长度
{
done = true;
for (i = 0; i < arr.Length - j; i++)
{
if (arr[i] > arr[i + 1])
{
done = false;
temp = arr[i];
arr[i] = arr[i + 1];//交换数据
arr[i + 1] = temp;
}
}
j++;
}
}

static void Main(string[] args)
{
int[] array = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
EbullitionSorter e = new EbullitionSorter ();
e.Sort(array);
foreach (int m in array)
Console.WriteLine("{0}", m);

}
}
}

分享到:
评论

相关推荐

    经典排序算法源代码-插入排序-选择排序-冒泡排序

    在计算机科学领域,排序算法是数据结构与算法中不可或缺的一部分,它们用于对一组数据进行排列,使其按照特定的顺序呈现。本资源包含三个经典的排序算法的源代码:插入排序、选择排序和冒泡排序,这些都是初级到中级...

    公共基础复习资料

    - 交换类排序法:冒泡排序、快速排序。 - 插入类排序法:简单插入排序、希尔排序。 - 选择类排序法:简单选择排序、堆排序。 #### 二、程序设计基础 1. **源程序文档化**: - 注释的重要性:提高代码的可读性...

    排序问题(选择法排序, 冒泡法排序, 合并法排序),VB6.0源代码编写

    - 特点:冒泡排序是一种稳定的排序方法,无论相同元素的相对位置如何,排序后的顺序都不会改变。其最坏、最好和平均时间复杂度均为O(n²)。 - VB6.0实现:通过两层嵌套循环,外层循环控制比较的轮数,内层循环用于...

    数据结构讲义

    ### 数据结构讲义知识点概述 #### 一、绪论 - **基础知识** ... - 内存占用:原地排序(如冒泡排序、选择排序、插入排序等)内存占用较小。 - 处理大数据集的能力:归并排序、基数排序等适合处理大规模数据集。

    综合排序 程序 数据结构(C语言) 课程设计

    - 冒泡排序:通过不断地比较相邻元素并交换位置,将较大的元素逐渐“冒”到数组的一端。 - 插入排序:将元素插入到已排序部分的正确位置,逐步构建有序序列。 - 选择排序:每次找到未排序部分的最小(或最大)...

    数据结构--内部排序

    本文将深入探讨标题"数据结构--内部排序"中涉及的几种主要排序算法,并对描述中提及的插入排序、Shell排序、冒泡排序、快速排序、简单选择排序以及堆排序进行详细解析。 1. 插入排序:插入排序是一种简单的排序算法...

    数据结构1800例题与答案.rar

    - 冒泡排序:重复遍历数组,相邻元素互换,直至无交换。 - 选择排序:每次找出未排序部分的最大(或最小)元素,放到已排序部分的末尾。 - 插入排序:将未排序元素逐个插入到已排序部分的合适位置。 - 快速排序...

    数据结构线性表快速排序

    ### 数据结构线性表快速排序知识点解析 #### 一、数据结构基础概念 - **数据结构**:数据结构是计算机科学中的一个核心概念,它主要研究数据的逻辑结构与存储结构,以及基于这些结构的数据操作方法。良好的数据...

    基于C++冒泡排序法

    冒泡排序法是一种基础但重要的排序算法,尤其在学习数据结构和算法的初期阶段,它为理解排序原理提供了直观的示例。C++是广泛应用于系统编程、应用编程、游戏开发等多个领域的强大编程语言,因此用C++实现冒泡排序是...

    数据结构与算法分析(Java英文版)

    - 冒泡排序(Bubble Sort):通过重复遍历待排序的序列,比较每对相邻元素并交换位置,直到没有再需要交换的元素为止。 - 插入排序(Insertion Sort):将未排序的元素逐一插入到已排序的序列中,保持已排序部分始终有序...

    数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序等等

    这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果...

    数据结构与算法分析C++版

    - **冒泡排序(Bubble Sort)** - 原理:重复地走访过要排序的数列,依次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来。 - 时间复杂度:平均/最坏情况为O(n^2),最好情况为O(n)。 - **快速排序(Quick ...

    数据结构期末复习

    ### 数据结构期末复习知识点 #### 第一章 绪论 1. **数据结构定义**: - 定义:数据结构是指相互之间存在一种或多种特定关系的数据元素的集合及其该集合中数据元素之间的关系组成的整体。 - 包含三个方面: - ...

    javaa算法的源码-AlgorithmsDS-in-Java:用源代码和文档在Java中实现算法和数据结构

    - 冒泡排序:通过相邻元素之间的交换逐步排序,适合小规模数据。 - 选择排序:每次找到未排序部分的最大(或最小)元素,放置到已排序部分的末尾。 - 插入排序:将元素插入到已排序部分的合适位置,适用于接近...

    C语言_插入排序法和冒泡排序法

    根据给定文件的信息,本文将深入探讨C语言中的两种经典排序方法:插入排序法与冒泡排序法。这两种方法在实际编程中应用广泛,对于理解数据结构与算法的基础概念至关重要。 ### 一、冒泡排序法 #### 1.1 基本原理 ...

    数据结构实验-排序算法

    2. **冒泡排序**:冒泡排序也叫肥泡排序,通过不断交换相邻两个不正确顺序的元素,使得每一趟遍历后,最大的元素“浮”到数组末尾。这个过程就像水中的气泡逐渐上浮一样。 3. **插入排序**:插入排序的工作方式类似...

    数据结构中的排序问题

    - 选择法排序:例如冒泡排序、选择排序等,通过每次找到最大(最小)元素并放到正确位置来逐步排序。 - 交换法排序:如快速排序、希尔排序等,通过交换元素来调整序列。 - 归并排序:利用分治策略,将序列分为两...

    数据结构与算法课件(PPT)

    - 冒泡排序:相邻元素比较交换,平均时间复杂度O(n^2)。 - 快速排序:基于分治策略,平均O(n log n),最坏O(n^2)。 - 归并排序:稳定排序,时间复杂度O(n log n),需要额外空间。 - 堆排序:利用堆数据结构,...

    java基础数据结构-排序算法

    - **冒泡排序**:通过重复走访过要排序的数列,依次比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。虽然实现简单,但是效率不高,时间复杂度同样为O(n^2)。 - **快速排序**:采用分治法策略来把一个序列...

Global site tag (gtag.js) - Google Analytics