冒泡排序c语言数据结构（数据结构-冒泡排序）

1）冒泡排序的基本思想 直接插入排序（Straight Insertion Sort）算法是一种常用且简单直观的方法它的基本思想是：设有n个数据的待排序序列，假设前面1到i-1个数据已经有序，是长度为i-1的有序序列，将第i个数据逐次与第i-1个数据、第i-2个数据……进行比较，直到找到第i个数据的插入位置，并插入得到一个新的长度为i的有序数列这一过程称为一趟插入，对第i个元素的插入称为第i趟插入，下面我们就来聊聊关于冒泡排序c语言数据结构?接下来我们就一起去了解一下吧!

冒泡排序c语言数据结构

1）冒泡排序的基本思想

直接插入排序（Straight Insertion Sort）算法是一种常用且简单直观的方法。它的基本思想是：设有n个数据的待排序序列，假设前面1到i-1个数据已经有序，是长度为i-1的有序序列，将第i个数据逐次与第i-1个数据、第i-2个数据……进行比较，直到找到第i个数据的插入位置，并插入得到一个新的长度为i的有序数列。这一过程称为一趟插入，对第i个元素的插入称为第i趟插入。

（2）冒泡排序的步骤

逐次进行相邻记录关键字的比较和必要的换位。首先比较第一个和第二个记录的关键字，将较小的一个放在前面，即第一个位置，较大的放在后面，即第二个位置。然后以同样的方式比较第二个和第三个……，直至完成第n-1个和第n个记录的关键字比较。共进行了n-1次比较，其结果是最大关键字的记录排序到位，并占据了第n个位置，称上述过程为第一趟冒泡。第二趟冒泡对第一个记录到第n-1个记录实施与第一趟冒泡相同的处理。共进行n-2次比较，使次大的关键字记录占据了第n-1个位置。一般的第i趟冒泡从第一个记录到第n-i 1个记录进行两两比较，共进行n-i次比较，直到第n-1趟冒泡，进行第一个记录与第二个记录的一次比较，完成排序。

例如，一组记录的关键字序列为{ 81， 63，45，72 }，冒泡过程如下：

初始状态 81 63 45 72

第一趟冒泡后 63 45 72 [81] 比较了3次

第二趟冒泡后 45 63 [72] [81] 比较了2次

第三趟冒泡后 [45] [63] [72] [81] 比较了1次

一般规则

• n个元素，要进行n-1趟冒泡
• 第j趟冒泡要进行 n-j 次元素间的比较

（3）冒泡排序的算法实现

冒泡排序算法

void bsort(NODE a[],int n) /* 对存放在a[1],a[2],…,a[n]中的序列进行冒泡排序 */ { NODE temp; int i,j,flag; for(j=1;j<=n-1;j ) /*共进行n-1趟冒泡*/ { flag=0; for(i=1;i<=n-j;i ) /*第j趟共进行n-j次比较*/ if(a[i].key>a[i 1].key) { flag=1; /*说明本趟有元素交换*/ temp=a[i]; a[i]=a[i 1]; a[i 1]=temp; } if(flag==0)break; /*没有元素交换，说明已排好序*/ } }

上述算法中外层循环控制冒泡趟数，内层循环控制每趟冒泡时记录关键字的比较次数。在每趟冒泡中，用flag标志量记录是否出现过记录的交换，如果没有出现过交换，说明记录序列已经有序，结束冒泡，这样可避免不必要的计算过程。例如在最好情况下，待排序的记录序列已经有序，程序只需要一趟冒泡，进行n-1次元素的比较。最坏情况下，待排的记录序列为逆序，则程序要完成双重循环的全过程。显然冒泡排序的时间复杂度为O(n2), 并且是稳定的。

冒泡排序是待排序序列中的元素相邻的两个数据进行比较，满足条件时进行交换，每一趟完成，序列中最大（最小）的数据被调整到最上面的位置，类似水中的冒泡，因此称作冒泡排序。