冒泡排序

Posted on | Post modified: | In
Words count in article: 360 | Reading time ≈ 1

-冒泡排序算法思想
-冒泡排序算法实现

算法介绍

冒泡排序又称起泡排序。它是通过一系列的“交换”动作完成的。首先，第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不执行交换；然后第二个关键字和第三个关键字比较，如果第二个大，则执行交换，否则不交换......依次执行下去。第一趟冒泡排序完成，最大的关键字被交换到了最后。经过多趟排序，最终使整个序列有序。 起泡排序算法结束的条件是在一趟排序过程中没有发生关键字交换。 ---

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BubbleSort(int R[],int n){
 //默认待排序关键字为整型
	int i,j,flag;
	int temp;
	for(i=n-1;i>=1;--i){
		flag=0;              //flag用来标记本趟排序是否发生了交换
		for(j=1;j<=i;j++)
			if(R[i-1]>R[i]){
				temp=R[i];
				R[i]=R[i-1];
				R[i-1]=temp;
				flag=1;
				}
			if(flag==0)
				return;
	}
}

时间复杂度

最坏情况下，每趟都要发生交换，复杂度为O（n2） 最好情况下，每一趟只进行循环，不进行交换，复杂度为O（n） 平均时间下时间复杂度为O（n2） ---

空间复杂度

由算法可知，额外辅助空间只有一个temp，因此空间复杂度为O（1）

Thanks for your reward！