交换排序—冒泡排序(Bubble Sort)

简介: 基本思想: 最简单的排序,也是最耗时间的排序 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

基本思想:

最简单的排序,也是最耗时间的排序

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

冒泡排序的示例:

 

算法的实现:

void bubbleSort(int a[], int n){
	for(int i =0 ; i< n-1; ++i) {
		for(int j = 0; j < n-i-1; ++j) {
			if(a[j] > a[j+1])
			{
				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
			}
		}
	}
}



冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。本文再提供以下两种改进算法:

1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

 
void Bubble_1 ( int r[], int n) {
	int i= n -1;  //初始时,最后位置保持不变
	while ( i> 0) { 
		int pos= 0; //每趟开始时,无记录交换
		for (int j= 0; j< i; j++)
			if (r[j]> r[j+1]) {
				pos= j; //记录交换的位置 
				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		i= pos; //为下一趟排序作准备
	 } 
}  

 

2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

 
void Bubble_2 ( int r[], int n){
	int low = 0; 
	int high= n -1; //设置变量的初始值
	int tmp,j;
	while (low < high) {
		for (j= low; j< high; ++j) //正向冒泡,找到最大者
			if (r[j]> r[j+1]) {
				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		--high;					//修改high值, 前移一位
		for ( j=high; j>low; --j) //反向冒泡,找到最小者
			if (r[j]<r[j-1]) {
				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
			}
		++low;					//修改low值,后移一位
	} 
} 
相关文章
|
搜索推荐
排序算法:QuickSort
排序算法:QuickSort
|
2月前
冒泡排序 和 qsort排序
冒泡排序 和 qsort排序
15 1
|
2月前
|
搜索推荐
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
27 1
|
7月前
|
搜索推荐 算法 Java
sort-01-bubble sort 冒泡排序算法详解
这是一个关于排序算法的系列文章摘要。作者整理了10种不同的排序算法,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序和大文件外部排序。文章详细介绍了冒泡排序的工作原理、流程,并提供了代码实现,强调了在实现中考虑的改进点,如统一接口、实用性增强和日志输出。此外,还提供了一个排序接口和工具类以方便使用,并通过测试代码和日志展示了排序过程。整个系列旨在帮助读者理解和掌握排序算法。相关代码已开源在GitHub。
|
7月前
|
搜索推荐 算法 Java
sort-03-SelectSort 选择排序算法详解
这是一个关于排序算法的系列文章摘要,包括了各种排序算法的介绍和Java实现。文章列举了冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序的链接和简要说明。其中,选择排序算法被详细解释,它是通过找到未排序序列中的最小元素并将其放到正确位置来逐步构建有序序列的。Java实现中,选择排序的`doSort`方法通过两层循环实现,时间复杂度为`O(N^2)`,是稳定的排序算法。整个排序项目已开源在GitHub。
|
7月前
|
搜索推荐 算法 Java
sort-02-QuickSort 快速排序到底快在哪里?
这是一个关于排序算法的系列文章的摘要。文章详细介绍了各种排序算法,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及处理大文件的外部排序。特别强调了快速排序,它是1959年由Tony Hoare发明的,平均时间复杂度为O(n log n),优于其他如合并排序和堆排序。快速排序采用分而治之的策略,选取基准元素,通过分区操作将数组分成两部分,然后递归地对这两部分进行排序。文章还通过示例和Java代码解释了快速排序的步骤和实现。最后,提供了开源项目的链接,供读者进一步学习和研究。
2-路插入排序(Two-Way Insertion Sort)
算法介绍 算法描述 算法分析 代码实现 参考
|
存储 算法 搜索推荐
|
搜索推荐 算法 数据可视化
【基础篇】9 # 排序:冒泡排序(Bubble Sort)、插入排序(Insertion Sort)、选择排序(Selection Sort)
【基础篇】9 # 排序:冒泡排序(Bubble Sort)、插入排序(Insertion Sort)、选择排序(Selection Sort)
122 0
|
算法 Java 测试技术
详解Java算法之冒泡排序(Bubble Sorting)
详解Java算法之冒泡排序(Bubble Sorting)
237 0
详解Java算法之冒泡排序(Bubble Sorting)