冒泡排序 C语言

野性酷女 2022-12-22 09:59 183阅读 0赞

### 冒泡排序 ###

冒泡排序( Bubble Sort)是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上 “漂浮” (左移)，或者使关键字大的记录如石块一样逐渐向下 “坠落”(右移)。

**算法步骤：**

（1）设待排序的记录存放在数组Data\[1…n\]中。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序(即Data\[1\].key > Data\[2\].key)，则交换两个记录。然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。

（2）然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。

（3）重复上述比较和交换过程，第i趟是从L.Data\[1\]到L.Data\[n-i+1\]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。直到在某一趟排序过程中没有进行过交换记录的操作，说明序列已全部达到排序要求，则完成排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
**时间复杂度**

最好情况：O(n)  
最坏情况：O( n 2 n^2 n2)  
平均情况：O( n 2 n^2 n2)

**空间复杂度**

O(1)

**算法特点：**

1）稳定排序。  
2）可用于链式存储结构。  
3）移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，次算法不宜采用。

**完整代码如下：**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100 //顺序表最大容量，可以自行加大 
    
    typedef struct 
    { 
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    { 
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    { 
    	L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    { 
    	printf("请输入："); 
    	while(1)//建立一个死循环，循环终止条件是按了enter键 
    	{ 
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{ 
    			printf("顺序表已满！\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    { 
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
    	{ 
    		printf("顺序表是空的！\n");
    		return ;
    	}
    	printf("打印为：");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    void BubbleSort(SqList &L)//对顺序表L做冒泡排序 
    { 
    	int i,j;//次数 
    	bool flag = true;//flag用来标志某一趟排序是否发生交换，若某一趟排序都不发生交换（flag==false）证明已排序完成，节省排序时间 
    	for(i=L.length;i>1&&flag;i--) 
    	{ 
    		flag = false;
    		for(j=1;j<i;j++)
    		{ 
    			if(L.Data[j].key > L.Data[j+1].key)//若前面数据大于后面数据，交换两数据位置 
    			{ 
    				flag = true;
    				L.Data[0] = L.Data[j];//L.Data[0]为哨兵，用作交换介质 
    				L.Data[j] = L.Data[j+1];
    				L.Data[j+1] = L.Data[0];
    			}
    		}
    	}
    }
    
    int main()
    { 
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	BubbleSort(L);//冒泡排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }

![在这里插入图片描述][20201119191604665.png_pic_center]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/56e5ec0984ef4f09a67505fa4f3dc04b.png
[20201119191604665.png_pic_center]: /images/20221120/ea27bc3cca2e434c936047e3a02cbc44.png