冒泡法排序_冒泡选择排序算法

冒泡法排序_冒泡选择排序算法/*冒泡法排序:共进行N-1趟比较,每趟比较中要进行N-1-i次两两比较时间复杂度:最差、平均都是O(n^2),最好是O(n)空间复杂度:O(1)稳定排序*/

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

Jetbrains全系列IDE稳定放心使用

/*冒泡法排序:共进行N-1趟比较,每趟比较中要进行N-1-i次两两比较
时间复杂度:最差、平均都是O(n^2),最好是O(n)
空间复杂度:O(1)
稳定排序*/

#include <stdio.h>
#define N 7
int main()
{
	int a[N],i,j,t;
	for(i=0;i<N;i++)
		scanf("%d",&a[i]);
	for(i=0;i<N-1;++i)
		for(j=0;j<N-1-i;++j)
			if(a[j]>a[j+1])//较大的数往下沉
			{
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
	printf("the sorted number:\n");
	for(i=0;i<N;i++)
		printf("%d",a[i]);
	return 0;
}


//-----------------时间复杂度O(n),空间复杂度O(1)(设计时:a[i] - 1不能大于数组a的下标范围)--------------------------
#include <iostream>
using namespace std;
int main()
{
	//int a[]={10,6,9,5,2,8,4,7,1,3};
	int a[]={6,5,4,3,7,8,9,10,11,12};
	int len=sizeof(a)/sizeof(int);
	int temp;
	for(int i=0;i<len;)
	{
		temp=a[a[i]-1];//不停的交换两个数
		a[a[i]-1]=a[i];
		a[i]=temp;
		if(a[i]=i+3)//使a[0]=3,a[1]=4....,这里需要知道数组中最小的数字,然后a[i]=i+3中i加最小的数字,注:最小的数字不能为0
			i++;
	}
	for(int i=0;i<len;++i)
		cout<<a[i]<<" ";
	return 0;
}

冒泡排序算法的改进

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

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

#include <iostream>
using namespace std;

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

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; //为下一趟排序作准备
	 } 
} 
int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	bubble_1(a,8);
	print(a,8);
}

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值,后移一位
	} 
}




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

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

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

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

(0)


相关推荐

  • JavaScript【5】高级特性(作用域、闭包、对象)

    JavaScript【5】高级特性(作用域、闭包、对象)

    2021年11月24日
  • 国际标准时间哪个时区_北京时间与世界时间的换算

    国际标准时间哪个时区_北京时间与世界时间的换算关于时间格式2016-08-9T10:01:54.123Z20160809100154.123Z处理方法今天遇到了一个奇怪的时间格式如以下格式,下面两种时间格式所表示的时间是同一个时间,这个不难理解//UTC时间,世界标准时间2016-08-9T10:01:54.123Z20160809100154.123Z如图所示,这是一张由网友提供的图片,里面显示的是时间UTC…

    2022年10月22日
  • C++中decltype与左值和右值「建议收藏」

    1decltype关键字decltype是C++11中引入的新的类型说明符。编译器根据分析表达式或者函数返回值来分析其类型。decltype的详细用法,请参考《C++中decltype的使用方法》2decltype与左值和右值decltype后面跟的表达式是左值或者右值时,编译器分析的类型会有所不同。如果表达式(非单个变量)的求值结果是左值,则编译器会得到一个引用类型;如果表达式(非单个变量)的求值结果是右值,则编译器会得到一个与表达式相同的类型。intarr[2]={10,2.

  • Java中this关键字详解

    Java中this关键字详解一、this关键字主要有三个应用: (1)this调用本类中的属性,也就是类中的成员变量; (2)this调用本类中的其他方法; (3)this调用本类中的其他构造方法,调用时要放在构造方法的首行。PublicClassStudent{Stringname;//定义一个成员变量nameprivatevoidSetName(Stringname){

  • 2022.01 激活_在线激活

    (2022.01 激活)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • 如何使用robots.txt及其详解

    如何使用robots.txt及其详解在国内,网站管理者似乎对robots.txt并没有引起多大重视,应一些朋友之请求,今天想通过这篇文章来简单谈一下robots.txt的写作。robots.txt基本介绍robots.txt是一个纯文本文件,在这个文件中网站管理者可以声明该网站中不想被robots访问的部分,或者指定搜索引擎只收录指定的内容。当一个搜索机器人(有的叫搜索蜘蛛)访问一个站点时,它会首先检查该站点根目录下是否存在robots.txt,如果存在,搜索机器人就会按照该文件中的内容来确定访问的范围;如果该文件不存在,…

发表回复

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

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