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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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值,后移一位
	} 
}