冒泡排序法c语言代码_用冒泡法对数组a进行排序

冒泡排序法c语言代码_用冒泡法对数组a进行排序选择法排序选择法排序是指:如果要把一个数组从小到大排列,那么就从该数组中依次选择最小的数字来排序。从第一个数字开始,将第一个数字与数组中剩下数字中最小的那一个交换位置,然后将第二个数字与剩下数字中最小的那个交换位置,以此类推,直到最后一个数字。例如输入数组{7,5,4,8,6,2,3}第一次排序通过查找最小的数字,交换7与2的位置;第二次查找5后面最小的数字,找到了3,交换5与3的位置;第三次查找4之后最小的数字,发现并没有数字比4小,交换4与4的位置(相当于没有改变);第四次查找8后面最小的数字5,

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

选择法排序

选择法排序是指:如果要把一个数组从小到大排列,那么就从该数组中依次选择最小的数字来排序。从第一个数字开始,将第一个数字与数组中剩下数字中最小的那一个交换位置,然后将第二个数字与剩下数字中最小的那个交换位置,以此类推,直到最后一个数字。
例如输入数组{7,5,4,8,6,2,3}
第一次排序通过查找最小的数字,交换7与2的位置;第二次查找5后面最小的数字,找到了3,交换5与3的位置;第三次查找4之后最小的数字,发现并没有数字比4小,交换4与4的位置(相当于没有改变);第四次查找8后面最小的数字5,交换8与5的位置。

起始值 7 5 4 8 6 2 3
第一次排序 2 5 4 8 6 7 3
第二次排序 2 3 4 8 6 7 5
第三次排序 2 3 4 5 6 7 8

因为剩下的数字中,可能有不止一个数字比当前数字小,所以需要一个临时值来储存当前最小的数字,还需要一个标志位来记录当前最小数字对应的位号。实现代码如下:

for(i = 0;i < n-1;i++)
{ 
   
	temp = a[i];
	iPot = i;
	for(j = i+1;j < 10;j++)  //从每一个数字依次向后查找
	{ 
   
		if(a[j] < temp)
		{ 
   
			temp = a[j];   //记录当前查找到的最小值与最小值对应的位号
			iPot = j;
		}
	}	
	a[iPot] = a[i];
	a[i] = temp;
} 

选择法排序逻辑简单,容易实现。共需要进行(n-1)!次比较,(n-1)次交换位置。计算量是固定的。对于较大的n运算速度较慢。

冒泡法排序

冒泡法排序是指:在排序时,每次比较数组中的相邻两个数组元素的值,将较小的数排在较大的数前面。
例如还是输入数组{7,5,4,8,6,2,3}

7 5 4 8 6 2 3

先比较2与3的大小,此时无需交换位置。
再比较6与2的大小,将2排在6的前面。

7 5 4 8 2 6 3

再比较2与8的大小,将2排在8的前面。

7 5 4 2 8 6 3

来看看代码是怎么实现的

int a[10];
int temp;
for(int i = 0;i < 10;i++)
{ 
   
	for(int j = 9;j > i;j--)
	{ 
   
		if(a[j] < a[j-1])
		{ 
   
			temp = a[j];
			a[j] = a[j-1];
			a[j-1] = temp;
		}
	}
}

这里的内循环for(int j = 9; j > i ; j –),只能从大到小递减来对比,这样才能保证可以把最小的数排到前面去。如果用for(int j = i+1;j < 9; j ++) 则无法保证把最小的数排到前面来。只有内外循环交错才能保证排序顺利进行。冒泡法排序是相对稳定的排序方法。

交换法排序

交换法排序是将每一位数与它之后的所有数字对比,如果发现比它小的数字,那么立即交换这两个数字的位置,连续向后对比直至最后一个数;然后再使用第二个数同样依次向后对比,直到排序完成。交换法排序和前面的选择法排序有些类似,选择法是找出后面最小的那个数字交换位置,而交换法则是后面只要有比当前数字小的值,立即交换位置,再继续对比。这样可以节约记录中间值和记录中间值对应位号的2个空间。但是需要更多次的交换运算。在数组基本有序时速度比选择法快。

int a[10];

for(i = 0;i <9;i++)
{ 
   
	for(j = i+1;j < 10;j++)
	{ 
   
		if(a[j] < a[i])
		{ 
   
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
}

插入法排序

插入法排序比较复杂,基本原理就是抽出一个数据,寻找相应的位置插入,再抽出一个数据,寻找相应的位置插入,直到完成排序。简单来说就是,对于一个数组来说,先取数组中的第二个数字,和第一个数字对比,如果比第一个数字小,则放到第一个数字前面;如果比第一个数字大,则放到第一个数字后面。然后取数组中第三个数字,与第二个数字和第一个数字对比,以此类推。

int a[10];
int iPos;

for(i = 1;i < 10;i++)
{ 
   
	temp = a[i];  //待插入的数字
	iPos = i-1;
	while((iPos >= 0) && (a[iPos] > temp))
	{ 
   
		a[iPos+1] = a[iPos];
		iPos--;
	}
	a[iPos+1] = temp;
}

假设现在有这样一段数列{1,2,3,6,9} 而下一个待插入的数是 a[5] = 4
也就是待插入值temp = 4,i = 5,iPos=4 那么函数是这样运行的:

先对比待插入的值temp 与 a[4] = 6 的大小,此时temp = 4,满足while循环,那么就把原来a[4]的值放在a[5]上

1 2 3 6 9
1 2 3 6 9

此时iPos自减,仍然满足while循环条件,继续执行while循环代码。再来对比temp与a[3]的大小,此时temp仍然为4,在while循环里并没有更改temp的值。发现a[3]还是小于temp,于是继续把a[3]也往后放一个,放到a[4]的位置。

1 2 3 6 9
1 2 3 6 9

此时iPos自减,但是因为a[2] = 3,那么a[2]的值比temp小,所以while循环结束,跳出循环。只需要将待插入的值temp的值填在此时空出来的a[iPos+1] 的位置即可。

1 2 3 4 6 9

折半法排序

折半法排序又称为快速排序,是选取一个中间值,然后把比中间值小的数字放在左边,比中间值大的数字放在右边。然后两边分别递归使用这个过程。折半法排序对于较大的n时有较快的运算速度,但是折半法排序是不稳定的,对应有相同关键字的记录,排序后结果可能会颠倒次序。但是可以通过对这种排序方法的学习,来熟悉了解一些递归的思想,以及二分法的实现。

CelerityRun(int left,int right,int array[])
{ 
   
	int i,j;
	int middle;
	int temp;
	i = left;
	j = right;
	middle = array[((right - left) >> 1) + left]; //实际这里的middle可以取左右边界内任意的一个值
	
	do
	{ 
   
		while((array[i] < middle) && (i < right))
		{ 
   
			i++;
		}
		while((array[j] > middle) && (j > left))
		{ 
   
			j--;
		}
		if(i<=j)
		{ 
   
			temp = array[i];
			array[i] = array[j];
			array[j] = array[i];
			i++;
			j--;
		}
	}while(i<=j)

	if(left < j)
		CelerityRun(left,j,array);
	if(right > i)
		CelerityRun(i,right,array);
}

在do while整个循环的过程中,middle的值是不变的

C语言中数组的排序算法——选择法、冒泡法、交换法、插入法、折半法

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/194157.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号