97-对冒泡排序算法的实现和分析

冒泡排序算法的思想

1.比较两个相邻的数据，将较大的数据往后交换，将最大的数据交换到数据序列的最后
2.循环以上过程，每次都会少一个最大数据

冒泡排序算法的分析

时间复杂度： O(n^2)
空间复杂度：O(1)----> 主要考虑malloc的空间与n有没有关系，递归次数与n有没有关系
稳定性： 稳定

首先，先书写出需要用到的辅助函数

#include<stdio.h>

/*辅助函数：
    1.打印数据
	2.判断整个数据序列是否已经有序
	3.交互两个数据swap方法
*/

void Show(int *arr,int len)//打印数据
{
	for(int i=0;i<len;++i)
	{
		printf("%d  ",arr[i]);
	}
	printf("\n");
}

bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
{
	for(int i=0;i<len-1;++i)
	{
		if(arr[i]>arr[i+1])
		{
			return false;
		}
	}
	return true;
}

void SwapValue(int *a,int *b)//交互两个数据swap方法
{
	int tmp=*a;
	*a=*b;
	*b=tmp; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

下面是冒泡排序的过程


接下来书写冒泡排序函数

void BubbleSort1(int *arr,int len)
{
	for(int j=0;j<len-1;++j)//趟数 
	{
		for(int i=0;i<len-1-j;++i)
		{
			if(arr[i]>arr[i+1])
			{
				SwapValue(&arr[i],&arr[i+1]);
			}
		}
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

最后书写主函数

int main()
{
	int arr[]={7,87,29,75,41,50,62,92,69,22,76,77,35};
	Show(arr,sizeof(arr)/sizeof(arr[0]));
	BubbleSort1(arr,sizeof(arr)/sizeof(arr[0]));
	Show(arr,sizeof(arr)/sizeof(arr[0])); 
	return 0;
	
}
1
2
3
4
5
6
7
8
9

运行截图如下

最后，对这个冒泡排序算法函数进行简单优化一下
对时间复杂度没有任何影响
针对一些情况进行优化，对比较有序的数组，可以省去一些遍历比较过程

void BubbleSort2(int *arr,int len)
{
	for(int j=0;j<len-1;++j)//趟数 
	{
		bool flag=false; 
		for(int i=0;i<len-1-j;++i)
		{
			if(arr[i]>arr[i+1])
			{
				SwapValue(&arr[i],&arr[i+1]);
				flag=true;
			}
		}
		if(!flag)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19