首页 > 代码库 > 算法学习之排序算法：冒泡排序

算法学习之排序算法：冒泡排序

2024-07-21 11:53:30   227人阅读

冒泡排序：不同于插入排序，冒泡排序主要通过“交换”来完成。


基本思想：

1、将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（Record[1].key > Record[2].key）,则将两个记       录交换之，然后比较第二个记录和第三个记录的关键字。

2、依次类推，直至第n-1个记录和第n个记录的关键字被安置到最后一个记录的位置上。完成第一趟冒泡排序。结果         使得关键字最大的记录被安置到最后一个记录的位置上。

3、进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位         置上。第i趟冒泡排序是从Record[1]到Record[n-i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记            录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。

4、整个排序过程需要进行k(1<=k<n)趟冒泡排序，判别冒泡排序结束的条件是“在一趟排序过程中没有进行过交换记        录的操作”。


下面以8个记录为例进行分析如下：

初始关键字：49   38   65   97   76   13   27   49

第一趟冒泡：49   38   65   97   76   13   27   49//比较第一个跟第二个记录的关键字，逆序，交换

                                    38   49   65   97   76   13   27   49


                     38  49   65   97   76   13   27   49//比较第二个跟第三个记录的关键字，逆序，交换                    

                      38   65   49   97   76   13   27   49


                      38   65   49   97   76   13   27   49//比较第三个跟第四个记录的关键字，正序，不变

                      38   65   49   97   76   13   27   49


                      38   65   49  97   76   13   27   49//比较第四个跟第五个记录的关键字，逆序，交换

                      38   65   49   76   97   13   27   49


                      38   65   49   76  97   13   27   49//比较第五个跟第六个记录的关键字，逆序，交换

                      38   65   49   76   13   97   27   49


                      38   65   49   76   13  97   27   49//比较第六个跟第七个记录的关键字，逆序，交换

                      38   65   49   76   13   27   97   49


                      38   65   49   76   13   27  97   49//比较第七个跟第八个记录的关键字，逆序，交换

                      38   65   49   76   13   27   49   97

第一趟冒泡排序结束，最大值97被安置到最后一个记录上。依次后面的冒泡排序：

                                    38   65   49   76   13   27   49   97

第二趟冒泡排序结束：38   65   49   13   27   49   76   97

第三趟冒泡排序结束：38   49   13   27   49  65  76   97

第四趟冒泡排序结束：38   13   27   49  49  65   76   97

第五趟冒泡排序结束：38   13   27  49   49   65   76   97

第六趟冒泡排序结束：13   27  38   49   49   65   76   97

第七趟冒泡排序，没有记录进行交换，因此冒泡排序结束，最后的冒泡排序顺序为：

                                     13   27   38   49   49   65   76   97


示例代码（C语言实现）：
/*********************************************************************
 Author：李冰 date：2014-9-6
 Email：libing1209@126.com
 @array: the pointer to the records
 @num：the length of the records
*********************************************************************/
void bubblesort(int array[], int num)
{
	if(array == NULL || num < 0)
		return;

	int i, j, tmp;

	for(i = 0; i < num; i++)
		for(j = 1; j < num - i; j++)
			if(array[j-1] > array[j]){
				tmp = array[j-1];	
				array[j-1] = array[j];
				array[j] = tmp;
			}	
}


上面的代码时严格按照冒泡排序进行的，但未利用冒泡排序是否结束的判断。下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

示例代码2（C语言描述）：

/*********************************************************************
 Author：李冰 date：2014-9-6
 Email：libing1209@126.com
 @array: the pointer to the records
 @num：the length of the records
*********************************************************************/
void bubblesort(int array[], int num)
{
	int j, tmp;
	bool flag;

	flag = true; //冒泡排序结束判断标志
	while(flag){
		flag = false;	
		for(j = 1; j < num; j++)
			if(array[j-1] > array[j]){
				tmp = array[j-1];	
				array[j-1] = array[j];
				array[j] = tmp;
				flag = true;
			}	
		num--;
	}
}

总结：

1、冒泡排序总的时间复杂度为O(n^2)。

2、可以设置冒泡排序完成判断标志flag，如果某一趟冒泡排序没有进行记录交换，则冒泡排序完成。

3、注意示例代码中的边界判断。


参考文献：

1、《数据结构（C语言版）》严蔚敏 吴伟东 编著

2、http://blog.csdn.net/morewindows/article/details/6668714

3、http://blog.csdn.net/to_be_it_1/article/details/37866391











    








算法学习之排序算法：冒泡排序


联系
我们