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

冒泡排序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次

一般规则

(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), 并且是稳定的。

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

,