首页 > 代码库 > 冒泡排序算法总结

冒泡排序算法总结

2024-07-18 06:25:15   221人阅读

冒泡排序算法是思路最简单、最直接的排序方法之一。

每遍历一遍，则将最大（或者最小）的一个数冒泡出来。

预先定义的排序类型。由于只是为了验证排序方法是否正确，所以此处只是简单的对10个元素进行排序检测。如下所示：

#define MAXSIZE 10typedef struct  {	int r[MAXSIZE+1];	int length;}SqList;void swap(SqList *L,int i,int j){　　int temp = L->r[i];　　L->r[i] = L->r[j];　　L->r[j] = temp;}

备注：本文中的所有排序都是按照升序进行排序的。

第一种：有点像选择排序的冒泡排序算法：

这种方法并不是传统意义上的冒泡法。传统上的冒泡法是对排序数组中的相邻的元素进行比较、交换，而这种方法是用每一个元素与剩下的元素进行比较、交换。代码如下所示：

void BubbleSort0(SqList *L){	int i,j;	for (i = 0; i < L->length-1; i++)	{		for (j = i+1; j < L->length;j++)		{			if (L->r[i] > L->r[j])			{				swap(L,i,j);			}		}	}}

第二种：传统的冒泡排序法：

void BubbleSort1(SqList *L){	int i,j;	for (i = 0; i < L->length; i++)	{		for (j = 0; j < L->length - i -1; j++)		{			if (L->r[j] > L->r[j+1])			{				swap(L,j,j+1);			}		}	}}

第三种：改进后的冒泡排序法

我们知道，在冒泡排序算法中，即使后面的元素序列已经有序了，不需要再进行比较时，冒泡排序算法依旧会执行到底。那么能不能将其进行改进，当遇到这样的情况时，避免多余的比较操作呢？

可以设置一个标识位，当没有遇到交换数据时，就说明已经排好序了。那么算法即可停止运行。具体代码如下所示：

void BubbleSort2(SqList *L){	int i,j;	bool flag = true;	for ( i = 0; i < L->length && flag; i++)	{		flag = false;		for (j = 0; j < L->length-1-i; j++)		{			if (L->r[j] > L->r[j+1])			{				swap(L,j,j+1);				flag = true;			}		}	}}

 

参考资料：《大话数据结构》


联系
我们