交换排序—冒泡排序(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值,后移一位
	} 
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏面朝大海春暖花开

入住腾讯云+社区

对于的github基础代码https://github.com/chywx/JavaSE

24610
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 四、数据结构:对象和数组

439100
来自专栏机器学习实践二三事

python基础----map和reduce

map和reduce Map简单来说就是:一个映射函数就是对一些独立元素组成的概念上的列表的每一个元素进行指定的操作 Reduce简单来说就是:对一个列表的...

21160
来自专栏C/C++基础

printf()详解之终极无惑

printf()是C语言标准库函数,用于将格式化后的字符串输出到标准输出。标准输出,即标准输出文件,对应终端的屏幕。printf()申明于头文件stdio.h。

44030
来自专栏Python小屋

Python 3.6.x字符串格式化方法小结

1 使用%符号进行格式 使用%符号进行字符串格式化的形式如下图所示,格式运算符%之前的部分为格式字符串,之后的部分为需要进行格式化的内容。 ? Python...

31560
来自专栏猿人谷

size_type、size_t、differentce_type以及ptrdiff_t

目录(?)[-] size_type size_t different_type ptrdiff_t size_t是unsigned类型,用于指明数...

22870
来自专栏猿人谷

求子数组的最大和

分析:输入一个整形数组,数组里有正数也有负数,数组中一个或连续的多个正数,求所有子数组的和的最大值。 当我们加上一个正数时,和会增加;当我们加上一个负数时,和会...

203100
来自专栏AI派

Numpy 修炼之道 (10)—— 结构化数组

之前我们操作Numpy的数组时,都是通过索引来操作的。针对二维数组,使用索引可以完成对行、列的操作。但是这是非常不直观的。可以把二维数组想象成一个excel表格...

46450
来自专栏IT可乐

深入理解计算机系统(2.5)------C语言中的有符号数和无符号数以及扩展和截断数字

  上一篇博客我们讲解了计算机中整数的表示,包括无符号编码和补码编码,以及它们之间的互相转换,个人觉得那是非常重要的知识要点。这篇博客我们将介绍C语言中的有符号...

29480
来自专栏赵俊的Java专栏

两数之和

22630

扫码关注云+社区

领取腾讯云代金券