冒泡交换排序C/C++代码实现

柔情只为你懂 2023-02-23 12:06 6阅读 0赞

## 举例： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
**通过两两比较相邻记录的关键字， 如果发生逆序，则进行交换**。

每进行一趟确定一个最大关键字的位置，其结果记录被安置到最后一个记录的位置上。 直到算法没有进行过交换记录的操作表示排序结束。

## 算法属性： ##

时间复杂度为O(n^2)  
空间复杂度为O(1)  
稳定排序。  
当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用

## 代码如下： ##

#include<stdio.h>
    
    #define MAXSIZE 20
    typedef int KeyType;
    typedef int InfoType;
    //记录类型
    typedef struct {
        
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    //顺序表类型
    typedef struct {
        
    	RedType r[MAXSIZE + 1];  //r[0]闲置或作哨兵
    	int length;	  			 //顺序表长度
    }SqList;
    
    
    //冒泡交换排序
    void BubbleSort(SqList &L) {
        
    	int i, j, flag = 1;
    	RedType t;
    	int m = L.length - 1;
    
    	for (i = 1; (i <= L.length - 1) && flag == 1; i++)
    	{
        
    		flag = 0;								//判断是否进行了交换，如果没进行交换则已有序退出循环
    		for (j = 1; j <= m; j++)
    		{
        
    			if (L.r[j].key > L.r[j + 1].key)	//如果逆序则进行交换
    			{
        
    				t = L.r[j];
    				L.r[j] = L.r[j + 1];
    				L.r[j + 1] = t;
    
    				flag = 1;						//进行了交换故大循环继续
    			}
    		}
    		--m;							    	//每躺结束时最大的记录已被安置好，不再继续参加比较
    	}
    }
    
    //打印排序结果
    void println(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		printf("%d, ", L.r[i].key);
    	}
    	printf("\n");
    }
    
    
    int main()
    {
        
    	SqList L;
    	L.r[1].key = 5;
    	L.r[2].key = 8;
    	L.r[3].key = 1;
    	L.r[4].key = 4;
    	L.r[5].key = 3;
    	L.length = 5;
    
    	BubbleSort(L);
    	println(L);
    }

## 运行结果： ##

![在这里插入图片描述][20200707111842186.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020070711141919.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[20200707111842186.png]: https://img-blog.csdnimg.cn/20200707111842186.png